Amazon Interview Question
Software Engineer / DevelopersTeam: Kindle
Country: India
Interview Type: In-Person
Agree. Time complexity is O(n*logk), additional space complexity (except result array) is O(1).
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
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 .
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
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?,
>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.
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.
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)
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.
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).....
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.
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 !!!!
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.
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).
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--;
}
}
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.
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