How To Ace That Technical Interview
Use King Arthur's strategy at the bridge of death to solve the prisoner problem
I spent many years applying for tech jobs and hiring for tech jobs in the financial world. I always hated the annoying interviewing technique of testing candidates with puzzles. I never used interview puzzles, ever, when I interviewed people. However, interview puzzles have been ubiquitous for decades in the financial and software industries, so much so that there are whole books for job candidates devoted to puzzles and their solutions.
Puzzles are used to screen candidates in the AI/ML/programming world and in the financial world. The widespread use of interview puzzles shows that tech managers don’t know how to hire or manage people. Extreme cleverness and mathematical acuity are not the most important traits you need in successful job candidates. Most of the math in financial quant jobs or in AI/ML is not that high level. People who are successful work hard, learn what they need to learn independently, are innovative, focus on quickly solving the problems that people need to be solved, and get along with others. The ability to get along with others may be the most important skill you want to look for. That so many tech managers ignore those skills in favor of puzzle-solving ability is one reason why there are so many “management challenges” in technical industries.
The problem with the puzzles is that they screen out potential employees who would be very successful. Nonetheless, as the interviewee, you have to deal with the puzzles when you interview. Everyone is studying the puzzle books, so you need to do something to stand out. The best strategy I think is to pick some commonly asked puzzles and figure out how to extend them. Then you hope to be lucky enough to get the puzzle you’ve prepared for.
Job interviews are not unlike the bridge of death in “Monty Python: In Search of the Holy Grail.” You want to be like King Arthur. When asked “What is the air speed velocity of an unladen swallow?” Arthur replied, “What do you mean? An African or European swallow?”
An example
There is an old puzzle you may have heard of. The warden of a prison calls a meeting with the prisoners and makes the following proposal: the prisoners can decide to enter a contest in which the warden will select a prisoner randomly from solitary confinement every day and put him in a room. In the room is a single light switch, which will be in the off position the day the game begins. The selected prisoner can decide to turn the light on or off, but other than that, there is nothing to do in the room. The prisoner is not allowed to touch anything in the room or attempt to leave any kind of message. The other prisoners will not know who has been selected on any day and they will not be allowed to communicate in any way after the game begins. The game ends when one of the prisoners announces when all the prisoners have been in the room at least once. If correct, the warden will free them all immediately. However, if incorrect he will double their sentence. The warden gives the prisoners one hour to confer. Should the prisoners take the deal?
The puzzle book solution is that the prisoners should appoint one prisoner, Bob, to be the official counter. Bob’s only job is to add one to his count every day he is randomly selected to enter the room, but only if he sees the light switch already turned on. He then must turn the switch off. If he is selected to enter the room when the light switch is turned off, he does nothing.
Every other prisoner’s only job is to switch the light on the first time he is randomly selected to enter the room, but only if the light switch is not already on. In all other cases, the prisoners must do nothing when they are randomly selected to enter the room.
In this way, every prisoner turns on the light exactly once and Bob counts that prisoner when he is randomly selected to enter the room. When Bob counts N-1 light switches that have been turned on, he can be sure that all N prisoners, including himself, have been in the room at least once.
You’ll likely have seen this puzzle in a puzzle book with the solution above. In this case, however, you can work out a better solution in advance that challenges the assumptions of the interviewer. Then you can channel King Arthur with something like: “What do you mean? How many prisoners are there and how long are their sentences?” Then you can explain as below.
Advanced solution
The puzzle book answer shows that a strategy exists to always decide when all prisoners have been in the room at least once. But that doesn’t mean the prisoners should take the deal. The answer depends on the number of prisoners and the length of their sentences. If the procedure takes longer to implement on average than the sentence the prisoners are serving, they shouldn’t take the deal, even if the standard solution works.
The key to solving this problem is to realize that each prisoner must wait some random number of days to get into the room for the first time to turn on the light. Similarly, Bob must wait some random number of days before he is selected to enter the room and count each prisoner who turned on the light. The total number of days to win the game is the sum of the days each prisoner must wait on average to turn on the light and the number of days Bob must wait to count each prisoner. The geometric distribution is ideal for this problem because it models the number of trials until the first success.
Suppose we’re in the middle of the game. Out of N prisoners, there are k prisoners remaining that have yet to turn on the light. The probability that one of the k prisoners will be selected to enter the room is
since the probability that any prisoner selected is 1/N and the probability that one of the k prisoners will be selected is
The probability that a prisoner will be selected who has already turned on a light is then
We can model the selection process of one of the k prisoners who has not yet turned on the light as a geometric distribution, which gives us the probability that one of the k prisoners will be selected in i days as
The formula says that prisoners who have already turned on the light switch are randomly selected for i-1 days, followed by the selection of one of the prisoners who has yet to turn on the light switch.
Similarly, Bob’s selection can also be modeled by a geometric distribution.
The probability that Bob is selected to enter the room after i days is
The average number of days that the kth prisoner will wait to turn on the light is the mean of the geometric distribution, which is the reciprocal of the probability he will be selected. The average wait time for the kth prisoner to be selected to turn on the light is
days.
The average time that Bob will wait to count each prisoner who has turned on the light is the reciprocal of his probability of being selected. Hence the average number of days for the kth prisoner to get into the room followed by Bob is
This is the average number of days to count the kth prisoner,. The total number of days is the sum of this quantity for k from 1 to N-1. Hence,
We can write this series as
Note that
so
Set j = N - i - 1 and thus
Finally,
where
the N-1 th harmonic number.
The harmonic numbers are the finite sums of the reciprocals of the integers. The first few harmonic numbers are H1 = 1, H2 = 3/2, H3=11/6, and H4 = 25/12.
The expected time to win the game is not all the prisoners need to make a decision. The wait time is random, so they will also need an estimate of the standard deviation of the wait time to account for uncertainty. Using the geometric distributions, and the fact that Bob’s selection is independent of every other prisoner’s selection, we can add the variance of Bob’s wait time to the other prisoner’s wait time. The total variance of the wait time is:
We can also derive an extremely accurate approximation for relatively small N. For N sufficiently large, the harmonic numbers can be approximated as
where γ ≈ 0.5772, the Euler-Mascheroni constant. Thus, for sufficiently large N, the expected waiting time in days to win the game is
Similarly, we can write the variance as
where we have made use of Euler’s famous Basel problem relation:
Should the prisoners take the deal?
Whether the prisoners should take the deal depends on how many of them there are and how long their sentences are. Suppose the prisoners all got three years. Using the formulas we developed, if there are 50 prisoners, the average time to decide how many prisoners have been in the room is 7.33 years with a standard deviation of about 1 year. They shouldn’t take the deal because they would more than double the length of their sentences. On the other hand, if there are only ten prisoners, it will take about a third of a year on average to determine when all prisoners have been in the room. That’s a good deal.