Interview Question

Interview San Francisco, CA

given a matrix where the numbers ascend both in rows

  & columns, e.g. 1 3 5 7 9 11 13 15 18 20 22 24 26 28 30 31 33 36 38 39 42 44 47 49 50 If you're asked to write a function that provides a boolean (YES or NO) answer to "does this number exist in this matrix", explain how you would design an algorithm to be most optimal.
Tags:
analytical
Answer

Interview Answer

2 Answers

0

I'm not 100% certain if that is the exact same style of matrix that was on the white board (I didn't scribble down my notes fast enough), so it may have been that some ascending numbers might be on the row above. E.G. 1 3 5 7 9 11 13 15 18 25 22 24 26 29 30 where 25 is on row 2 and 22 is on row 3. After some hand wringing and a bit of stress, the questioner dropped a hint that I could look at the beginning and end of a row and rule it out immediately if the beginning and end didn't have the desired number in range. I'm guessing they wanted a much more specific answer than this though, along with big / little O complexity time.

Interview Candidate on Jan 29, 2013
0

Start from the right-top. Keep going left till our number is greater than the number at [row,col]. Once this col is found, increment the row and move down, Repeat until found.

Anonymous on Feb 18, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.