Ebay Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Lets say each list is of size M
Take list[0],list[1] merge them, take list[2],list[3] merge them,.. take list[n-2],list[n-1] and merge them
Next take two previously sorted list and merge them, keep doing this unil there is one list remaining.
compleixty O(MXN)
or
Merge the list[0] and list[1] call the merged list mergeList
for(i = 2 ; i < n ;i++)
merge(mergeList, list[i])
This is again a O(MXN) algo
struct node{
node * next;
int data;
};
node * simple_merge(node * list1, node * list2)
{
node * result = NULL;
node * p1 = list1;
node * p2 = list2;
node * p3 = NULL;
while(p1!=NULL && p2!=NULL)
{
node * chosen = NULL;
if(p2== NULL|| (p1!=NULL && p2->data > p1->data))
{
chosen = p1;
p1 = p1->next;
}
else
{
chosen = p2;
p2 = p2->next;
}
if(result == NULL)
{
result = chosen;
p3 = result;
}
else
{
p3->next = chosen;
p3 = chosen;
}
chosen->next = NULL;
}
return result;
}
node * merge_lists(node ** lists, int numLists)
{
node * result = NULL;
node ** currents = new node * [numLists];
if(numLists == 1)
{
result = lists[0];
}
if(numLists == 2)
{
result=simple_merge(lists[0], lists[1]);
}
else
{
int index = numLists/2;
node * result1= merge_lists(lists, index);
node * result2 = merge_lists(lists[index+1], numLists-index);
result=simple_merge(result1, result2);
}
return result;
}
public static Node NmergeSort(LinkedList A[]){
int N= A.length;
Node res=null;
Node node = new Node(null, 0);
while(A.length>0){
int min = Integer.MAX_VALUE;
int I=-1;
for(int i=0;i<N;i++){
if(A[i]!=null && A[i].head.val<min){
min = A[i].head.val;
I=i;
}
}
node = A[I].head;
A[I].head = A[I].head.next;
if(res==null){
res = node;
}else{
node.next=res;
res=node;
}
}
return res;
}
public static Node NmergeSort(LinkedList A[]){
int N= A.length;
Node res=null;
Node node = new Node(null, 0);
while(A.length>0){
int min = Integer.MAX_VALUE;
int I=-1;
for(int i=0;i<N;i++){
if(A[i]!=null && A[i].head.val<min){
min = A[i].head.val;
I=i;
}
}
node = A[I].head;
A[I].head = A[I].head.next;
if(res==null){
res = node;
}else{
node.next=res;
res=node;
}
}
return res;
}
Does the new list has to be sorted as well ? Can u give an example ?
- An Enthusiast April 05, 2014