## Amazon Interview Question

Country: United States

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

we can use n-way merge using minimum heap of size(min of no of row and coloumn ) ,
it is example of standard n-way merge , here we are given n-sorted rows in 2-D matrx .

algorithm would work like :

1. pick up 1st elements from all the rows and insert them into Min-heap.
2. top of element contain minimum element , pop it and insert element from the array
whose element was poped .
3. while making insertion check the last popped value , if it is same then do not push this into heap, simply increment its pointer in the repected row, this will take care of duplicates too.
3.keep doing this operation till no element is left in any of the row and heap .

Complexity: if matrix is of size m*n
O(log m)*m*n

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

min of first no in different rows. then time O(m*n*log(m)) space O(m)

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

No - heap takes O(logm) for comparison not O(m). Look at the solution I gave

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

yeah, I said space is O(m)

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

So let's do a dryrun for min heap approach:
a. Insert from the first row {2 5 7 9 14 16} first in the heap.
b. At this point the root node of the heap contains element 2.
c. Start inserting from second node {3 6 8 10 15 21}.So let's pick the first element of the second node which is 3.So we will check if 2<3 and it is so we will just add the 3 in the leaf node of the heap.
'C' step will be repeated for all the rest of the nodes in the row 2.
This whole thing will end once we have accounted for all the rows in the heap.
I wonder how will we take care of repeats?

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

I think you want to insert 2 3 4 7 into the min heap
when you process the heap, remove the root, which is 2,
add the second number in the first row into the heap, which is 5.
you need to keep a pointer for each row where all numbers before the pointer are already added into the heap.

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

why are you processing columnwise?

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

@anish1 ...this will work for repetition also and yang is not processing columnwise this is how you will have to create the heap picking 1st element from each row(starting with it) and then pick next element from row whose element has been recently popped from the min heap.

@zerobyzero ... ur logic is correct however your step 3(simply increment its pointer in the repected row) will be able to avoid adding repeated element to heap only if the repeated item is being brought into heap after pop or in other words the next smallest element is being inserted in heap which is same as popped element. However if the repeated elements were brought into heap from diff rows and they were not smallest at that time then they will be inserted in heap....Anyway it will work in that case also as you can always have repetition in min heap with a tie breaker

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

If memory is abundant, I think this can be done in O(m * n) time. The solutions shown up to this point are actually O((m * n) lg(m * n))

1. Find the biggest element k in the array. Time: O(m * n)
2. Create a 1D array Z of size k and set each value to zero. Time: O(m * n)
3. Insert every element into the array at the index equal to its value. This is basically a dummy hash table. For instance, 5 would go into Z[5]. Time: O(m * n)
4. Create a linked list L and set the head node of L equal to the smallest element in the array. Time: O(m) -> you can find it by iterating the first column
5. Now that the elements are sorted (other than the zeroes), iterate through array Z, inserting the values onto the end of the linked list L. Time: O(m * n)
6. Create an array R the size of the L and fill the array with the contents of L. Time: O(m * n)
7. Return R

Time: O(5 * m * n + m) = O(m * n)
Space: Constant (but could be quite large). Again, this solution emphasizes an vastly improved worst case time over optimizing space.

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

Cant largest element be found by only traversing last column...then its not o(m*n)...Am i missing somethin?

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

What if some numbers in the matrix are negative?

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

You need a hash table. Iterate through the matrix, and put the element in the hashtable if it is not in the hash and then put it in the new array. If the element is in the hashtable, skip the element and move on to the next one in the 2d matrix. Once you have gotten the unique elements from the matrix, use quicksort. O(nlgn) time complexity algo.

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

we can make a heap-tree from the given elements as heap tree is a balanced-Binary tree so height is propotional to logn so building up heap-tree from n-unique elements will take O(nlogn)time,then we can use heap-sort to sort in O(nlogn) time.This will save extra use of HashTable.

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

All we need is a binary tree, it should be faster to insert the elements and it provides a sorted set as a result.

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

this will be O(mn)log(mn) and also needs an extra O(mn) space

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

You can use a set. Set does not allow duplicates. Put all the elements in the set. Then remove and do quicksort.

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

Since each of the m rows are sorted, all you need to do is to do a m-way comparison to find the minimum element from the m rows. You can ignore duplicates since you know the previous minimum. This will give an O(mn*m) algorithm since there are m comparisons at each step.

However, the m-way comparison at each step to find the minimum can be done using a heap - which will give us an O(mn*logm) algorigm with only O(m) extra memory.

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

Care to give an example?

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

Here is the code:

class mycomparison
{
public:
bool operator() (const pair<int,int> & lhs,
const pair<int,int> & rhs)
{
return lhs.first > rhs.first;
}
};

