## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

``````void UniqueInt(int **A, int R, int C)
{
int ROW[R], COL[C];
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
if(ROW[i] < A[i][j]){
ROW[i] = A[i][j];
ROW[i] = j;
}
if(COL[j] > A[i][j]){
COL[j] = A[i][j];
COL[j] = i;
}
}
}
if(R<C){
for(int i=0; i<R; i++){
if(ROW[i] == COL[ROW[i]])
cout << A[i][ROW[i]];
}
} else {
for(int i=0; i<C; i++){
if(COL[i] == ROW[COL[i]])
cout << A[COL[i]][i];
}
}``````

T(N) = Size of MATRIX, i.e. MXN.
S(N) = 2*M + 2*N.

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

I was trying to create test cases manually and I couldnt create a matrix with more than one such number in MxN matrix due to the cyclic dependency. so it possible to create a matrix with more than one such values? if yes how?

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

Find the max number in each row and the min num in each column
Now for every position compare with row max and col min and then print if it is.

O(N+N)

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

``````for(int i = 0; i < N ; i++)
{
for(int j =0; j < M ; j++)
{
if(row[i] > arr[i][j])
row[i] = arr[i][j];

if(col[j] < arr[i][j])
col[j] = arr[i][j];
}
}

for (int k = 0 ; k < N ; k++)
if(row[k] == col[k])
{
// got position
}

2 3 4 5
4 5 6 7
1 2 3 0
9 8 7 6

row[] = 3, 3, 2, 0
col[] = 2, 2, 2, 2``````

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

First, the complexity is O(N^2) not O(N + N)
Second, the function is not quite correct because the largest number in the ith row is not necessarily the smallest number in the ith column. For example, in the following matrix,
1 2 3
4 5 6
7 8 9
the largest number in the first row is not the smallest number in the first column, but the smallest number in the third column.

Third, the two comparisons in the first nested loop is not quite correct. I think the signs should be reversed. i.e., < should be > and > should be <.

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

Problem statement says: The biggest in its row and also the smallest in ITs column
so if we take below matrix:
1 2 3
4 5 6
7 8 9

then 3 is biggest in its ROW(i.e 1st row) and smallest in its COLUMN(i.e 3rd column)

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

The code above only compares row[i] with column[i], which I don't think is correct.

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

``````//C#
static void display(int[,] _arr)
{
int[] smallestOfColumn = new int[_arr.GetLength(1)];
int[] smallestOfColumni = new int[_arr.GetLength(1)];
int[] smallestOfColumnj = new int[_arr.GetLength(1)];
for (int i = 0; i < _arr.GetLength(0); i++)
{
int biggestOfRow = _arr[i, 0];
int biggestOfRowi = i;
int biggestOfRowj = 0;
for (int j = 0; j < _arr.GetLength(1); j++)
{
if (biggestOfRow < _arr[i, j])
{
biggestOfRow = _arr[i, j];
biggestOfRowi = i;
biggestOfRowj = j;
}
if (i == 0)
{
smallestOfColumn[j] = _arr[i, j];
smallestOfColumni[j] = i;
smallestOfColumnj[j] = j;
}
if (smallestOfColumn[j] > _arr[i, j])
{
smallestOfColumn[j] = _arr[i, j];
smallestOfColumni[j] = i;
smallestOfColumnj[j] = j;
}
}
Console.WriteLine("Biggest of row " + (i + 1) + " is " + biggestOfRow + " at row " + (biggestOfRowi + 1) + " and column " + (biggestOfRowj + 1));
}
for (int j = 0; j < _arr.GetLength(1); j++)
{
Console.WriteLine("Smallest of column " + (j + 1) + " is " + smallestOfColumn[j] + " at row " + (smallestOfColumni[j] + 1) + " and column " + (smallestOfColumnj[j] + 1));
}
}``````

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

package com.algorithms;

