## Amazon Interview Question for SDE-2s

Country: India
Interview Type: Written Test

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

Sort the matrix first as if it were a regular array. That is, for an MxN matrix treat it as a sequential, linear array of M*N elements and sort it using a known sorting algorithm.

Then, swap the first row with the last, the second row with the second to last, the third row with the third to last, etc.

This is O(MN log(MN)) as it is bounded by the initial sorting. No additional memory is used so space complexity is O(1). I believe you can't achieve better than these bounds.

``````#include <stdio.h>

static void swap(int arr[], size_t i, size_t j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

static void swap_arrays(int arr1[], int arr2[], size_t sz) {
size_t i;
for (i = 0; i < sz; i++) {
int tmp = arr1[i];
arr1[i] = arr2[i];
arr2[i] = tmp;
}
}

static void quicksort(int arr[], size_t sz) {
if (sz <= 1) {
return;
}

swap(arr, 0, sz/2);

size_t i, j;
i = 0;
for (j = i+1; j < sz; j++) {
if (arr[j] <= arr[0]) {
i++;
swap(arr, i, j);
}
}

swap(arr, 0, i);
quicksort(arr, i);
quicksort(arr+i+1, sz-(i+1));
}

void matrix_mostly_sorted(size_t rows, size_t cols, int matrix[rows][cols]) {
quicksort(&matrix[0][0], rows*cols);
size_t i;
for (i = 0; i < rows/2; i++) {
swap_arrays(&matrix[i][0], &matrix[rows-(i+1)][0], cols);
}
}

static void print_matrix(size_t rows, size_t cols, int matrix[rows][cols]) {
size_t i, j;
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
printf("%d\t", matrix[i][j]);
}
putchar('\n');
}
}

int main(void) {
printf("Enter matrix dimensions followed by the elements\n");
printf("> ");

size_t rows, cols;
while (scanf("%zu%zu", &rows, &cols) == 2) {
int matrix[rows][cols];
size_t i, j;
for (i = 0; i < rows; i++) {
for (j = 0; j < cols; j++) {
scanf("%d", &matrix[i][j]);
}
}

matrix_mostly_sorted(rows, cols, matrix);

print_matrix(rows, cols, matrix);
printf("> ");
}

return 0;
}``````

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

Nicely done!

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

I think we would need 2 passes
one pass for sorting rows in ascending order
and one pass for sorting columns in descending order
Example Case:
1, 9, 10
4, 5, 6
7, 8, 11

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

The key observation should be that the transpose of such a matrix would have both its rows and columns in increasing order. So a simpler algorithm would be :

``````1. Create a min heap with all the elements of the matrix: O(MN)
2. Fill the matrix diagonally.
3. Return the transpose of the matrix.``````

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

Define a shim/API on top of the matrix such that someone can use a single index to treat the elements of matrix as a one dimensional object.

i.e.,

Some map like:
arr(k) = matrix[i][j]

Then sort arr(k) using a regular sorting function.

Now which mapping from k to (i,j) would give the intended result?

We want the matrix to end up being sorted like this, for example with 3x4 matrix, (1, 2, 3, just refer to the order of increasing elements:

13 14 15 16
9 10 11 12
5 6 7 8
1 2 3 4

So the mapping would have to be something like this (assume k, i,j are 0 indexed):

arr(k) = matrix[ k%num_col ][ num_row - (k / num_col) - 1]

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

c++

``````#include<iostream>

const int m=3, n = 3;
int arr[m][n] = { {4,3,23},
{2 , 11, 34},
{22, 54, 32}
};

void dump_arr() {
for ( int i = 0 ; i < m  ; i++) {
for ( int j = 0 ; j < n  ; j++) {
std::cout << arr[i][j] <<" ";
}
std::cout<< "\n";
}
}
void swap( int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}

int main() {
std::cout << "  Original array : " <<std::endl;
dump_arr();
for ( int i = 0 ; i < m ; i++) {
for (int j =0 ; j < n-1 ; j++) {
for ( int k = j+1; k < n ; k++) {
if (arr[i][j] > arr[i][k] ) {
swap ( arr[i][j], arr[i][k]);
}
}
}
}
std::cout << " Rows sorted in ascending order" << std::endl;
dump_arr();

for (int i = 0 ; i < n; i++) {
for ( int j = 0 ; j < m-1 ; j++) {
for ( int k= j+1; k < m ; k++){
if (arr[j][i] < arr[k][i]) {
swap(arr[j][i], arr[k][i]);
}
}
}
}
std::cout << " Columns sorted in descending order" << std::endl;
dump_arr();
}``````

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

I think we would need 2 passes
1 pass to sort all rows in ascending order
and second pass to sort all columns in descending order

Example case:
1, 9, 10
4, 5, 6
7, 8, 11

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

There are cases where just sorting the rows won't be enough.
Example Case:
1, 9, 10
4, 5, 6
7, 8, 11

and

1, 2, 3
7, 8, 11
4, 5, 6

So if we first sort rows in ascending order
then sort columns in ascending order
and then flip the matrix

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

#include<iostream>
using namespace std;

int a[100],l,u,i,j;
void quick(int a[],int l,int u)
{
int p,temp;
if(l<u)
{
p=a[l];
i=l;
j=u;
while(i<j)
{
while(a[i] <= p && i<j )
i++;
while(a[j]>p && i<=j )
j--;
if(i<=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;}
}
temp=a[j];
a[j]=a[l];
a[l]=temp;
quick(a,l,j-1);
quick(a,j+1,u);
}
}

int main()
{
int b[15][15],i,j,m,n,k,x;
k=0;
cout<<"Enter number of rows and columns"<<endl;
cin>>m>>n;
cout<<"Enter the elements"<<endl;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
cin>>b[i][j];
a[k++]=b[i][j];
}
quick(a,0,k-1);
k=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
b[i][j]=a[k++];
}
for(j=0;j<n;j++)
for(i=0;i<m/2;i++)
{
x=b[i][j];
b[i][j]=b[m-1-i][j];
b[m-1-i][j]=x;
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
cout<<b[i][j]<<"\t";
cout<<endl;
}
return 0;
}

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

