Amazon Interview Question SDE-2s
Country: India
Interview Type: Written Test
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
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.
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]
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();
}
#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;
}
#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;
}
//============================================================================
// Name : MatrixSorting.cpp
// Author : Nitish Raj, scientist DRDO
// Version :
// Copyright : Your copyright notice
// 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;
}
//============================================================================
// Name : MatrixSorting.cpp
// Author : Nitish Raj, scientist DRDO
// Version :
// Copyright : Your copyright notice
// 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;
}
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;
}
#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;
}
}
}
}
}
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.
- 010010.bin July 05, 2015#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; }