Amazon Interview Question Software Engineer / Developers
I don't think complexity will be O(Nlogk).
I think merging will be done as follows:
Step 1: Merge k/2 lists each of size N.
Complexity=> 2*N ( OR O(N)) for each of the lists
Hence total order should be (k/2)*2*N
O(K*N)
Step 2: Merge k/4 lists each of size 2N.
Complexity 4*N ( OR O(N)) for each of the lists
Hence total order should be (k/4)*4*N
O(K*N)
...
Total steps will be logK.
Hence Total Complexity will Be : O(N*K logK )
Space complexity : N*K
Agree with Aditya.
Method 1: To get min, maintain a min-heap of K elements, one from each of the K LLs, that's O(logK), and since all NK elements should be compared in this way, total complexity is O(NKlogK).
Method 2: Like Ojha said, in each round merge K/2 pairs of LLs. So O(NK) for each round, since all elements should be visited and compared. Altogether logK rounds, so total complexity is O(NKlogK).
We have to maintain k pointers for each linked list separately.
If we maintain these k pointers in a Heap, then to find the smallest element among those k pointers will take only O(log k) time.
Hence total complexity will be O(nlogk).
Please correct me if I am wrong.
As there are total n*k elements in all.
( k lists having n each ).
Hence for inserting each one into heap ( size K ),
Complexity will be logK.
hence total will be O( n*k logk).
Its obvious as There are n*k total elements each should be acessed once. that's getting reflected in the ORDER.
i think the above answer is wrong...because each individual list is sorted and we have to divide the entire sorted lists into pairs, merge-sort them and then each pair merge sort result is again merge-sorted...so a total of (k-1) sorts are taking place...
And the time complexity for each merge sort is O(n*logn) if n is the size of each list
so for (k-1) lists, its O((k-1)*(nlogn)).
Case ii) But what happens if each list is of different size, then too i think that the answer would be near to the above answer...
Please correct me if i am wrong.
Use Counting sort. Complexity-O(n+k).
As the k lists are already sorted. The biggest element can be found in time O(k). Then use counting sort by treating the all the k lists as single list (intuitive- adding k lists together) which will take O(n+k)..
complexity will be linear if k<=n.
Maintaining heap completely ignores the fact that lists are sorted.
We can maintain k pointers and select least and next-to-least elements (O(k) + O(logK) - 2), once we increment the pointer in list with least element, we can immediately compare it with the next-to-least element - this will potentially reduce the time to half. I don't think asymptotic bound can go below O(nk).
Suppose N be the size of each individual List.
- Manjesh Ojha December 11, 2010Follow the below steps
1. First Take two list at a time and merge them. do the same process for all the remaining lists.This operation results in k/2 lists. time complexity for this step is O(N)
2. Repeat steps till k/2 == 1.
Total Time Complexity: O(Nlogk).
Correct me for any mistakes :)