Hudson River Trading interview question

You have three sock drawers. One has red and blue socks, one has blue and green socks, and one has green and red socks. What is the expected number of socks you must pull to be sure which drawer is which, assuming that the number of socks of each color in each drawer is both large and equal?

Interview Answers

Anonymous

27 Sept 2024

5 - first drawer requires 1 for the first and 2 for the second color; second drawer requires 2 to see the repeat color.

5

Anonymous

14 Oct 2024

optimal solution I think

Anonymous

25 Oct 2024

Its 19/4. Optimal solution is draw one from each drawer. Now you will only get sequence like R G R or R G B. Each of them you just need to draw from one drawer to tell, which needs 2 times EV. So this you get 3+2=5. Now if you first two draw from two drawers are both Red, then you know the remaining one is RB, and you only need 4 times here. The probability of such is 1/4. So 14* 4 + 3/4*5=19/4

1

Anonymous

15 Jan 2025

The 19/4 solution is correct but it's written pretty poorly so I'll re-explain for reference: The optimal drawing strategy is to draw a single sock from each drawer. After drawing from two drawers, if you get the same color from both (eg. Red, Red) you know the final drawer contains the other 2 colors (eg. blue and green). In this case, you just need to then draw from one of the original two drawers until you get a different color, which has an EV of 1/(1/2) = 2 draws, for a total of 4. Note that getting the same color twice has a probability of 1/4, since you have a 1/2 probability that the second drawer contains the color of the first draw, and a 1/2 probability that you draw the same color. In the case where the first two draws are different (eg. Red, Green), we then draw from the third. If this draw is either Red or Green, then we are in the same situation as earlier, meaning that we need 2 more draws for a total of 5. If the third draw is unique from the first two (meaning that you've now drawn Red, Green, Blue in some order), we note that we simply must now identify the identity of ONE of the three drawers to solve (you can pretty easily work through this and find it out yourself). This, as we've used before, takes an EV of 2 draws, meaning that it will also take a total of 5 draws. Now, we've found that there is a 1/4 chance that we have 2 same-color draws initially, which will take us expected 4 draws, and 3/4 chance of not having this, which gives us an expected 5 draws. So, our final answer is (1/4)*4 + (3/4)*5 = 19/4.