## Amazon Interview Question for Computer Scientists

• 1
of 1 vote

Country: United States
Interview Type: Written Test

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

Note that a standard sorting algorithm can do what you want.

You can simply sort the n^2 array in Ω(n^2 log n^2) time with merge sort, and note that Ω(n ^2 log n^2) = 2 n^2 log n is Ω(n^2 log n) as required.

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

Correct its just sorting n^2 elements you can use merge sort with complexity ( n^2 Log n^2) which is 2*n^2Logn

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

1. Sort the array first.
2. Assign the value of the sorted result one by one starting from the first one to the result 2-d array diagonally starting from the top-left cell.

Time complexity for 1st step is n^2*log(n^2) = 2*n^2log(n), and 2nd step costs n^2. Thus, the overall cost is O(n^2log(n)).

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

``````public int[][] convert(int[] arr) {

int dem = (int) Math.ceil(Math.sqrt(arr.length));
int[][] res = new int[dem][dem];

Arrays.sort(arr);
int p = 0;
for (int row = 0; row < dem; ++row) {
for (int c = 0, r = row; r >= 0 && c < dem; --r, ++c) {
res[r][c] = arr[p++];
}
}
for (int col = 1; col < dem; ++col) {
for (int r = dem - 1, c = col; r >= 0 && c < dem; --r, ++c) {
res[r][c] = arr[p++];
}
}
return res;
}``````

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

I guess the question is to output a matrix where both rows and column are sorted. To do that
1) Sort the n^2 elements O(n^2 logn)
2) Make the first n elements as first row, next n elements as 2nd row.....
Other matrix combinations can be formed by using the below logic
1) Choose a value of increment d <n
2) Pick up the elements of a row in increments of d e.g.
row 1: 1, 1+d, 1+2d....
row 2: 2, 2+d, 2+2d....

``````for(i=1;i<=n;i++)
{ for(j=i;j<=n^2;j+=d)
print A[j]
print "\n"
}``````

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

If use a sorting then we have an sorted array for O(n^2 log n), so filling matrix by rows or by columns gets as result a sorted matrix by columns and rows.
But If we know about the range of numbers that it's a sequence then we can get sorted matrix by calculating an row and column indexes by number in the sequence for O(n).

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

in c++ sort with anything and just treat it like a 2-d array. you are done.

if it is fixed in the sense that the values are always 1-n, we can print it in linear time

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

Well, lets imagine that matrix is linear array divided into N equal parts where each part represents row in the matrix. Now imagine that this linear array is sorted and we try to write it to the matrix level by level. If array is sorted it means that if we write it into a matrix level by level then each row in the matrix is sorted and each column is sorted as well. This is because previous level is always closer to the beginning of array and since our array is sorted it means that every element in previous level is less then every element in the next one.
We want to avoid situation with big memory complexity. To do so we can can introduce function that acts as if it would transfered matrix to the linear array and got its ith element. something like

``get(int i, int matrix[][]``

This is useful because using this function we are able to sort array just with any normal sort that uses index access to elements.
This function looks pretty easy actually:

``````//assume that matrix is square
int get(int index, int matrix[][]) {
return matrix[index/matrix.length][index%matrix.length];
}
int get(int index, int matrix[][]) {
return matrix[index/matrix.length][index%matrix.length];
}

int get(int index, int matrix[][]) {
return matrix[index/matrix.length][index%matrix.length];
}

int get(int index, int matrix[][]) {
return matrix[index/matrix.length][index%matrix.length];
}

int set(int index, int matrix[][], int value) {
matrix[index/matrix.length][index%matrix.length] = value;
}``````

using this two functions we can use some O(nlogn) sort. But since we are using O(n) get sorting this array will cost us O(n^2 logn)

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

How about thinking of the n^2 array already as a 2d array. Then, all the code would have to do is execute a single sort on each of the columns (that would be expected O(n^2 log n) if using a QuickSort) and sort each row (that would also be O(n^2 log n) ). Then entire sort would be effectively O(n^2 log n). This would be significantly better than O(n^2 Log n^2).

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

Logn^2 = 2 * Log n. So basically the complexity is the same.

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

The difference between a 10 second and a 5 second application runtime is pretty significant.

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.