The post collects some interesting puzzles from my interviews, math forums, stackoverflow, etc.
Design a function , such that where is a 32 bit signed integer.
Solution:
.
Start from a place on earth surface, you travel south for 100 miles, east for 100 miles, and finally north for 100 miles and you get back to your starting point. Where did you start?
Solution:
At the north pole.
Or, 100 miles north of any point on the circle around the south pole that is 100 miles in circumference.
Or, 100 miles nouth of any such circle whose circumference is an integral fraction of 100 miles.
Imagine an administrator willing to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants.
Solution:
This problem is a famous example of optimal stopping theory. The solution come from the wiki.
Each of them is put on a hat of either red or blue with i.i.d probability of 0.5. (i.e. equal chance of being red and blue, and what’s put on one person doesn’t affect what are on the other people.) Each one can only see the other people’s hats, but not his own. He has to guess the color of his own hat by writing down either “Red”, “Blue”, or “Don’t know”. After all three people write down their guesses, they would win if:
At least one of them guessed right, and
None of them guessed wrong.
Those three people can discuss a strategy before the hats are put on their heads. After the hats are on, they can’t communicate to each other including seeing other’s guess. What strategy would give them the best chance of winning and what’s the probability of winning under that strategy?
Solution