Subscribe to:
Post Comments (Atom)
Cracking the Coding Interview: Fourth Edition (308 page e-book / PDF)
Delivered instantly as a PDF via email. For Software Engineers & SDETs
- 150 programming interview questions and answers
- 5 proven approaches to crack algorithm questions
- 10 mistakes candidates make, and how to avoid them.
- How to prepare for technical and behavioral questions without wasting your time!
Just $29.99 to Crack the Interview!
Remember that game 20 questions? You have to ask 20 questions to guess a word. Well, the way to cheat is to narrow it down half way every time. The English Dictionary has about 500,000 words, meaning you would still have queries to spare.
ReplyDeleteYes, 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). Which for 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 call bisection, but same paradigm). For example, you want to find the cube root of N (N^(1/3)), but don’t have some sort of library ready. Easy solution? Binary search! You know x=y^3, so “guess” a value for x, and go from there!
Even though "binary search" is the classical answer, in real life you'll follow an approach similar to a "Trie". Say you're searching for "Tennis", you don't open the middle of the dictionary, you aim closer to T, and you again search for "e" and so on.
ReplyDeleteAre you guys really understanding the question?
ReplyDeleteI think anonymous #1 is right.
ReplyDeleteI wouldn't typically use a dictionary to look up a name. An encyclopedia would be a more appropriate resource.
ReplyDeleteIf you look beyond the "tricky" aspect of the question, i think the simple answer would be "alphabetically".
Rather than use a binary approach, i'd assume the dictionary has already been divided into ~26 sections (often P & Q are listed together, and sometimes X/Y/Z).
Open to the section containing the first letter of the name. Then use a method similar to the one described in comment #1.
I'd also mention that most proper names would be listed alphabetically by LAST name.
ReplyDeletei think indexing is the way to go
ReplyDeletei think indexing is the way to go
ReplyDelete26 Clustering followed by second level of 26 clusters...and so on.
ReplyDeleteBinary Search for the final bucket.
26^LevelOfIndexing - Clusters formed.
By traversing char by char we can converge to our searched node.
Multilevel Clustered Indexing followed by Binary Search.
In comment#1, Inspite of using
- sorted nature of words.
- relationship between characters.
- All character are uniformly distributed.
Data is indexed on the basis of question. F(Question,Answer) = Index.
Please comment
This comment has been removed by a blog administrator.
ReplyDelete