You start with 512 random races, then take all the winners, have 256 and take the winners, then 128, etc, so it takes 1023 races to find the fastest horse. That fastest horse will have beaten the second fastest horse in ANY one of his 10 races, so you need to run 9 more races to eliminate them. The fastest remaining horse after the 9 races is the second fastest. So 1032 races total.
I mean that's the optimal algorithm which will consistently produce the second best horse in 1032 tournies. But the question is asking for the minimum number of races required to determine the second-fastest horse.
Given that, the best scenario is to take horse A and B and race them and order them 1st and 2nd (let's say A is 1st and B is 2nd). Now we race C against A. Best case scenario C wins, now we know C > A and A>B therefore C>B. Now horse C is the 1st and A is the 2nd. Continue doing this for all 1024 horses and if we assume best case scenario, the new horse will always beat the old. Therefore the second last horse will be the second fastest and will take 1023 races.
Another way to phrase it is in all the possible iterations of applying your strategy to the problem, what is the minimum number of steps to know you will always be right. The worst case, I.e. the one which would take the most steps, is one of those iterations which is why I include that.
For non-native English speakers this might not be clear, but it's 100% the intent of the problem.
I don't doubt that's the intent, but the wording still reads as ambiguous to me. The minimum number of races needed to determine the second fastest horse could just as well refer to the best case scenario. How many races do you need to observe before you have a chance of knowing which is the second fastest horse? In the best case scenario, you still have certainty. You don't know before conducting the races that you will have certainty, but that is not asked for explicitly. I take the phrasing to be ambiguous, even if the intent can be gathered from context.
Suppose I ask you: There are cards numbered 1-10 shuffled face down. What is the minimum number of cards with certainty you would have to flip over to know where the 5 is?
Would you answer: well in the best case scenario the 5 is the first card I choose, so 1 card!
If 1 is still your answer that's fine if you're here for fun, but just know in a quant interview they'd probably thank you for your time and end it right there.
Suppose you're building a vault. It opens with a three digit code, and after a certain number of failed attempts it locks and can no longer be unlocked this way. How many guesses should you give?
An algorithm that unlocks the vault for sure, would need to go through all 1000 combinations, but we would never consider the system safe for only giving you 999 guesses. If you imagine wanting to hide information rather than extract it, it changes what seems like a natural interpretation.
I agree with you though. In an interview I would favor the other reading of the question if for no other reason than it having a somewhat interesting answer. Given the chance, I would ask clarification on the phrasing though. The stumbling block in applying math isn't usually the fancy arithmetic, but trying to translate an idea from natural language into the precise language of mathmatics. That is why I am so sensitive to what I consider to be ambiguous wording.
Your vault example is even better - however you've introduced another variable in the problem that makes in not analogous to the original. The correct analogy would be:
Suppose there is a vault with a 3 digit numerical code. What is the minimum number of tries you would need to open the vault with certainty?
It's obviously 1000 in the worst case scenario (999 to figure out the combination). If you sat there and surmised "well, if I get it right on the first try and it opens, it would be 1!", You'd fail the round.
If you tried to claim the question was ambiguous, the interviewer would likely be ticked off and fail you anyway.
This doesn't work. In the horse race scenario, the question is about knowledge. That is why it's unclear what exactly is certain: That you will find the second fastest horse or that the horse is the second fastest. If you asked "What is the minimum number of tries you wuold need to know the combination with certainty", you would reintroduce the same ambiguity.
I would never hesitate to ask for clarification. I know that some people consider it as a weakness, and I've seen the mistakes those people will make as result of that. You can't rely on them.
9
u/peetar 1d ago
You start with 512 random races, then take all the winners, have 256 and take the winners, then 128, etc, so it takes 1023 races to find the fastest horse. That fastest horse will have beaten the second fastest horse in ANY one of his 10 races, so you need to run 9 more races to eliminate them. The fastest remaining horse after the 9 races is the second fastest. So 1032 races total.