A few of my coworkers and I put together the ultimate Google interview question:
You are trying to cross a river with a barman, a bear, a fox and a thousand rabbits.
You have a single row boat that travels at 99.9% the speed of light that can only carry you and two animals at a time. The row boat has only one instruction: Go forward. It returns true iff it managed to go forwards.
For every 5 minutes of wait time, the rabbit population on each side of the river will grow according to the Fibonacci sequence.
Also, each rabbit has a unique integer written on its back and you want to line them up in numerical order on the other shore but can only look at 100 rabbits at a time.
You can ask questions of the bear, the fox and the rabbits but the fox always lies, the rabbits always tell the truth, and the bear will eat you if it thinks your question is dumb.
If you leave the fox unattended, he will attempt to jump into a manhole while carrying the cover.
The bear is trying to implement a stack where push, pop and min are O(1).
A gnome appears and asks the barman for a drink, the barman pulls out a gun and the gnome says "thank you" and leaves.
The barman then holds up a ladder that reaches partially over the river, allowing you to drop rabbits onto the other side but you don't know how high a fall the rabbits can survive.
Your answer must be robust as our boats and ladders are flaky, and we pride in building world class infrastructure over flaky components.
How would you unit test your river-crossing algorithm?