A question encountered at a Google interview.The person was hired.What is the quickest way to find the last name Ostark in a phone book if you can only open the book and if it is not on that page you must close the phone book and try again. AKA-you cannot flip through the pages, after each guess you must close the book and then reopen it.

One way would be to make guesses based on the thickness of the phone book. E.g. I start by guessing that Ostark is at the 3/5 of the book. I open it at the 3/5's and if I see, for example, Richards, I'll know that I have to adjust my second guess upwards....

Fold the page you opened so a part of it stands out ?

Is trickery allowed? For example like McCarreira suggested folding the page or can one tear out the incorrect page? If the answer is no, may be a binary search? Actually can we call someone on that page and ask him/her to look it up for us?

actually if the definite goal is to call this person, I will call operator Otherwise, I will split it in the middle and remove the first half.Then close teh book, split it in 2 and remove the last half... and so on

QuoteOriginally posted by: rcarlton88What is the quickest way to find the last name Ostark in a phone book if you can only open the book and if it is not on that page you must close the phone book and try again. AKA-you cannot flip through the pages, after each guess you must close the book and then reopen it.The quickest way is to change the rules, dumbass.

Open the phonebook anywhere. Write "Ostark" in it. Done."Rule changing" is always an interesting metabrainteaser problem. How far can one push the solution outside the stated confines of the problem? How much should one infer a higher-level problem (e.g., reaching "Ostark" on the phone) to solve the unstated true problem? How much should real world, devil-in-the-details factors affect the solution?Some of this rule changing should be in the context of the questioner. With Google, I'd think about a parallel distributed solution or a solution in which leverages freely available data. The question asks for "quickest" not "least total effort" so that leave open the option to tap into multiple processors.

Have a ton of numbered bookmarks.

If you open the book and all the names are before ostark in alphabetical order:you tear out all the pages on the left side and the close the book and repeat.If you open the book and all the names are after ostark. You tear out all the pages on the right side...Continue until you find Ostark.

Probably consider all words that would probably not appear as a first letter of a name. Eliminate Y, Z, X, U, K, Q, V, ..? Then take ratio 15/(26-7). Then take ruler and measure 15/19 up from start. Open and look at letter you are at. Then say if you are at P, then do a similar count with second letter of name. Now you take portions of 1/19th from book. So if you open at Perry you would look 15/(26-7)- 4/(1/19) from the start, since there are around four letters that would likely follow a first between s, t, u, v, w, x, y, z, a, b, c, d, e . Do the same repetition until success. However you would need a ruler for this....and I am not sure of which letters are more likely to appear in different places of names.