how to create a visual studio Normal C/CPP project

Create new Project

Then select Visual C++ -> General -> Empty Project

Reverse the Linked List in K pairs

Problem description and solution can be found at
http://geeksforgeeks.org/?p=8014

Main points here.

1)reverse the first K pairs by normal reverse technique.
2)one pointer will contain last element of the reversed list
3)special check for first time.. to change root and master prev node.
4) special check to end the list

Monolithic and microlithic kernel

http://welovec.blogspot.in/2011/04/difference-between-monolithic-and.html

Nothing to cram, funda is simple as their names. Mono means everthing in kernel space.
Micro means very minimal in kernel space.

Mono what goes into the kernel (kernel space)
Process management, memrory management, file system, i/o services etc. e.g Linux kernel;

Micro Kernels what goes into the kernel
very minimal support for the process management goes into the kernel, everything else all above mentioned things are implemented in user space.

These services in user space are called as servers. kernel communicates with them with message passing(IPC). e.g QNX





The main disdvantage of monolithic kernels is the dependency between system components - a bug might crash the entire system - and the fact that large kernels also

become difficult to mantain.

Other disadvantages are the kernel size, lack of extensibility and the bad maintainability. Bug-fixing or the addition of new features means a recompilation of the whole

ernel. This is time and resource consuming because the compilation of a new kernel can take severalhours and alot of memory. Everytime someone adds a new feature or

xes a bug, it means recompilation of the whole kernel.

Copy a linked list with next and arbit pointer

http://geeksforgeeks.org/?p=1155

Look at method Number 3.
The funda here is to insert new node in between the nodes of original ist in way like this

1-2-3-4-__

1-1-2-2-3-3-4-4__

The new node instered have random pointer as zero.

Now in second pass we will link the arb pointer as this

copyList->arbit = org->arb->next. this would work and we would reach to the replica of org node. as in our new node orgList next pointer is the node which will be our final node in the new list.


not in third pass. to modify correct the next pointer

like cop->next = copy->next->next
and org ->next = org->next->next.


set the last pointer of the org list to the zero.

Implement a stack where, getMinValue() operation is of O(1)

Main source of the article

http://www.rawkam.com/?p=1337

The problem statement is: Implement a stack where, getMinValue() operation is of O(1).

Solution :
1st Soultion : maintain two stacks. First stack is the normal one. Second stack top will always contain the minimum value at the point. So when ever you need min value simply take it form the second stack top element.

Push Operation
aprat from normal operation on first stack
Add the element to second stack if top most element of the second stack is less then the current element.

Pop Operation
First stack normal pop up will be done.
Check if the poped element is same as the top element in the second stack. then remove that element from the second stack as well.

Pros and Cons: Pros are all three operations ie. push pop and getMinValue are of O(1). But the flip side is that the it requires more space.


2nd Solution:
Mainin the pointer minPoiner, and you need to modify the pointer when doing Pop operation.in Pop operation may require traversal of the entire stack to find the next min value.

pros : NO extra space, but the Pop operation is O(n).



3rd solution :
Modify the stack node structure itself. add one field that points to the next min element.
Funda is like this. first each node will have an extra field called next min.
node {
next;
data;
nextMin;
}

Plus as usal there would be one pointer Min Pointer which will point to the current min value element.

Push operation
if current pusehed element is less then the earlier maintained min value. Definatly you need to modify the Min Pointer but you also need to do one more thing. like

top->nextMin = Old Min
Min = new min.

Pop Operation
Very simple if current poped node is the min node simply put the min node to top->next min node.


Please note that this can be little deseptive, as this nextMin we will not use for all the nodes.

Both push pop and get min are of order O(1)

Doubly Linked list using one Pointer

Problem : The question is to implement the doubly linked list. But you should maintain only one pointer per node.

Solution :
Remember how to swap the two numbers without using any third variable. XOR funda.

Same thing is applied here.
Suppose list is as below
A - B -C

What we will do is, we will main the address difference of the previous and next node in the current node in the link field.

e.g in case of B

node->link = A XOR C.

so when you want to traverse from left to right, you need left pointer .

and can find Address of c as A XOR node->link == A XOR A XOR C =c

similarly you can go back to the right to left, only thing is you need address of the right node here to traverse.


some additional info
1) You need to maintain two extra node here. start and end. start -> left = NULL
and similarly end -> right = NULL

2) you need additional node info here to travel to next node. e.g need address of A if you want to go from B to C

reference link is at

http://www.linuxjournal.com/article/6828?page=0,0

Find repeated array

Problem: You have any array n+2. It has elements from 1 to n and two other elements are repeated. We need to find the repeated elements. Solution should not more then O(n) complexity

Hint: If you use the array value as the index to jum to some location. So the location where you are reaching after the jump should be visited only once. If you reach there more then one way, it means the key by which you are coming here already used.