vector<int> MergeMatrix(int input[M][N])
{
priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pq;
vector<int> result;
vector<int> current(M, 0);
for (int i=0; i < M; i++)
{
pair<int,int> value;
value.first = input[i][0];
value.second = i;
pq.push(value);
current[i]=0;
}
while (! pq.empty() )
{
pair<int,int> top;
top = pq.top();
pq.pop();
if  (result.size() ==0)
{
result.push_back(top.first);
}
else if (result[result.size()-1] != top.first)
{
result.push_back(top.first);
}

if (current[top.second] < N-1)
{
current[top.second]++;
top.first = input[top.second][current[top.second]];
pq.push(top);
}
}
return result;
}

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

This can be done in O(m * n) time using only arrays:

public static int[] MergeAndSort(int[][] inputArray){
int m = inputArray.length;
int n = inputArray[0].length;
int high = Integer.MIN_VALUE;
int low = Integer.MAX_VALUE;

for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (inputArray[i][j] > high)
high = inputArray[i][j];
if (inputArray[i][j] < low)
low = inputArray[i][j];
}
}

int[] hash = new int[high-low + 1];
int counter = 0;

for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (hash[inputArray[i][j] - low] == 0)
counter++;
hash[inputArray[i][j] - low] = 1;
}
}

int[] newOne = new int[counter];
int count = 0;

for (int i = low; i < high+1; i++)
if (hash[i - low] == 1)
newOne[count++] = i;

return newOne;
}

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

Would you mind explaining the logic?

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

further optimization
u don't need to traverse the whole 2D array to find the min and max elements . Since the row are sorted , just need to compare the first and last elements of all rows to find min and max.

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

Basically you are doing COUNTING SORT.
In this case: offset = hight- low + 1
Time and space in worst case: O(N*M + offset)

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

What if numbers in 2D array are very large?

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

Hello, my friend ,assume we have two rows, each row contains one element.
Row 1 : 1
Row 2: 2^31 -1

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

Where are you using the fact that given elements are sorted in a Row....May be that needs to be considered??

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

The approach should be similar to the one used in merge sort to merge the sorted parts. The only difference is here we have m parts comparing to the 2 parts in standard merge sort. Here is the Java implementation

import java.util.Arrays;

public class Merge {
public int[] mergeAndSort(int[][] matrix) {
if (matrix == null) {
return null;
}
int[] result = new int[matrix.length * matrix[0].length];  //assuming n is fixed, otherwise it can be calculated
int[] rowsIndexes = new int[matrix.length];
int arrayIndex = 0;
int currentCount = 0;
int max = getMax(matrix);
while (currentCount++ < result.length) {
int min = getNextMatrixMin(matrix, rowsIndexes, max);
if (arrayIndex == 0 || min > result[arrayIndex-1]) {
result[arrayIndex++] = min;
}
}
return trim(result, arrayIndex);
}

private int[] trim(int[] array, int toSize) {
int[] trimmed = new int[toSize];
for (int i = 0; i < toSize; i++) {
trimmed[i] = array[i];
}
return trimmed;
}

private int getMax(int[][] matrix) {
int max = matrix[0][matrix[0].length - 1]; //last element in the first row

//check if the any last element in other rows is bigger
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][matrix[i].length - 1] > max) {
max = matrix[i][matrix[i].length - 1];
}
}
return max;
}

private int getNextMatrixMin(int[][] matrix, int[] rowsIndexes, int max) {
int min = max;
int index = 0;
for (int i = 0; i < matrix.length; i++) {
if (rowsIndexes[i] < matrix[i].length  && matrix[i][rowsIndexes[i]] < min) {
min = matrix[i][rowsIndexes[i]];
index = i;
}
}
rowsIndexes[index]++;
return min;
}

public static void main(String[] args) {
int matrix[][] = {
{2, 5, 7, 9, 14, 16},
{3, 6, 8, 10, 15, 21},
{4, 7, 9, 15, 22, 35},
{7, 8, 9, 22, 40, 58}
};

int[] array = new Merge().mergeAndSort(matrix);
System.out.println(Arrays.toString(array));

}
}

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

In python:

def sort2darr(arr):
mpos = [1]*len(arr[0])
heap = [(x[0],i) for (i,x) in enumerate(arr)]
heapq.heapify(heap)
(val, idx) = heapq.heappop(heap)
res = [val]
mpos[idx] += 1
while True:
try:
(val, idx) = heapq.heappop(heap)
except IndexError:
return res # done
if val != res[-1]:
res.append(val)
if mpos[idx] < len(arr[0]):
to_push = (arr[idx][mpos[idx]], idx)
heapq.heappush(heap, to_push)
mpos[idx] += 1

The idea is to maintain a heap of the smallest item in each row, advancing the indexes.

Jerry.

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

Or, if you just want pure python magic, here's a one liner, using itertools

def sort2darr(arr):
return sorted(set(itertools.chain(arr)))

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

I think we can use Binary Search Tree to store unique values of 2D array in sorted manner. STL set can also be used.

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

You can use TOURNAMENT tree.

Time: O(N*M*lgM)
Space: O(2M-1) ~ O(M)

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

This can be done using merge. foreach row i in Arr Merge row(i) to row(i+1). While merging, make sure to drop the number if its duplicate.