public class MatrixMaxMinRowCol {
public static void main(String[] args){
int[][] a = {
{9,2,3,18},
{4,5,6,23},
{1,8,9,5}
};
int ROWS = 3;
int COLS = 4;

for ( int i = 0; i < ROWS; i++){
int biggest = a[i];
int smallest = a[i];
int bigPos = 0;
int smallPos = 0;
for ( int j = 0; j < COLS; j++){
if ( a[i][j] > biggest){
biggest = a[i][j];
bigPos = j;
}
if ( j < ROWS ){
if ( a[j][i] < smallest ){
smallest = a[j][i];
smallPos = j;
}
}
}
System.out.println("Biggest in row "+(i+1)+" is :"+biggest+" Pos is : "+bigPos);
System.out.println("Smallest in col "+(i+1)+" is :"+smallest+" Pos is :"+smallPos);
}
for ( int i = ROWS; i < COLS; i++){
int smallest = a[i];
int smallPos = 0;
for ( int j = 0; j < ROWS; j++){
if ( a[j][i] < smallest ){
smallest = a[j][i];
smallPos = j;

}
}
System.out.println("Smallest in col "+(i+1)+" is : "+smallest+" Pos is : "+smallPos);
}
}
}
Output:

Biggest in row 1 is :18 Pos is : 3
Smallest in col 1 is :1 Pos is :2
Biggest in row 2 is :23 Pos is : 3
Smallest in col 2 is :2 Pos is :0
Biggest in row 3 is :9 Pos is : 2
Smallest in col 3 is :3 Pos is :0
Smallest in col 4 is : 5 Pos is : 2

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

It should satisfy both requirements: largest in each row and smallest in that column.

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

Could you please correct me, what was the problem ? I hope it has taken care.

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

it says printing out those numbers who is the largest in its row and at the same time the smallest in its column, not largest ones in each row and smallest ones in each column

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

Thanks you, understood.

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

C++

``````void find(int N, vector<vector<int> >& matrix)
{
vector<int> largestEachRow(N);
vector<int> smallestEachColumn(N);
for(int i = 0; i < N; i++) {
smallestEachColumn[i] = numeric_limits<int>::max();
}
for(int i = 0; i < N; i++) {
int largest = 0;
for(int j = 0; j < N; j++) {
if(matrix[i][j] > matrix[j][largest]) {
// records the position of the largest integer in each row
largest = j;
}
if(matrix[i][j] < smallestEachColumn[j]) {
smallestEachColumn[j] = matrix[i][j];
}
}
largestEachRow[i] = largest;
}
cout << "The qualified integers are at: \n";
for(int i = 0; i < N; i++) {
if(matrix[i][largestEachRow[i]] ==
smallestEachColumn[larestEachRow[i]]) {
cout << "row: " << i << " column: " << largestEachRow[i] << endl;
}
}
}``````

Time complexity O(N^2). Can't do better because integers are not sorted, to find out the largest integer in each row we must inspect every integer in each row.

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

just realized that we need to output the positions of elements, not their values.

``````var m  = [
[1,4,7],
[2,5,8],
[3,6,9]
];

var rows = m.length;
var cols = m.length;

var maxColumnsInRows = []; // index = row num, value: col num
var minRowsInColumns = [];

for(var i=0; i<rows;i++){
maxColumnsInRows[i] = 0;
minRowsInColumns[i] = 0;
}

for(var ri=0;ri<rows;ri++){
for(var ci=0; ci<cols;ci++){
var currentRowMaxColumn = maxColumnsInRows[ri];
var currentColumnMinRow = minRowsInColumns[ci];
var currentValue = m[ri][ci];
if(currentValue > m[ri][currentRowMaxColumn])
maxColumnsInRows[ri] = ci;
if(currentValue < m[currentColumnMinRow][ci])
minRowsInColumns[ci] = ri;
}
}

