Interview Questions And Answers 
-
On an average, how many times would you have to radomly flip open the Seattle phone book in order to find a specific name?
12,145 Views |
(15 votes, avg: 3.73)
Loading ...
Answers »
Our Sponsors
Our Sponsors
It depends on the number of pages in the phone book. Let’s say that the Seattle phone book has 800 pages. Let’s also assume that every page in the phone book has names (no blank pages, etc). In this case, the book as 400 openings. Your chances of randomly opening the book to the right page is 1 in 400.
I would say do it smartly. If I’m going to randomly open a book to find a name, I want to narrow my chocies each time so I’m eventually getting closer to the goal.
So, open the book, if you aren’t at the rigth page, figure out what side the name is in (left or right). Rip out that part of the book, and choose randomly again. Repeat this process until you are down to your page
On average, this should take log(n) times where n is the number of pages in the book.
I would like to try the binary search… so it would be Log #Pages to Base2
Read the question: “randomly filp open”
Just estimate the number of people in seattle, People per household, percentage of household not withdrwan form the ph book, and number of entires per page. then its simple..
Since they said you and not some random person, they are asking whats the fastest way to randomly choose something right. Average people would take 1/n pages. Smarter people can do it in log_2(n).
The answer is 1. You “randomly” flip open the book once, the rest of the time you are using prior knowledge and a search strategy.
I’m inclined towards Carson’s answer though I’m not sure if this is what the interviewer wants to hear from us.
No one actually answered the question though. Lets take the first answer and assume flipping once gives you a 1:400 probability. So (on average) to find the name we need at least a 50% probability, you’d have to randomly flip open the book 200 times.
Two keys:
1.On an average — it means not 1 or 400(800 pgs);
2.radomly flip — you cannot use binary serach, but you do something close, that what everybody does.
Say you want to find John MacCain, you are not going to open #10 or # 390 even you open radomly.
Say you open # 150, and it has Joe Courier. You know you have a lot work to do. So, you do it “almost” radomly, but advanced another 345 pg. And this time, you get a T. Nakazawa. So, you understand, you need to go back a little.
With binary search, you need only 8(lg 512) to 9 time. Since you cannot use the search exactly, I would estimate it to be 1.5 to 2 times 8 = 12 to 16 times.
Assuming Jorge’s 400 openings, and further assuming that openings are not prejudiced by previous openings, such as might well happen if the spine became creased, or contaminants introduced between pages, or static charge dissipated / increased, etc. etc. …then the answer is 277.
You can probably impress them by giving them two different answers…
Simple answer:
If you are allowed to rip out any page that doesn’t have the name as you look at a page, then the answer is simply 1/2 the number of pages. (Sampling without Replacement.)
More complex answer.
If you must preserve the phonebook (Sampling with Replacement), then the probability of NOT find the name at any give try is:
(N-1)/N
(This is assuming that this is truly random, which with a physical book isn’t necessarily the case.)
The 0.5 probability of NOT find the the name after x tries is multiplicative:
((N-1)/N)^x = 0.5
If N is 400, then x will be 277 (as mentioned by Donald), requiring logarithms to solve.
But you just gave an answer that says “with probability .5, you will not find the correct page by attempt 277″. This is *not* the same as the expected number of pages you’d need to flip!
The problem can be rephrased as follows: you have a weighted coin that lands on heads with probability (1/400). If you flipped the coin repeatedly until it landed on heads, what is the expected number of flips?
This is a geometric distribution:
http://en.wikipedia.org/wiki/Geometric_distribution
And the expected value of a geometrically distributed random variable is 1/p = 400.
Leave an Answer/Comment