## Ebay Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

They say it is list so we do not need extra memory will not be needed till you can merge the nodes in between by using next pointers

something like this : may need to be fixed for bugs\cornercase but logic should be like this
{
foreach(List<int> outerlist in sortedList.skip(1).take())
{
MergeList(MergedList, outerList);
}

return MergedList;
}

{
if(list1.data < list2.data)
{
list root = list1current = list1;
}

while(list1current != null && list2current != null)
{
if(list1current < list2current)
list1current = list2current++;
else
{
temp = list1current.next ;
list1current.next = list2current;
list2current = list2current.next;
list1current.next.next = temp;
list1current = list1current.next;
}
}

if (list2current != null)
{
list1current.next = list2current;
}

return rootlist;
}

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

You can merge the lists in pairs. First merge lists 1 and 2, then 3 and 4, and so on. After you're done, you have half as many lists. Make another pass to merge those lists in pairs again and you'll have a quarter of the number of lists you started with. Do this again and again until you only have one list.

Over the course of the entire algorithm, the number of comparisons is O(log N * totalInputElements), since it's one comparison per element per pass. One pass halves the number of lists and therefore there will be O(log N) passes. This number of comparisons is the asymptotic minimum for merging N sorted lists. Only O(1) space is used (additional space would be used if you were doing this with arrays, but it's not needed for linked lists).

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

Or better: glue lists and do mergesort!

Same asymp. runtime, space and comparisons.

You are basically doing mergesort here, duh

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

If you glued the lists, you'd have to do some kind of mergesort that detects existing runs and exploits them (e.g. Timsort). I assume the number of elements E is >> N and that therefore there is some difference between O(E log N) and O(E log E), the complexity of naive mergesort.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Glue the lists together into a single list.
Mergesort the list (can be done with O(1) space for LLs)

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

how this ensures minimum number of comparison... ?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

We have N Lists. Maintain a min heap of size N. The heap will store the top value of all the lists initially and will help in getting the min at any point of time in O(1). Each node in the heap will also store a reference to the list it belongs to, inorder to handle duplicates. Have N pointers pointing to the top of the N lists. Do the same thing merge sort does, but get the min in O(logN) time instead of doing O(N) comparisons.

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

Oh, I saw the fact that extra memory shouldn't be used. That's kind of weird they would tell you such a thing. I am open to seeing other solutions.

The other way to do it would be to use segment trees to find the minimum in O(1). Updates to the tree will take O(logN). Then again seg trees take O(N) space.

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.

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