for(ri=0; ri<rows;ri++){
var maxCol = maxColumnsInRows[ri];
var minRow = minRowsInColumns[maxCol];
if(ri == minRow){
console.log('row: ' + ri +' ,col: ' + maxCol);
}
}``````

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

Find max number in a row. Check if it's min in column.

``````public void printBiggestInRowSmallestInColumn(int[][] arr) {
for (int i = 0; i < arr.length; i++) {

int maxInRow = Integer.MIN_VALUE;
int maxInRowInd = -1;
for (int j = 0; j < arr.length; j++) {
if (maxInRow < arr[i][j]) {
maxInRow = arr[i][j];
maxInRowInd = j;
}
}

int minInCol = Integer.MAX_VALUE;
int minInColInd = -1;
for (int j = 0; j < arr.length; j++) {
if (minInCol > arr[j][maxInRowInd]) {
minInCol = arr[j][maxInRowInd];
minInColInd = j;
}
}

if (minInColInd == i) {
System.out.println("[" + i + "," + maxInRowInd + "]="
+ arr[i][maxInRowInd]);
}
}
}``````

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

#define ROW 3
#define COL 4
int main()
{
int arr[][COL]={{9,2,3,18},
{4,5,6,23},
{1,8,9,5}};
int max=0,min=999;
int *row=(int *)malloc(sizeof(int)*ROW);
int *col=(int *)malloc(sizeof(int)*COL);
int row_index=0,col_index=0;
for(int i=0;i<ROW;i++)
{
for(int j=0;j<COL;j++)
{
if(arr[i][j]>max)
{
max=arr[i][j];
row[row_index]=j;
}
}
max=0;
row_index++;
}
for(int i=0;i<COL;i++)
{
for(int j=0;j<ROW;j++)
{
if(arr[j][i]<min)
{
min=arr[j][i];
col[col_index]=j;
}
}
min=999;
col_index++;
}
for(int i=0;i<ROW;i++)
printf("%d ",row[i]);
printf("\n");
for(int i=0;i<COL;i++)
printf("%d ",col[i]);
getchar();
return 0;
}

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

I feel like there must be an interesting trick here with the stipulation in the problem statement that they are unique numbers and it's a square matrix, but I'm failing to think of one. Probably because my linear algebra skills are forgotten.

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

``````public void printCyclic(int[][] table, int iMax, int jMax){ //O(m*n)?
int iMin = 0, jMin = 0; //outer scope of min,max
iMax--; jMax--;
while((iMin <= iMax)|| (jMin <= jMax)){ // Terminate Condition
for(int j = iMin; j<=jMax; j++){
System.out.print(table[iMin][j]);
}iMin++;
for(int i = iMin; i<=iMax; i++){
System.out.print(table[i][jMax]);
}jMax--;
for(int j = jMax; j>=jMin; j--){
System.out.print(table[iMax][j]);
}iMax--;
for(int i = iMax; i>=iMin; i--){
System.out.print(table[i][jMin]);
}jMin++;
}
}``````

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

``````public void findRowMaxColMin(int[][] table, int iMax, int jMax){
int[] colMins = new int[jMax];
Map<Integer, Integer> rowMaxs = new HashMap<Integer, Integer>();
for(int i =0; i<iMax; i++){
int rowMax = 0;
for(int j =0; j<jMax; j++){
if(j == 0)rowMax = table[i];
else{
if(table[i][j] > rowMax)
rowMax = table[i][j]; // update max
}
if(i == 0) colMins[j] = table[j];
else{
if(colMins[j] < table[i][j])
colMins[j] = table[i][j]; //update min
}
}
rowMaxs.put(rowMax, i);	//put the rowMax as elements are unique
}
for(int j = 0; j < jMax; j++){
if(null != rowMaxs.get(colMins[j])){
System.out.println("Element: "+colMins[j]+" Row: "+ rowMaxs.get(colMins[j])+ " Col:"+ j );
}
}//O(n*m), extra space = array[col] and map<int, int>(row)
}``````

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.