Amazon Interview Question for Software Engineer / Developers


Team: Kindle
Country: India
Interview Type: In-Person




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

We do not need to use extra space even we wanna use heap. We can make use of the array given to store result. For example, we can make use of the tail of the result array. At the beginning, the tail won't be touched, so we can use last n position in this array, and make it work as a heap.

- shou3301 December 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Agree. Time complexity is O(n*logk), additional space complexity (except result array) is O(1).

- Aleksey.M January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Good one, though I see there is no need to use a heap at all.

1. Out of the n arrays, copy the first array to the end of the result array.
2. For the remaining n-1 arrays, merge each of them with the result array itself and keep storing the values in the result array.

For ex: if each of the n sorted arrays is m, then the result array is assumed to have a space of nm.

1. In the first step copy the contents of the first array into the end of the result array so the values are stored from nm-n+1 to nm (assume for simplicity, the index is based at 1)
2. Merge the second array with the result array starting at nm-n+1 and keep storing the values from nm-2n+1 to nm
3. Repeat the above steps until the final array when you start merging the result array from n + 1 and store the values from 1 to nm

- Murali Mohan July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

we can use minimum heap of size n with 1st element from every array.
1. pop the minimum element from the heap and push the element from the arrya which contains minimum element and heapify again....this process continues till no element remain in any array .

- zeroByzero November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution is wonderful. Restriction was we can't use extra space.

- Riyad Parvez December 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

May be the expected answer is n-way merge sort.
1> First sort indivisual n arrays (may be using bubble sort)
2> now use n-way merge and save the result in resultant array

- sp!de? November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Notice that we can't use extra space. How much space will your n-way merge use?

- Vikas November 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Hi Vikas,
Since we have all n arrays already sorted, the next step i.e. n-way merge sort, won't take any extra space (except the resultant array).
In fact, external sorting, which is used in case of memory restriction also uses this technique.

in this sorting,
1>>we will read 1st number from each sorted array, and put the least number in the resultant array.
2>>increament the index for this array from which least number is taken
3>>read next numbers and write least number of this cycle to resultant array
4>>continue till we are out of numbers from all the arrays
:)

- sp!de? November 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the length of resultant array ?

- Srikant Aggarwal November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sp!de?,

>increament the index for this array from which least number is taken

If I understand your algorithm, you will need to store n indexes. So, it is not using O(1) space.

- Vikas November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@sp!de?,

>increament the index for this array from which least number is taken

If I understand your algorithm, you will need to store n indexes. So, it is not using O(1) space.

- Vikas November 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Pick the min of every array till there are no elements in any of the arrays and append the min to the output array. Uses 2-3 temp variables.

Complexity = O(n*m) where m is the total number of elements in the array.

- Vikas November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how do you keep track of next min element in each array without using non-constant additional space

- Anonymous March 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you please explain clearly?, n number of sorted arrays of fixed length?

- Andi November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think that's what Bucket Sort does.

- Nitin Gupta November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you mean merge sort.

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

def partition(a, s, e, m):
  if ( (e - s) == 1 ):
    if ( a[e/m][e%m] < a[s/m][s%m] ):
      (a[e/m][e%m], a[s/m][s%m]) = (a[s/m][s%m], a[e/m][e%m])
    return e
  x = (s+e)/2
  pv = a[x/m][x%m]
  (a[e/m][e%m], a[x/m][x%m]) = (a[x/m][x%m], a[e/m][e%m])
  x = s
  for i in range(s, e):
    if ( a[i/m][i%m] <= pv ):
      (a[i/m][i%m], a[x/m][x%m]) = (a[x/m][x%m], a[i/m][i%m])
      x += 1
  (a[x/m][x%m], a[e/m][e%m]) = (a[e/m][e%m], a[x/m][x%m])
  return x


def quicksort(a, left, right, m):
  # If the list has 2 or more items
  if ( left < right ):
    pi = partition(a, left, right, m)
    quicksort(a, left, pi-1, m)
    quicksort(a, pi + 1, right, m)


def sort_array(a):
  n = len(a)
  m = len(a[0])
  quicksort(a, 0, n*m-1, m)

a = [
  [9, 8, 7, 10, 15],
  [1, 2, 3, 11, 14],
  [6, 5, 4, 12, 13]
]

print(a)
sort_array(a)
print(a)

- shyam November 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think anyone cares about your program or wasting time trying to figure out its correct-ness.

Can you communicate your intentions with human language? Can you communicate your logic with human language?

So by the looks of it you are doing an n-way merge sort using quicksort?

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

This question doesn't sound right. Where do you put the result? Can we just pick any one of them to start putting the result and then use the next array and so on? If so, it's just a in-place merge sort.

- Chris November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its becoming hopehesless..After going through couple of questions today, I feel like people should first try to learn some form of a human comprehendible language properly before attempting to become a machine linguist. Reminds me of my highh school chemistry teacher who used to get pissed off at students who were preparing for the toughest engineering entrance exams but could not even perform a simple math calculations correctly.

- The Artist November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what you are trying to depict is the form of external sorting.....
u don't have sufficient space in the main memory to sort entire elements.....
so u do it by generating runs....
we construct a tournament tree with the help of input buffers and output buffers(by reading a block ) from second memory....
We increase the run number whenever we find a new element that enters into the tree by reading from second memory(and changing the run number if necessary).....

- don November 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi don, could you explain the "tournament tree with help of input and output buffers" a bit more. Maybe a link would be helpful.

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

well i think this might be a solution:
just copy all arrays in the final array and perform any sorting technique now on this big array, this will need O(n) for copying and O(nlogn) for sorting so eventually we end up with a over all O(n log n).


