## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

int arr[3][3][3]=
{
{
{11, 12, 13},
{14, 15, 16},
{17, 18, 19}
},
{
{21, 22, 23},
{24, 25, 26},
{27, 28, 29}
},
{
{31, 32, 33},
{34, 35, 36},
{37, 38, 39}
},
};

let's look for the element 35

since the array is sorted
1> locate the 2d array with third dimension i such that a[i][0][0]<=key<=a[i][n][n] //complexity O(n)

2> //complexity O(n)
once u have the 2d array, keep the index on top rightmost

and compare with the element go down (row increase) if current number is less than the key

go left(decrease column if the current number is greater than key

total complexity O(n)

eg: for 35

a[2][3][3] is the 2D array where we have to search

since 31 < 35 < 39

apply the 2nd rule...

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

This doesn't work as written. There can easily be more than one dimension i such that a[i][0][0]...a[i][n][n] brackets the key. The simplest case is when a[0][0][0] = a[1][0][0] = ... = a[n][0][0] and a[0][n][n] = a[1][n][n] = ... = a[n][n][n] even though the interior of those slices may be distinct. In that case, you'd be forced to search all the two-dimensional slices based on your algorithm, so it would be O(n^2) total complexity, assuming n^3 is the size of the array.

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

int main()
{
int a[2][3][4] ={
{
{1,2,3,4},
{5,6,7,8},
{9,10,11,12}
},
{
{13,14,15,16},
{17,18,19,20},
{21,22,23,24}
},
};

int i,j,k,found = 0;
int num = 19;
i = 0;
j = 0;
k = 0;
while(i < 2)
{
if(num > a[i][3][4])
i++;
else
break;
}
while(j < 3)
{
if(num > a[i][j][4])
j++;
else
break;
}
for(k = 0; k < 4; k++)
{
if(num == a[i][j][k])
{
found = 1;
printf("found at i=%d\tj=%d\tk=%d\t",i,j,k);
break;
}
}
if(found == 0)
return 0;
}

complexity will < o(n)....o(i) + o(j) + o(k) at max.... can reduce still....

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

I think it is still a binary search. The interviewer just put 3D there to make it looks scary. You need to D&C in 3D.

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

The straightforward divide-and-conquer solution for the two-dimensional problem where you compare to the center element and rule out a quadrant at each step leaves two subproblems of worst-case sizes n/4 and n/2 which leads to total complexity greater than sqrt(n) (which is the complexity of the clever algorithm that starts at the max-min corner and repeatedly walks along either axis). Adapted to the three-dimensional problem, the worst-case split would be something like n/2 and 3n/4, which is even worse. There might be a way to adapt the "max-min" walk, but it seems a lot less simple.

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

The idea is divide the cube into 8 sub-cubes and at each step we exclude a sub-cube based on mid-value of the main cube.
We split the cube into 1/8 and 7/8 at each step. It will be O(lg n) complexity alogrithm.

Code:

``````bool search3D(int arr[], int startX,int endX, int startY, int endY, int startZ, int endZ, int d){

If( startX > endX || startY>endY || startZ > endZ)
return false;

int midX = startX + (endX - startX)/2;
int midY = startY + (endY - startY)/2;
int midZ = startZ + (endZ - startZ)/2;

if( arr[midX][midY][midZ]  ==  d){
return true;
}
else if(arr[midX][midY][midZ] < d){
return search3D(arr, midX, endX, midY, endY, midZ, endZ);
}else{
return
search 3D(arr, startX, midX, startY, midY, startZ, midZ)
|| search 3D(arr, midX, endX, startY, midY, startZ, midZ)
|| search 3D(arr, startX, midX, midY, endY , startZ, midZ)
|| search 3D(arr, midX, endX, midY, endY, startZ, midZ)

|| search 3D(arr, startX, midX, startY, midY, midZ, endZ)
|| search 3D(arr, startX, midX, midY, endY, midZ, endZ)
|| search 3D(arr, midX, endX, startY, midY, midZ, endZ);
}
}``````

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

@abhijeet15oct, if arr[midx][midy][midz] < d, we still eliminate just the 1/8th upper cube, any element in rest 7/8th of matrix can be less than d. Anyway, your solution takes 7^(log(max(x,y,z)) time which is not acceptable. Also if start values are 0 and end values are 1, mids are all 0s and we call functions with same arguments recursively so this is infinite recursion. Stack overflow.

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

Can we

a) divide the 3D array into eight quadrants by dividing it across rows, columns and depth. ( 0->row/2->rows ; 0->column/2->column; 0->depth/2->depth)

b) compare the left top and the right bottom of each quadrant with the key value given. For eg: while the first division it will be between a[0][0][0], a[depth/2][row/2][col/2] ).

