How Not to Interview a Database Administrator (The Google Way)

As suggested by the following story, Google would have preferred to hire my teenage daughter as the manager of their database team instead of me. I was on a long drive with my family so—to pass the time—I asked them to solve the problem that the Google interviewer had asked me to solve:

“Four men are on one side of a rickety bridge on a dark night. The bridge is only strong enough to support two men at a time. It is also necessary for the men crossing the bridge to carry a lantern to guide their way, and the four men have only one lantern between them. Andy can cross the bridge in 1 minute, Ben in 2, Charlie in 5, and Dan in ten minutes. How quickly can all four men be together at the other side?”

My daughter’s first solution was identical to mine.

Andy and Ben cross the bridge first. This takes two minutes.
Andy returns with the lantern. This takes one minute.
Andy and Charlie cross the bridge next. This takes five minutes.
Andy returns with the lantern. This takes one minute.
Andy and Dan cross the bridge last. This takes ten minutes.

The total time for the above solution is 19 minutes. However, I had googled the answer after returning from my interview (at Google) and knew that the four men could cross in 17 minutes, so I asked my daughter to try again. She “solved” the problem on her second attempt which suggests that Google would have preferred to hire her as a manager of database administration instead of me. Click here to see the “solution.”

I quoted the words “solved” and “solution” in the above paragraph because we still need a rigorous proof that the above “solution” is in fact the optimal solution; that is, is there a solution that takes less than 17 minutes? Neither does the above “solution” provide any insight into the general case. For example, the above “solution” is not optimal if Ben takes 4 minutes to cross the bridge instead of 2 minutes. The above “solution” needs 23 minutes if Ben takes 4 minutes to cross the bridge but it can be done in 21 minutes. And what if there are more than four people who need to cross? I am willing to bet that my Google interviewer would not have been able to prove the optimality of the above “solution” or solve the general case. If you’re interested, a comprehensive mathematical treatment of the above case as well as the general case can be found in this mathematical paper by Prof. Gunter Rote of the Free University of Berlin.

The Google interview technique is not the best technique for finding the best database administrators (or those with the right aptitude). Please feel free to comment. Is it just a case of sour grapes on my part?