Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
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.
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)
printf("not found ");
return 0;
}
complexity will < o(n)....o(i) + o(j) + o(k) at max.... can reduce still....
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.
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.
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);
}
}
@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.
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
d) Else discard the quadrant.
#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
cout<<"Not Found";
}
Works in O(n) time
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.
#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
cout<<"Not Found";
}
Works in O(n) time
@ 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 ??
@ 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 ??
@ 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 ??
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.
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{
System.out.println("element not found");
}
}
}
}
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)
Console.WriteLine("Element not found");
Console.ReadLine();
}
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);
}
}
}
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)
int arr[3][3][3]=
- Gautam February 12, 2012{
{
{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...