We pay for user submitted tutorials and articles that we publish. Anyone can send in a contributionLearn More
This is the fourth post in the series of programming job interview challenge. Today, I will provide the answer to job interview challenge #3, talk about readers answers (all of the comments are now approved) and give you a new challenge. So, lets get into business:
The correct answer to challenge #3:
Take a look at the example and assume we are looking for 11. As described, start with the lower left cell which contains number 8, because 11 is bigger than 8 – go right. 11 is bigger than 9 – go right, 11 is smaller than 17 – go up, 11 is smaller than 12 – go up, 11 is bigger than 9 – go right, 11 is smaller than 12 – go up, 11 is bigger than 10 – go right. 11 is found! The complexity of that solution is O(m+n) because the worst case scenario would be to search along an entire row and an entire column. This question could be also solved by starting from the upper right cell and going to the opposite directions so the winners are: Tristan, David, Marcos Silva Pereira and Anton Irinev.
Due to the fact that we received a lot of answers, I won’t be able to refer to each one of them. Instead, I will try to categorize some of the answers and relate to bunches of solutions. The first category is “The complexity is not as good as O(m+n)” so its obvious why those are not the “winners”.
This little 3X3 example matrix is for the “Start from the upper-left corner” category. If you start searching from that corner, you won’t be able to find number 5. Those who best described these kind of solution wrote “Move to the cell which has a greater value but is not greater than the search value”, so the path would be: 1 -> 4 -> Value not found in the matrix, which is wrong.
Another category is the “Two-dimensional recursive binary search” (I don’t want to mention names in that section, so look in the comments for the full algorithms). Although those solution are correct, their complexity is not as good as some of the readers thought. It took me half a day of wondering about those solution to realize that there is a basic wrong assumption in all of them. They all split the matrix into two other smaller matrixes and so on (recursively). The problem is that you may end up with rectangular matrixes (or even begin with such matrix, I said it is mXn matrix), and that is where those solutions fail. Just take a look at the following matrix – trying to find 14 will lead you to search the whole matrix… and the complexity would be O(mXn).
The only one who posted his solution in his blog – Adam’s Tech Thoughts is Adam B so I have to refer to his solution too. Adam, you will fail to find 12 in the example matrix to the left.
All of the other commentators: please accept my apologizes if I didn’t cover your solution. If you still think that you provided a better solution, just let me know (with an explanation).
One lesson I learned from the previous post is that it is very hard to read an undocumented code. Some of the readers provided code without any explanation and it is very difficult to understand whether their solution is correct or not. So, next time please avoid sending code without any explanations.
This weeks question:
How would you implement the following method: Foo(7) = 17 and Foo(17) = 7. Any other input to that method is not defined so you can return anything you want. Just follow those rules:
I must admit that I wouldn’t ask this weeks question in a job interview, but it is a really nice question. Because last weeks challenge was difficult, I am providing you with a little “fun” challenge that is more of an experiment than a job interview. This is not a real world problem but it does check how simple can we think, so think - simplicity! I believe that all of your answers will be correct, but it will be interesting to see how simple will they be.
Reminder: Comment with answers will not be approved until next weeks challenge (if readers will see the correct answer in one of the comments, it will become pointless).
The answer is now provided in Challenge #5 (Record Sorting)
Tags :answerchallengecorrecteficienthi techimagesjob interviewpixelproblemprogrammingquestionsolution
Copyright © 2012 Dev102.com
Breeze : Designed by Amit Raz and Nitzan Kupererd