Amazon Interview Question
Country: India
Nice question. An algorithm to solve it goes like below.
0. Start at any corner, say top left.
1. Keep traversing along the diagonal from (0,j) to (j,0), where 0<=j<=N-1, until you hit a 1. If the upper left of the matrix is exhausted, keep traversing along the diagonal (i,N-1) to (N-1,i), where 1<=i<=N-1. Traversing the diagonal helps in hitting the vertex first, rather than a side of a square/rectangle.
2. if you hit a 1. start 2 pointers - one moving horizontally to the right and the other vertically down. Advance these pointers one step at a time as long as 1s are seen. and maintain in 'ones_count' variable, the count of 1s seen. If any one of them encounters a 0, go to step 1. If both of them hit 0s go to step 3
.
3. 'Transpose' the directions of pointers so the pointer that was moving horizontally to the right moves vertically down and vice-versa. Keep advancing the pointers one step at a time until 'ones_count' number of 1s are seen, which means we have found a square, or otherwise 0s are encountered in which case, go to step 1
Similar idea can be applied to find rectangles as well. Minor modifications may be needed to separately keep track of the number of 1s seen in horizontal and vertical directions. Also the condition to stop advancing the pointers would be different here.
@Ayahuasca
Hey nice. First of all a quick check: this is a O(N^3) solution, right? O(N^2) spent on the traversal on diagonals and O(N) on checking the validity of the square, right?
Second, why take diagonal traversal? Why cannot we just pick a pair (row, col), use it as one corner of the square, then check if the square is valid for a given size? This also takes O(N^3) time (and this is (20.11) in cracking the coding interview). Is there any benefits gained from the diagonal search? Thanks.
@ Chih.Chiu.19
1. No. It's an O(N^2) algorithm. each element of the matrix is traversed at most thrice.
2. Diagonal traversal helps to encounter a vertex first rather than a side of a square/rectangle . Once you are at a vertex, you will know how to proceed from there.
Take as examples the following 3x3 matrices. The algorithm starting at top left (0,0) and traversing the diagonals will better be able to figure out the top left vertex of a square/rectangle and then proceed to figure out the rest of the geometric object.
0 0 0 0 1 1 0 0 0
0 1 1 0 1 1 1 1 0
0 1 1 0 0 0 1 1 0
For that matter, you can start at any of the four corners and then do a diagonal traversal to hit the vertex of the geometric object. From there you can proceed in horizontal and vertical directions to figure out the rest of it.
@Akbar-The-Emperor
Thanks. Just to be sure, you consider the matrix to be N by N, right? Then the algorithm is O(N^3), since you are enumerating all the elements of the matrix and for each (i,j) value and you check the sides of the square.
As for the diagonal traversal, I still think it does not save much time; in fact the column scan algorithm given as the solution to problem (20.11) in Craking the Coding Interview looks fine to me, and I do not see how using diagonal traversal will help to make the code any faster or cleaner. Care to elaborate a bit more? :)
@Apostle:
"1. No. It's an O(N^2) algorithm. each element of the matrix is traversed at most thrice."
I agree with Chih.Chiu.19. It seems to be O(N^3) by your explanation. What happens with your algorithm on an NxN matrix filled all with 1?
While doing the diagonal parsing (looking for corners) what happens after you have processed a corner? Continue parsing the diagonal or maybe you skip the whole diagonal? (otherwise I don't see how your algorithm runs in less than O(N^3)).
@cristian.botau
If the matrix happens to have all 1s, we start at the top-left corner and then the algorithm traverses along the 4 edges of the matrix, finds a square and quits. In this particular traversal, you will traverse 4n-4 elements and that is the maximum- sized square you can find in an NxN matrix. The question is asking us to find "a" square and we quit after seeing the first square.
Coming to the argument of each element being traversed at most thrice, the traversal mechanism I have mentioned will encounter a particular element at most thrice- first during the diagonal traversal and consecutively during either or both of horizontal traversal to the right and vertical traversal to the down.
Chih.Chiu.19 is confused and is talking about a completely different problem from "Cracking the coding Interview"book, where it is an "optimization" problem asking to find a square with 'maximum' size, whose solution provided in that book uses DP and is of the order O(N^3).
The problem here is asking just to find any square, whereas the problem mentioned by Chih.Chiu.19 is an optimization problem - its a big difference!
- tarun July 22, 2013#include "stdio.h" #define ROW 3 #define COL 3 int a[ROW][COL] = { {1,1,1}, {1,0,1}, {1,1,1} }; int findSquare(int x, int y, int len) { int i=0,j=0,failure = 0; for (i=0;i<len;i++) { if((a[x][y+i] != 1)||(a[x+len-1][y+i] != 1)) { failure = 1; break; } } if(!failure) { for(j=1;j<len-2;j++) { if((a[x+j][y]!=1) ||(a[x+j][y+len-1]!=1)) { failure = 1; break; } } } if(!failure) { for(i=1;i<len-1;i++) { for(j=1;j<len-1;j++) { if(0 != a[x+i][y+j]) { failure = 1; break; } } } } return (!failure); } void printSquare(int x,int y, int len) { int i,j; for(i=0;i<len;i++) { for(j=0;j<len;j++) { printf("%d ",a[x+i][y+j]); } printf("\n"); } } int main() { int length = 0,i,j,success = 0; for (i=0;i<ROW-2;i++) { length = 2; for(j=0;j<COL-2;j++) { while((COL >= j+length) && (ROW >= i+length)) { if(!findSquare(i,j,length)) { length++; } else { printSquare(i,j,length); success = 1; break; } } if(success)break; } if(success)break; } return 0; }