Amazon Interview Question
Software Engineer / DevelopersWe can have a result list initialized to null
Iterate through the n sorted lists and do
merge(result,list);
Assume the unsigned lists[] contain the head pointers of n sorted lists
struct node* mergeLists(unsigned int lists[])
{
struct node *result = null;
for(i=0;i<n;i++)
result=merge(result,lists[i]);
return result; //return the head of the n sorted single list
}
struct node* merge(struct node *a, struct node *b)
{
struct node* result=null;
if(!a)
return b;
if(!b)
return a;
if(a->data<=b->data)
{
result=a;
result->next=merge(a->next,b);
}
else
{
result=b;
result->next=merge(a,b->next);
}
return result;
}
We cannot avoid extra space .The best we can do is to free the heap after the insertion .And the lists to be merged as well .
We can merge all the sorted lists taking two lists at a time.
Ex:
Linkedlist1
1->5->8>14
LinkedList2
0->4->6->15->16
Now merge above two linked lists with alternate elements
1->0->5->4->8->6->14->15->16 0(2*k)
Now sort (1,2) , (2,3) , (3,4) etc position elements in the merged list
after sorting(1,2)
new linked list is
0->1->5->4->8->6->14->15->16
after sorting(2,3)
new linked list is
0->1->5->4->8->6->14->15->16
after sorting(3,4)
new linked list is
0->1->4->5->8->6->14->15->16
.
.
.
Final Linked List
0->1->4->5->6->8->14->15->16 : 0(2*k)
Similarly we can merge other n-2 list without using extra space
However the over all order is (n*k)
In previous merging algorithm there is a problem that ..
1 -> 5 -> 7
2 -> 3 -> 4 -> 6 -> 8
Correct it again ...
This is such a common question.
Use a heap. Get the top elements of all the elements and put it in heap. For every element removed from top of the heap, get the next element in the sorted array which current element belonged to and add it to the heap.
Repeat this till no elements are left in all lists. This will result in N(lgK) efficiency.
Perfect.
Construct a min-heap with a size of number of linked lists. always the toor node will have the min element. remove the root element, and insert the next element in the same tree. The insertion is of O(log k) where 'K' is the number of lists, and this process will be continued for (n * k) elements, supposing that there are average n elements in each list. so the total complexity will be O(n * k * log k).
In contrast if we keep merging taking 2 lists at a time, it will be O( n* n * k).
when a element is removed of the heap, how would you determine which list the element originally belonged to ??
secondly, each time a element is removed it would take O(log n) to insert a new element and maintain heap...(if possible to determine list by your method).
Clarify me if i am wrong ?
Another solution:
We have 3 values: 1, 2, and 3. to sort this we can use following algo:
traverse the list
-when we get node with value 1, remove the node from the
list and insert it at the begining
-when we get 3, remove the node from list and insert it at
the end.
-when we get 2, just leave it like that and move ahead.
This way however the sorted list will not preserve the "order".
To deal with that we can:
-save the node pointer to
the last inserted position for node values.
OR
-sort in descending order i.e. removing and inserting 1, 3
at end,begining respectively.
use merge sort for each linked list.
- Dinesh May 23, 2011