Amazon Interview Question
Applications DevelopersCountry: United States
There must be some catch in this question. Is there any time complexity expectation? The simplest would be of O(m*n) complexity.
Algorithm would be:
- Find first row from _top_ which has at least one column in that row as '1'
- Find first row from _bottom_ which has at least one column in that row as '1'
The difference of the above row numbers + 1 is height of the character.
Thanks,
Laxmi
I think this can be solved in n*log(m)
- From top search for 1 in each row till first occurance using binary search
- Once you find that, perform same from bottom
Difference between row nums + 1 is your required height
I am assuming that the question can be interpreted as a MXN grid with 1 in each cell where the character's part lies, 0 otherwise. Assuming that the character dots will be connected, it means all the cells numbered 1 will be connected. We need to figure out the maximum extent of the connected cells.
Approach
Travel in the diagonal direction, till you hit a cell with value 1. If you do not hit any cell with 1, then either half of the matrix does not contain any character and hence the cells to be tested will be reduced(not necessarily halved).
Once you get one cell having value 1, you can start that as a seed and do a traversal of the connected cells keeping an eye on the yMin and yMax of the visited cells.
I cant understand the question. Anyone pls explain.
- pradeep December 12, 2012