How would I find a book in a large library?

I found the following question while preparing for an interview:

You are in a very huge library that has no computer access, and you're looking for one particular book.

You look up where the book suppose to be from the card catalog, and went to shelf X to find it.

However the book is not there.

There is only one person that can answer questions, which is the libarian, but he only answers yes/no 开发者_JAVA百科 responses. Plus, his answers might not be correct.

What is your strategy for finding this book?

How would you answer this question? What methods of searching would you use?

Use Binary search type questions to narrow the location of the book.

Each question should narrow the search field by half.

"Is the book on this half of the library"? (Point to the right direction).

Would work as an initial question.

You can also use The Knight and the Knave as part of your method of questioning the person. Your first 5 questions (to establish a baseline) could be about things you 'know'. You could determine his error rate from there. After that, you can use Binary Search-esque questions to determine where the book is.

1. Ask the interviewer for more information about the librarian and go from there. In particular, find out if he's susceptible to bribery (I mean the librarian, but come to think of it this might go for the interviewer as well).
2. Double-check for dumb mistakes (wrong card, wrong shelf, "661-88" is reall "88-199" and so on).
3. Search the drawer of borrowed-book cards. If it's been borrowed, note the due date and come back later, or note the borrower's home address and go to plan B.
4. Look in the vicinity, a few books in either direction and the shelves above and below, in case it was incorrectly reshelved.
5. Check the tables, floors, photocopiers and return carts.
6. Look for a gap on the shelf. If there is a gap in the right spot then at least you know you're looking in the right place. If there's no gap then look for a book on that shelf that doesn't belong-- somebody may have swapped them by mistake. If there's no such misplaced book then maybe the book was never on this shelf, see below.
7. Look for dust on the shelf. It might indicate whether a book has been removed within the past month. Likewise check the index card for signs of age. The flowchart gets a little complicated, but the book may have been lost years ago.
8. Check the index system: if the book doesn't have the right number for its subject/title/author/whatever, then there is a typo on the index card and you must calculate the correct number yourself to find out where the book really is.
9. Just go out and buy the damned book, your time is more valuable than this.

Step A: Calibrate your Librarian.

Pick a random book in the library, walk to a random spot and then ask the Librarian if the book (whose location you know) is to your left. Keep testing the Librarian until you have a good estimate of the probability, p, that Librarian answers correctly. Note that if p < 0.5 then you are better off following the opposite of whatever Librarian tells you. If p=0.5 then give up on Librarian -- her responses are no better than a flip of a coin.

If you find that p depends on the question asked (for example, if the Librarian always answers certain questions correctly, but other questions always falsely), then go to Step B1.

Step B1: If p==0.5 or p depends on the question asked, start thinking outside the box, like Beta suggests.

Step B2: If p < 0.5, reverse the answer the Librarian gives, and proceed to Step B3.

Step B3: If p > 0.5: Choose N. If p is close to 1, then N can be a low number like 10. If p is very close to 0.5, then choose N large, like 1000. The right value of N depends on p and how confident you wish to be.

Ask the Librarian the same question N times ("Is the book I'm looking for to my left"). Assume for the moment that whatever response is given more frequently is the "correct answer". Calculate the average response, assigning 1 for the "correct answer" and 0 for the wrong answer. Call this the "observed average".

The responses are like draws from a box with 2 tickets (the right answer and the wrong answer.) The standard deviation of a sample of N draws will be sqrt(pq), where q = 1-p. The standard error of the average is sqrt(pq/N).

Take the null hypothesis to be that p=0.5 -- that the Librarian is simply giving random responses. The "expected average" (assuming the null hypthesis) is 1/2.

The z-statistic is the (observed average - expected average)/(standard error of the average) = (observed average - 0.5)*sqrt(N)/(sqrt(p*q))

The z-statistic follows a normal distribution. If the z-statistic is > 1.65 then you have about a 95% chance the average response of the Librarian is statistically significant. If after N questions z is less than 1.65, repeat Step B3 until you get statistically significant response. Note that the larger you choose N, the larger the z-statistic will be, and the easier it will be to obtain statistically significant results.

Step C: Once you get a statistically significant response, you act upon it (using George Stocker's binary search idea) and hope you have not been statistically unlucky. :)

PS. Although the library might be 3-dimensional, you could play the Binary Search game along the x-axis, then the y-axis, then the z-axis. So the 3-dimensional problem can be reduced to solving 3 (1-dimensional problems).

here's a starting point: Assume the library uses the Dewey decimal system (but any classification system could be substituted). Question 1: is the book in the 100s? Question 2: is the book in the 200s? .. is the book between 50 and 150? is the book between 150 and 250?

Depends on who you are interviewing for:

Government (non-law enforcement/military) - hire infinite number of staff to check every location in library. Then hire an infinite number of junior managers to manage those staff, add an infinite number of middle managers etc.

Large corporation - same but use unpaid interns.

Government (law enforcement/military) - take librarian, apply tazer or waterboarding until location of book is revealed.

Small company (web 2.0 startup) - blog about location of book until somebody tells you.

Small company (real business) - try another library / bookstore.

Is it cheating to ask if the librarian takes commands? If he does, simply tell him to find the book and bring it back to you.

How would you answer this question?

"Thank you for your time." And I'd get up and walk out of the interview room. I'm not interested in working with people who think that asking silly riddles in an interrview is more useful than asking me to write some code or demonstrate how I would plan a project or lead a team.