#include<iostream>
using namespace std;

int a[100],l,u,i,j;
void quick(int a[],int l,int u)
{
int p,temp;
if(l<u)
{
p=a[l];
i=l;
j=u;
while(i<j)
{
while(a[i] <= p && i<j )
i++;
while(a[j]>p && i<=j )
j--;
if(i<=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;}
}
temp=a[j];
a[j]=a[l];
a[l]=temp;
quick(a,l,j-1);
quick(a,j+1,u);
}
}

int main()
{
int b[15][15],i,j,m,n,k,x;
k=0;
cout<<"Enter number of rows and columns"<<endl;
cin>>m>>n;
cout<<"Enter the elements"<<endl;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
cin>>b[i][j];
a[k++]=b[i][j];
}
quick(a,0,k-1);
k=0;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
b[i][j]=a[k++];
}
for(j=0;j<n;j++)
for(i=0;i<m/2;i++)
{
x=b[i][j];
b[i][j]=b[m-1-i][j];
b[m-1-i][j]=x;
}
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
cout<<b[i][j]<<"\t";
cout<<endl;
}
return 0;
}

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

Suppose we have
1 2 3
4 5 6
7 8 9

o/p
7 8 9
4 5 6
1 2 3

1. First sort array in ascending order
2. Start picking up set of n (n is dimension)
3. Put these set row wise into matrix

Complexity - nlogn - to sort array + n filling matrix
Final - nlogn

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

``````//============================================================================
// Name        : MatrixSorting.cpp
// Author      : Nitish Raj, scientist DRDO
// Version     :
// Description :  Ansi-style
//============================================================================

#include <iostream>
using namespace std;

class Matrix
{
int r , c;
int arr[10][10];
int arrTmp[20],count;
public:
Matrix()
{}
void getArrayInput();
void makeLinearArray();
void sortSelection();
void rowWiseSwap();
void printMatrix();

};

void Matrix::getArrayInput(){

cout<<"Enter size of ROW"<<endl;
cin>>r;
cout<<"Enter szie of COL"<<endl;
cin>>c;

for(int i = 0 ; i<r ;i ++)
for(int j = 0 ; j< c ; j++)
{
cout<<" ["<<i<<"]["<<j<<"]  = ";
cin>>arr[i][j];
}

}

