## Amazon Interview Question for SDE1s

Country: India
Interview Type: In-Person

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

take every two adjacent sorted arrays, merge them in place say the initial sorted arrays are X1 X2 X3 ...XN.
we merge X1 and X2 in place keeping the result in array which is indexed from X1[0] to
X2 [2N-1] similarly for the next two arrays. after the first pass we have m/2 sorted arrays of length 2n each . in the next pass we shall consider sorted arrays of size double the previous pass.
every pass takes m*n time and we have logm no. of passes.total time complexity is O(mnlogm)

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

What if m != 2^k..?? I think this method wont work.. Correct me if I am wrong..

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

store elements in binary search tree and do IN order

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

Please could you share any code, you think is going to work

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

1. Maintain a heap of size m (number of arrays) .
2. Create a min heap containing first elements of all m arrays.
3. Pull the root node from the heap. This is the smallest element.
4. Add to the heap, the second node of the array to which this number belongs to.
5. Heapify the modified heap
6. Repeat step 2 to 6 until all elements are processed.

Algorithm complexity - O(log(mn))

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

This is the Mergesort Merge Function Call.

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

In place merge sort might be the answer. In reality In place merge sort is hard to get right the easier solution is Quicksort.

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

Assuming the output array's space is availabe.. make a heap of all the arrays and heapsort. Better then O(n^2) by merging individually..

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.