c) If the key appears to lie in that quadrant, repeat step1

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

``````#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
int n = 33;
int i, j, k, f = 0;
int ar;
int ar2;
int arr[3][3][3]=
{
{
{11, 12, 13},
{14, 15, 16},
{17, 18, 19}
},
{
{21, 22, 23},
{24, 25, 26},
{27, 28, 29}
},
{
{31, 32, 33},
{34, 35, 36},
{37, 38, 39}
},
};

for(i=0 ; i<3; i++)
{
if(n>=arr[i][0][0])
ar = i;
}

for(j=0;j<3;j++)
{
if(n>=arr[ar][j][0])
ar2 = j;
}

for(k=0;k<3;k++)
{
if(n == arr[ar][ar2][k])
{
f = 1;
}
}

if(f == 1)
cout<<"Found";
else

}

Works in O(n) time

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

The 3D matrix is sorted on each row, column and depth. But in the example you gave, every element in next plane is assumed to be greater than elements of previous plane, which is incorrect. Actually if I take your assumption, I could solve the problem in O(log(n)) time. O(n) is very bad. In O(n) time, I could've checked each and every element in 3D matrix and compared it with the given number.

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

``````#include <iostream>

using namespace std;
int main(int argc, char *argv[]) {
int n = 33;
int i, j, k, f = 0;
int ar;
int ar2;
int arr[3][3][3]=
{
{
{11, 12, 13},
{14, 15, 16},
{17, 18, 19}
},
{
{21, 22, 23},
{24, 25, 26},
{27, 28, 29}
},
{
{31, 32, 33},
{34, 35, 36},
{37, 38, 39}
},
};

for(i=0 ; i<3; i++)
{
if(n>=arr[i][0][0])
ar = i;
}

for(j=0;j<3;j++)
{
if(n>=arr[ar][j][0])
ar2 = j;
}

for(k=0;k<3;k++)
{
if(n == arr[ar][ar2][k])
{
f = 1;
}
}

if(f == 1)
cout<<"Found";
else

}

Works in O(n) time

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

@ psykotic

Sorry i missed that part ..it seems that locating the the 2d array will take O(n)

but it can be improved using Binary search .....(to locate a 2 D array)

but in the worst case when a[0][0][0]=a[0][n][n]=a[1][0][0]=a[1][n][n]......=a[n][n][n]

Then the complexity will be O(n^2) .... can we do better in this worse case ??

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

@ psykotic

Sorry i missed that part ..it seems that locating the the 2d array will take O(n)

but it can be improved using Binary search .....(to locate a 2 D array)

but in the worst case when a[0][0][0]=a[0][n][n]=a[1][0][0]=a[1][n][n]......=a[n][n][n]

Then the complexity will be O(n^2) .... can we do better in this worse case ??

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

@ psykotic

Sorry i missed that part ..it seems that locating the the 2d array will take O(n)

but it can be improved using Binary search .....(to locate a 2 D array)

but in the worst case when a[0][0][0]=a[0][n][n]=a[1][0][0]=a[1][n][n]......=a[n][n][n]

Then the complexity will be O(n^2) .... can we do better in this worse case ??

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

I think we dont need to bother about whether the array is 3D or 2D. Create an int *p and store the address of the first element of the array a[0][0][0]. Then, since all the elements are in contiguous locations lets say the total size of the array is n, we simple need to add n/2 to the address of *p and compare. Then with simple D&C, it can be solved.

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

when the row and column are sorted then u r method won't work
for eg
1 4 7 12
2 6 8 13
3 9 10 15
5 11 14 16