void Matrix::printMatrix(){

for(int i = 0 ;i< r ; i++)
{
for(int j = 0; j<c;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}

}
void Matrix::makeLinearArray(){
count = 0;
for(int i = 0 ;i< r ; i++)
for(int j = 0; j<c;j++)
{
arrTmp[count] = arr[i][j];
count++;
}
}

void Matrix::sortSelection(){
for(int k = 1; k <r*c ; k++){
int data = arrTmp[k];
int j = k-1;
while(j>=0 && arrTmp[j]>data)
{
arrTmp[j+1] = arrTmp[j];
j--;
}
arrTmp[j+1] = data;
}

count = 0;
for(int i = 0 ;i< r ; i++)
for(int j = 0; j<c;j++)
{
arr[i][j] = arrTmp[count];
count++;
}

}
void Matrix::rowWiseSwap(){
for(int i = 0 ;i< r/2 ; i++)
{
for(int j = 0; j<c;j++)
{
int tmp = arr[i][j];
arr[i][j] = arr[r-i-1][j];
arr[r-i-1][j] = tmp;

}
}

}

int main() {

Matrix obj;
obj.getArrayInput();
obj.makeLinearArray();
obj.sortSelection();
obj.rowWiseSwap();
obj.printMatrix();

return 0;
}``````

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

``````//============================================================================
// Name        : MatrixSorting.cpp
// Author      : Nitish Raj, scientist DRDO
// Version     :
// Description :  Ansi-style
//============================================================================

#include <iostream>
using namespace std;

class Matrix
{
int r , c;
int arr[10][10];
int arrTmp[20],count;
public:
Matrix()
{}
void getArrayInput();
void makeLinearArray();
void sortSelection();
void rowWiseSwap();
void printMatrix();

};

void Matrix::getArrayInput(){

cout<<"Enter size of ROW"<<endl;
cin>>r;
cout<<"Enter szie of COL"<<endl;
cin>>c;

for(int i = 0 ; i<r ;i ++)
for(int j = 0 ; j< c ; j++)
{
cout<<" ["<<i<<"]["<<j<<"]  = ";
cin>>arr[i][j];
}

}

void Matrix::printMatrix(){

for(int i = 0 ;i< r ; i++)
{
for(int j = 0; j<c;j++)
cout<<arr[i][j]<<" ";
cout<<endl;
}

}
void Matrix::makeLinearArray(){
count = 0;
for(int i = 0 ;i< r ; i++)
for(int j = 0; j<c;j++)
{
arrTmp[count] = arr[i][j];
count++;
}
}

void Matrix::sortSelection(){
for(int k = 1; k <r*c ; k++){
int data = arrTmp[k];
int j = k-1;
while(j>=0 && arrTmp[j]>data)
{
arrTmp[j+1] = arrTmp[j];
j--;
}
arrTmp[j+1] = data;
}

count = 0;
for(int i = 0 ;i< r ; i++)
for(int j = 0; j<c;j++)
{
arr[i][j] = arrTmp[count];
count++;
}

}
void Matrix::rowWiseSwap(){
for(int i = 0 ;i< r/2 ; i++)
{
for(int j = 0; j<c;j++)
{
int tmp = arr[i][j];
arr[i][j] = arr[r-i-1][j];
arr[r-i-1][j] = tmp;

}
}

}

int main() {

Matrix obj;
obj.getArrayInput();
obj.makeLinearArray();
obj.sortSelection();
obj.rowWiseSwap();
obj.printMatrix();

return 0;
}``````

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

``````void sortMatrix(int* matrix, int row, int col) {
std::qsort(matrix, row*col, sizeof(int), [](const void *left, const void *right) -> int {
int *i = (int*)left;
int *j = (int*)right;
return (*j - *i);
});
std::qsort(matrix, row, sizeof(int)*col, [](const void *left, const void *right) -> int {
return ((*(int*)left) - (*(int*)right));
});
}

int main()
{
int matrix[][4] = {
{ 3, 2, 5, 11 },
{ 6, 8, 7, 1 },
{ 4, 10, 9, 12 }
};

sortMatrix(&matrix[0][0], 3, 4);

for (int r = 0; r < 3; ++r) {
for (int c = 0; c < 4; ++c) {
cout << matrix[r][c] << " ";
}
cout << endl;
}
return 0;
}``````

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

``````#include <stdio.h>

void main(){

int array1[10][10], array2[10][10];
int i, j, k, a, m, n;

scanf("%d %d", &m, &n);

for (i = 0; i < m; ++i){

for (j = 0; j < n; ++j){

scanf("%d", &array1[i][j]);
array2[i][j] = array1[i][j];

}
}

//Arranging rows in ascending order
for (i = 0; i < m; ++i){

for (j = 0; j < n; ++j){

for (k =(j + 1); k < n; ++k){

if (array1[i][j] > array1[i][k]){

a = array1[i][j];
array1[i][j] = array1[i][k];
array1[i][k] = a;

}

}

}

}

//Arranging the columns in descending order

for (j = 0; j < n; ++j){

for (i = 0; i < m; ++i){

for (k = i + 1; k < m; ++k){

if (array2[i][j] < array2[k][j]){

a = array2[i][j];
array2[i][j] = array2[k][j];
array2[k][j] = a;

}

}

}

}``````

}

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

I believe the idea is to do it in the same matrix. Also this won't scale, the running time is too bad.

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.