Technical Interview Preparation

We can think of two different solutions -
Sol 1:
With additional memory where time complexity of findmin(),Push(),Pop() is O(1) but space complexity is O(n). Along with pushing the elements push the current minimum on to the stack. For pop operation pop 2 elements instead of 1 , it is still O(1).
For ex: Let us assume the following numbers which are pushed on to the stack.
4 2 9 3 6 1
Stack state will be something like below
4 4 2 2 9 2 3 2 6 2 1 1.
POP(x) = pop(), pop().
Where POP(x) is modified stack pop operation. pop() is standard pop() operation.
FINDMIN(x)=pop()
PUSH(x)=push() and push( MIN(pop(),elem)).
Where PUSH(x) is modified stack push operation. push() is standard push() operation.
Here storage needed for stack is 2n where n is number of elements in the stack.

Sol 2:

1. Start reversing the list. If you reach the head, then there is a loop.
But this changes the list. So, reverse the list again.
2. Second solution is called Hare and Tortoise approach. Basically have 2 ptrs both
pointing to the start of the list. Increment first pointer by one and
second pointer by 2. After each increment comapre if they are equal. They will meet if there is a loop.

p1 = p2 = head;
do {
p1 = p1->next;
p2 = p2->next->next;
} while (p1 != p2);

3. Hash all seen nodes and compare the next node with the nodes in the hash. If a node is already present in the hash then there is a loop.

If the list is circular and there are no references to the nodes in the list from anywhere else! Just copy the contents of the next node and delete the next node. If the list is not circular, we can delete any but the last node using this idea. In that case, mark the last node as dummy!

NODE *DupRem(NODE *head)
{
NODE *p1 = head, *p2, *resultList = NULL, *temp = NULL;
while(p1 != NULL)
{
p2 = p1->link;
while(p2 != NULL)
{
if(p1->data == p2->data)
{
break;
}

else
{
p2 = p2->link;
}
}

if(p1->data==p2->data)
{
p1 = p1->link;
}else
{
if(resultList == NULL)
{
resultList = p1;
temp = p1;
p1 = p1->link;
}else
{
temp->link = p1;
temp = temp->link;
p1 = p1->link;
}
}
}
return resultList;
}

list* merge(LIST* list1, LIST* list2){
LIST *it1, *it2, *head;
if(!list1) return list2;
if(!list2) return list1;
head = (list1->value value) ? list1 : list2;
if(head == list1)
{ it1 = list1; it2 = list2;
}
else{
it1 = list2;
it2 = list1;
}
while(it1->next && it2){
if(it1->next->value >= it2->value){
list *temp = it1->next;
it1->next = it2;
it2 = it2->next;
it1->next->next = temp;
}
else{
it1 = it1->next;
}
}

if(it2)
it1->next = it2;
return head;
}

Sol:
Original list: head->1->2->3->4->5->NIL should be transformed to head->2->1->4->3->5-> NIL

int reverse_pairs(LLIST ** head)
{
LLIST * temp = ULL;
LLIST* current_pair = *head;
LLIST** previouspair = head;
while((current_pair != NULL) && (current_pair->next != NULL))
{
temp = current_pair;
current_pair = current_pair->next;
temp->next = current_pair->next;
current_pair->next = temp;
*previouspair = current_pair;
current_pair = temp->next;
previouspair = &temp->next;
}
return 0;
}

Sol:
We can solve this easily using Hare and Tortoise approach. Basically have 2 pointers both pointing to the start of the list. Increment one pointer by 1 and
another by 2. When pointer 2 reaches end of the list pointer 1 will be in the middle of the linked list.

Node *FindMiddle( Node *head )
{
Node *p1, p2;
p1 = p2 = head;
while( p2 && p2->next )
{
p2 = p2->next->next;
p1 = p1->next;
}
return( p1 );
}

Sol: Have 2 pointers at the beginning of the linked list. Move ptr1 by n locations. Then start moving ptr2(which is at beginning of the list) parallel with ptr1. By the time ptr1 reaches the end of linked list, ptr2 will be at the nth last element.

Code:
void nth_last_elment(NODE *ln, int N)
{
NODE *nelement = ln, *node = ln;int i = 0 ;

while(i < N && node != NULL){
i++;
node = node->next;

}
if(i != N)
{
printf(“\n Lesser than N elements in list %d \n “,N);
return ;
}
else
{
while(node != NULL)
{
node = node->next;
nelement = nelement->next;
}
}
printf(“\n %dth element of link list from end is : %d ” ,N,nelement->info);
}