it works only when matrix is sorted for eg

1 2 3 4
5 6 7 8
9 10 11 12

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

It can be done in Log(n) time .... where n = n1*n2*n3 ( total number of elements).. just treat this as a binary search on one dimensional array. where the actual index in the array should be computed as..
i1 = ( i ) / ( N2 *N3)
i2 = [ (i) % ( N2 * N3)]/N2
i3 = [ i ] % N3

below is the implementation in Java....

import java.util.Scanner;

public class ThreeDimensionalMatrix {

/**
* @param args
*/

public static int binarySearch(int arr[][][],int startI, int lastI,int num,int N1,int N2,int N3){

if ( startI == lastI){
if ( arr[(startI/(N2*N3))][(startI%(N2*N3))/N2][startI%N3] == num){
return startI;
}else {
return -1;
}
}else{
int midI = (startI+lastI)/2;
int test = arr[(midI/(N2*N3))][(midI%(N2*N3))/N2][midI%N3];
if ( test == num){
return midI;
}else if ( test > num){
return binarySearch(arr, startI, midI, num, N1, N2, N3);
}else{
return binarySearch(arr, midI+1, lastI, num, N1, N2, N3);
}

}
}
public static void main(String[] args) {

Scanner scan = new Scanner(System.in);
int N1 = scan.nextInt();
int N2 = scan.nextInt();
int N3 = scan.nextInt();
int arr[][][] = new int[N1][N2][N3];
for ( int i=0;i < N1;i++){
for (int j=0; j<N2;j++){
for ( int k=0; k < N3;k++){
arr[i][j][k] = scan.nextInt();
}
}
}

int temp;
while ( (temp = scan.nextInt()) >=0){
if( (temp =binarySearch(arr,0,N1*N2*N3,temp,N1,N2,N3)) >-1){
System.out.println("i = "+(temp/(N2*N3))+" j = "+( (temp%(N2*N3))/N2)+" k = "+(temp%N3));
}else{
}
}
}

}

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

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SearchIn3DArray
{
class point
{
public int i, j, k;
public point(int a, int b, int c)
{
i = a;
j = b;
k = c;
}
}

class Program
{
static void search3DArray(int[, ,] A, int l, int m, int n, int k)
{
Queue<point> Q = new Queue<point>();
bool flag = false;

point p = new point(l - 1, m - 1, 0);
Q.Enqueue(p);

while (Q.Count > 0 && flag == false)
{
p = Q.Dequeue();

if (A[p.i, p.j, p.k] == k)
{
flag = true;
Console.WriteLine(" Found at [i,j,k]= [" + p.i + ", " + p.j + ", " + p.k + "]" + ": " + A[p.i, p.j, p.k]);
}
else if (A[p.i, p.j, p.k] < k)
{
if (p.k + 1 < n)
{
Q.Enqueue(new point(p.i, p.j, p.k + 1));
}
}
else
{
if (p.i - 1 >= 0)
{
Q.Enqueue(new point(p.i - 1, p.j, p.k));
}
if (p.j - 1 >= 0)
{
Q.Enqueue(new point(p.i, p.j - 1, p.k));
}
}
}
if (flag == false)
}

static void Main(string[] args)
{
int[, ,] A = new int[,,]{
{
{1, 6, 12},
{4, 9, 15},
{7, 13, 18}
} ,
{
{2, 7 ,14},
{5, 10, 16},
{8, 17, 20}
},
{
{3, 11, 19},
{21, 25, 30},
{22, 26, 31}
}

};
search3DArray(A, 3, 3, 3, 20);
}
}
}``````

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

I think it can be done in worst case O(n+ logn) time.
In the 3rd dimension,
Choose the middle layer,now check if the element to be searched is in the range of this layer. key >= a[i][0][0] && key <= a[i][n][n]
then search this layer in O(n) time -- standard Young tableau search
else if key < a[i][0][0]
go to previous layer
else
go to next layer
the layer search works in a binary seach fashion -- O(logn)

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

a[i][j][k] is nothing but an array of i*j*k contiguous elements. So you have an array of i*j*k elements and you have to search for an element. Simple binary search - O(log n)

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.