Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
I think this is a right solution. My only proposal for improvement not to do straight forward iterating but go by perimeter: top,left to top,right; top,right to bottom,right; bottom,right to bottom,left and, finally, bottom,left to the top,left. Then just decrease each grid dimension by one and continue iterating.
Improvement here is that we stop exactly at the moment we have processed each side of the target minimum rectangular.
I think we can improve the run time by not traversing row wise, but on the borders of the grid. Keep min-i, max-i, min-j, max -j as the four variables (as in 1st comment to this problem) and also maintain flags for them. as soon as all the four variables are modified we are done. Once the exterior most border is traversed move on to one level below and so on. The worst case for this will still be O(n^2).
One more approach:
Lets Find the diagonal co-ordinates of the rectangle. That should be enough to define a rectangle covering all stones.
ALGO: Array M*N
1) Start from (0,0) and move along matrix diagonal.
2) For the first (i,j) if row i or col j contains stone, then (i,j) becomes the first coordinate of the rectangle's diagonal. Stop Here.
3) if row i or col j doesn't contains stone, then set i=i+1 , j=j+1 , GOTO 2)
4) To Find Second coordinate of the rectangle, start from (M-1,N-1), and similar to above, just in this case set i=i-1, j=j-1.
Time Complexity = O(mn)
- niraj.nijju July 01, 2012