Interview Report
- 0of 0 votes
Answersk-way-mergesort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine in which you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, and so on until you merge in the final (kth) input array. What is the time taken for this strategy, as a function of k and n ? (Optional: can you think of a faster way to do the k-way merge procedure ?)
- saurabh March 15, 2012 in India
θ(n^2(k))
θ(n(k^2))
θ(nk)
θ(nlog(k))| Report Duplicate | Flag | PURGE
- 0of 0 votes
Answers3-way-mergesort : Suppose instead of dividing in half at each step of the mergesort, you divide into thirds, sort each third, and finally combine all of them using a three way merge. What is the overall running time of this algorithm ? (Hint - Note that the merge step can still be implemented in O(n) time.)
- saurabh March 15, 2012 in India
n
nlog(n)
n^2(log(n))
n((log(n))^2)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm