Technical Interview

Home
Added Recently
Data Structures
Puzzles
Google & Microsoft
C/C++ Questions
Java Interview Questions
Quantitative Problems
Algorithms
Featured Articles
Amazon Interview Question
Compaq Interview Question
Technical Interview
Interview Process
Introduction Questions
Object Oriented
Google Pages
Fundamental Questions
Resume Tips
Links
Contact Us
Submit Question/Answer
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!