Merging will take O(n) because rows are sorted. Merging m rows will take O(m).
Total complexity time O(n*m). Space complexity O(m+n).

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

Here is a little piece of code from me:

import java.util.Arrays;
public class SortedMatrixToSortedArray {

public static void main(String... args) {
int[][] matrix = {
{2, 5, 7, 9, 14, 16},
{3, 6, 8, 10, 15, 21},
{4, 7, 9, 15, 22, 35},
{7, 8, 9, 22, 40, 58}
};
int[] result = mergeAndSort(matrix);
int[] expected = {2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 21, 22, 35,
40, 58};
System.out.printf("result:   %s%n", Arrays.toString(result));
System.out.printf("expected: %s%n", Arrays.toString(expected));
}

private static int[] mergeAndSort(int[][] matrix) {
int[] result = new int[]{};
for (int[] row : matrix) {
result = mergeAndSort(result, row);
}
return result;
}

private static int[] mergeAndSort(int[] x, int[] y) {
int n = findDistinctLength(x, y);
int[] result = new int[n];
for (int k = 0, i = 0, j = 0; k < n; k++) {
if (i == x.length) {
result[k] = y[j++];
} else if (j == y.length) {
result[k] = x[i++];
} else if (x[i] < y[j]) {
result[k] = x[i++];
} else if (x[i] > y[j]) {
result[k] = y[j++];
} else {
result[k] = x[i];
i++;
j++;
}
}
return result;
}

private static int findDistinctLength(int[] x, int[] y) {
int i = 0;
int j = 0;
int n = 0;
while (i < x.length && j < y.length) {
if (x[i] < y[j]) {
i++;
} else if (x[i] > y[j]) {
j++;
} else {
i++;
j++;
}
n++;
}
return n + x.length - i + y.length - j;
}

}

See with tests here - github.com/ffbit/just-for-fun/blob/master/src/test/java/com/ffbit/fun/array/SortedMatrixToSortedArray.java

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

The problem can be solved using binary search tree / merge sort

An alternate way of solving this problem,

1. Created an 1-D array
2. Since each row is sorted, start reading data from first column of each row, and store into 1-D. Starting from row 0 to r - 1.
3. Record the tail index of the 1D array.
4. While storing the data, looks from backwards of 1-D array to find an slot for the new element / discard duplicate.
5. Shift the elements towards right, when new elements are not added towards the end of 1D array.
6. Step 2 is repeated till last column

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

1st method: merge sort
take two rows at a time and merge adding check for repetitions. This will require maintaining two arrays of size m*n and need to switch between them. T(m*n) S(m*n) however constants and space requirements are high.

2nd method: maintain a min-heap
maintain 2 arrays of size m. one will store the row index of elements in a min heap and other the corresponding column index. solution can be devised in following 3 steps:
1) Initialize a min Heap.
2) Make a min Heap
3) Pop elements and store in resultant array.
Below code gives an idea.

int main()
{
int arr[m][n],hashRow[m],minArr[m],resArr[m*n],i,j;
i=0;
1st step
while(i<m)
{
j=0;
while(j<n)
{
if(!isUnique(minArr,arr[i][j]))           //---------T(m)
j++;
else
{
minArr[index]=i;
hashRow[i]=j;
index++;
break;
}
}
}
// 2nd step
makeMinHeap(minArr,hashRow,index-1); //--------------T(mlogm)
//3rd step
while(index>=0)
{
resArr[count++]=minArr[0];
i=minArr[0];
j=resArr[i]+1;
while(j<n)
{
if(!isUnique(minArr,arr[i][j]))
j++;
else
{
minArr[0]=arr[i][j];
hashRow[i]=j;
break;
}
}
if(j=n)
{
minArr[0]=minArr[index];
index--;
}
restoreDown(minArr,index,0);   //-------------------T(m*nlogm)
}
}

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

#include<stdio.h>
#include<stdlib.h>
int B[100];
int j=0;
void smallest(int *p[],int n, int r, int *counter)
{
int i;int min=*p[r];

for(i=r+1;i<n;i++)
{
if(*(p[i])<min)
{
min=*p[i];
break;
}
}
for(i=0;i<n;i++)
{
if(min==*p[i])
{
p[i]++;
counter[i]++;
}
}
B[j++]=min;
}

int main()
{

int x[4][6]={{2,5,7,9,14,16},
{3,6,8,10,15,21},
{4,7,9,15,22,35},
{7,8,9,22,40,58}};
int m=4;//number of rows
int n=6;//number of columns
int *p[4]={x[0],x[1],x[2],x[3]};//array of pointer storing each rows
int i,k=1;
int counter[4];
int r=0;
for(i=0;i<m;i++)
counter[i]=0;
while(k<m*n)
{
if(*p[r]==x[m-1][n-1])
break;
if(counter[r]==n)
r++;
smallest(p,m,r,counter);
k++;
}
B[j++]=x[m-1][n-1];
for(i=0;i<j;i++)
printf("%d\n",B[i]);
//
}

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.