correct it if wrong.

- vishu November 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

n is total no. of elements

- vishu November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

take first two arrays
perform merge sort and put output in the output array
copy it back to the first two arrays, so now all elements in first array are lesser than the elements in the second array.

Now perform merge between 12 and 3

do the same thing

- Pushkar November 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take 2 arrays at a time
merge them
perform quicksort on them
space complexity remains o(n) and worst case time complexity will be o(n^2) avg case time complexity will be O(n log n)

- supratim.sengupta November 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Assuming length of all the array is fixed and same i.e. length
2. Here a[k][i] means ith element of kth array among N arrays. Just didn't get in my mind how to represent kth array so used this notation.
3. Starts from the back of the array. Takes the last element of all of the array and insert the maximum in last position of given_array and again inserts less than max in last-1 position.
4. Again for second last element of all the arrays.

#define Total_length length*NoOfArrrays
int given_array[Total_length]
int p=Total_length
for(int i=lenth;i>0;i--){
    for(int j=0;j<NoOfArrays;j++){
          for(int k=j; k<NoOfArrays;k++) {
                 if( a[k][i] > a[j][i] )
                    swap(a[k][i] , a[j][i] );
          }
          given_array[length--]=a[j];
     }
}

p.s. Improve if i am wrong !!!!

- nikkiani1991 November 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

take least element from 1st location of each array,increament the location by 1 index from where least element is taken.
Do the above step till all the arrays are done.
Do not take duplicate values in the final array.

- Anonymous January 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

take least element from 1st location of each array,increament the location by 1 index from where least element is taken.
Do the above step till all the arrays are done.
Do not take duplicate values in the final array.

- Anonymous January 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that you have n arrays in the files...and you can load only 1 of them of size m in memory at a time..n way merge sort (external sort) is the best bet.

1. Open the file stream from (m-1) files out of n and load the first value out of each into memory so total memory taken so far is (m-1)...now take the minimum element of the m-1 values and write it to a file or System outout buffer...so now u have used all of the m memory spaces...Once you have out 1 value, you can load next value from the input file stream just like we do in a typical merge sort.....repeat it untill all of the m files are done.
2. so now, you have 1 file which contains the sorted array for m files out of n.
3. Repeat the step 1 for all of the n files taken in groups of m.
4. Repeat the step 1,2 and 3 untill you get a singe sorted file....and thats what you want.

I hope it helps.

- A January 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

call find min on each of the n arrays every time, complexity O(n*k). Then find min of mins and place it in current index of result array, complexity O(n). Total time complexity O(n) and constant size (current index).

- Anonymous March 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In order to merge K-sorted arrays, we can simply merge the sorted sub-arrays at the back of the
bigger array.

I've added comments in the code. just to give the idea how it works, it is not the optimized version and also make
some assumption but overall gives the clear idea of the algorithm.

// A little modified form of merge algorithm, it just keep track of the start position
// in the bigger array.
void merge(int left[], int right[], int n, int m, int a[], int start) {

	int i = 0;
	int j = 0;
	while (i <n && j < m) {
		if (left[i] < right[j]){ 
			a[start++] = left[i++];
		}
		else {
			a[start++] = right[j++];
		}
	}

	while (i < n) 	a[start++] = left[i++];
	while (j < m) 	a[start++] = right[j++];

}

// The algorithm is based on the merge-sort merge algorithm.
// what it actually does is simple it simply picks up the list and
// merge it at the end of the bigger array. 

// a little arithematic for indexing is required.
// I've assume size of each sub-list to be 10 it can easily extends to different size lists.
// the logic is simple every time you perform the merge start from size of already merged list + size of new sub-list to be merged.
// The you need to remember two things at every iteration.
// first = size of array 'a', (i.e. elements that are present in array a)
// second = the starting index from where to start merging the new list to the existing list.
void merge_lists(int* lists[], int sz, int a[], int n) 
{ 
	
	// assume size of every sub-list = 10.
	int m = 10;			

	// flag to keep track whether it's a first pass
	// if yes then it simply 
	bool isFirstPass = false;		
	int iListIter = 0;

	// copy the array directly to a.
	while (sz > 0) {
		
		// pick the list and merge it 
		int* left = lists[iListIter];
		if (isFirstPass == false) {		// no elements are present in the main array.

			iListIter++;
			isFirstPass = true;

			// merge two lists in the bigger array.
			int* right = lists[iListIter];
		
			merge(left, right, m, m, a, n - (iListIter + 1)* m);		// start merging the arrays at the end.
			sz--;
		}
		else {
			merge(left, a + n - (iListIter * m), m, (iListIter * m), a, n - ((iListIter + 1)* m));
		}

		iListIter++;
		sz--;
	}
}

- Laiq Ahmed March 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you need to sort it in ascending order, simply form a MAX-HEAP and store it in the output array. At this point, the 0th element is guaranteed to be the maximum element. Here's the kicker - remove max and swap it with the last element in the heap. Now perform max-heapify on the root. Keep iterating until all roots have been deleted.

const int arr_length = ARRAY_LENGTH;
for(int i = 0; i < n; ++i)
{
	for(int j = 0; j < arr_length; ++j)
	{
		insert_heap(arr[i][j], &heap);
	}
}

int last = arr_length * n;
while(last > 0)
{
	swap(&heap, 0, last);
	--last; //remove last element from heap
	max_heapify(&heap, 0, last);
}

I'm leaving insert_heap, swap and max_heapify as standard methods. Complexity is O(nlogn) This doesn't leverage the fact that the initial arrays are sorted, so I'm sure there's a more efficient algorithm.

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

This is essentially in-place heap sort :)

- Anonymous July 24, 2013 | 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