Google & Microsoft
Java Interview Questions
Amazon Interview Question
Compaq Interview Question
What method would you use to look up a name in a dictionary?
Do you remember that game 20 questions? You have to ask 20 questions to guess a word. The way to cheat is to narrow it down by half every time. The English dictionary has about 500,000 words, meaning you would still have queries to spare.
Yes, it would be boring, but it would go something like this:
Does your word come before the word â€œmarryâ€? Yes
Does your word come before the word â€œgerrymanderâ€? You get the point.
Assuming you already know you have to sort, you can binary search at O(log_2 N). For this, say, a trillion, is less than 50.
But its application doesnâ€™t stop there, as it -as well as its cousin ternary search- can help you solve numerical equations (this is actually called bisection). For example, you want to find the cube root of N (N^(1/3)), but donâ€™t have any sort of library ready. Easy solution? Binary search! You know x=y^3, so â€œguessâ€ a value for x, and go from there!
Â© 2006 - 2011 Technical-Interview.com . All rights reserved