Amazon Interview Question
Computer ScientistsCountry: United States
Interview Type: Written Test
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)).
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;
}
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"
}
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).
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)
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).
Note that a standard sorting algorithm can do what you want.
- themonk September 15, 2014You 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.