Amazon Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

use merge sort for each linked list.

- Dinesh May 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We 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;
}

- Anonymous May 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Need to avoid extra space.

- Anonymous June 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

- san June 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

we can!! there is a mergesort without using extra space. mergesort two link list and result would be concatenation of the two lists.

- vivekh February 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Satish June 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In previous merging algorithm there is a problem that ..
1 -> 5 -> 7
2 -> 3 -> 4 -> 6 -> 8

Correct it again ...

- Nagarjuna October 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose there are 2 lists
1) 1,7,11,13,19
2) 15,18,20,25,36

Merge them:
(1,15),(7,18),(11,20),(13,25),(19,36).

Even if u sort (1,2),(3,4).....it would be same list.
Doesn't work in these cases.

- Piyush Beli February 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Anonymous May 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- @rams May 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- hello June 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Abhinav July 04, 2011 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More