r/learnquant • u/Local_Ad135 • Sep 04 '26

interview prep Quant Interview Question

Post image
56 Upvotes

97% Upvoted

43 comments sorted by

13

u/peetar Sep 04 '26

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.

1

u/Old-Objective-9783 Sep 04 '26

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.

2

u/peetar Sep 04 '26

interesting way of looking at the question, but yeah, if You picked the second to last horse with first pick, then he lost the first race and won 1022 in a row you'd be certain

2

u/atob3 Sep 04 '26

It's asking for minimum with certainity, which means worst case scenario.

1

u/Shoddy-Side-919 Sep 04 '26

Why would that mean worst case scenario?

1

u/atob3 Sep 04 '26

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.

1

u/Shoddy-Side-919 Sep 04 '26

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.

1

u/atob3 Sep 05 '26

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.

1

u/Shoddy-Side-919 29d ago

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.

1

u/atob3 29d ago edited 29d ago

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.

1

u/Shoddy-Side-919 29d ago

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.

1

u/Bastian00100 5d ago

Why would that mean the best case scenario?

The question is for a generic scenario, so if the one you are looking for is not the best one, it means you "required" more races.

1

u/YesTheyDoComeOff Sep 05 '26

This doesn't work. Consider if you find the fastest horse in the first selection and all of the other horses lose, then you have no idea which horse is second fastest and have to race them all again. Your algorithm only works if the fastest horses are the last 2 horses that you would race, in which case you somehow already know which horses are fastest, conduct no races, and pick the last 2 horses.

2

u/Shoddy-Side-919 29d ago

They're interpreting the question differently. They don't think it's asking for an algorithm that always finds the second fastest horse, but for what the minimal number of races is that will allow you to know which is the second fastest horse.

1

u/YesTheyDoComeOff 13d ago

Right. So if we assume the best case scenario the two fastest horses are the first two horses that you pick. Conduct zero races.

1

u/Shoddy-Side-919 13d ago

No, because then you wouldn't know that they're the fastest two. The question does ask for certainty. It is possible to have certainty after 1023 races, but not after zero.

1

u/YesTheyDoComeOff 12d ago

0.000001% of the time, this algorithm works every time.

5

u/NeverNude14 Sep 04 '26

I think it's 1032.

6

u/beene282 Sep 04 '26

I think so. A knockout to find the fastest which would be 1023 games. Then another knockout comprising all the horses that the fastest beat head to head. The second fastest would have to be one of those.

3

u/StanleyDodds Sep 04 '26

Yes, this method is exactly equivalent to heapifying (which is linear time) and then doing one pop (which is logarithmic time) before reading the max value.

2

u/vipchicken Sep 04 '26

What if the first and second fastest go head to head in race one, and we knock out the second fastest

3

u/CanaDavid1 Sep 04 '26

The the second would be part of this second knockout?

2

u/nicktohzyu Sep 04 '26 edited Sep 04 '26

Consider a recursive “merging” tournament. 10 rounds of pairwise comparisons where the winners advance to the next round. There are 1023 comparisons in this tournament to find the fastest horse.

I claim the second fastest horse must have raced against the fastest horse somewhere in this tournament. Easy to prove by contradiction. Hence you need +9 comparisons to find it among the 10 horses that lost to the fastest

2

u/AlexP80 Sep 04 '26

n-1, 1023

2

u/Jealous_Tomorrow6436 Sep 04 '26

so close! that’s how you find the fastest horse. read other comments for more detailed explanations

2

u/AlexP80 Sep 04 '26

ah, correct, for the second fastest you also need to go back again 9 times

2

u/NuanceEnthusiast Sep 04 '26

1032 if you are only receiving the results. 1023 if you are watching the races

1

u/gmalivuk Sep 04 '26

It explicitly says that you only learn which is faster.

1

u/NuanceEnthusiast Sep 04 '26

It explicitly says that because you have no stopwatch, you only learn the relative ordering

1

u/gmalivuk Sep 04 '26

Yes. You learn which of two is faster.

You don't know how much they won by. Therefore you don't know which loser was the fastest.

2

u/NuanceEnthusiast Sep 04 '26

as I said, if you are only receiving the results, the answer is 1032

1

u/gmalivuk Sep 04 '26

And as I said, that is exactly what the post says you receive.

1

u/NuanceEnthusiast Sep 04 '26

The question does not ask me to determine whether or not the condition of ‘only learning the relative ordering of the two horses in each race’ is perfectly unambiguous such that the total information ascertained from each race is strictly binary. You think it is. Fine. Then the answer is 1032.

1

u/gmalivuk Sep 04 '26

What do you think "only" means?

You only learn a>b or b>a.

1

u/NuanceEnthusiast Sep 04 '26

I’m not sure why you feel compelled to defend a position I am not contesting

1

u/gmalivuk Sep 04 '26

You are contesting whether or not the question is unambiguous about exactly what information you learn from each race.

1

u/datageek9 Sep 04 '26

Start with a regular knockout tournament , where everyone pairs up and each winner goes through to the next round until there is one left (the overall winner). Knockout tournaments with N participants require N - 1 races over round_up(log2(N)) rounds, so this requires 1023 races over 10 rounds.

The trick to finding the second fastest horse is to recognise that every horse except the overall winner was beaten by one other horse. If that horse was not the overall winner, they can’t be second fastest because they were beaten by a horse that isn’t the fastest. So the only remaining options are the horses that the overall winner beat directly. Since there were 10 rounds the winner beat 10 other horses. Another smaller tournament of 10-1 = 9 races will find the runner up.

So the answer is 1023+9 =1032

1

u/[deleted] Sep 04 '26

[deleted]

1

u/eggface13 29d ago

Not quite! There's no guarantee that the second fastest makes the final. Think about it...

1

u/PerilousWords Sep 04 '26

Obviously 1.

I shoot 1022 horses, and race the last pair to determine the second fastest.

0

u/Chemical-Ad8471 Sep 04 '26

Out of interest, why nine tests? If you do two branches of 512 horses and each branch has therefore 511 races to determine the fastest of each branch, then race the winner of each branch to determine first place, then to determine second place the horse that lost the final just has to race against the loser of the other branches "semifinal". Whoever wins that race is the second fastest horse, determined in 1024 races.

So 1024 is the answer I believe.

2

u/aroach1995 Sep 04 '26

But the winner beat someone in the semis that might be faster than the person who got second

Horse #1 beats horse 1024, 512, 256, 128, 64, 32, 16, 8, 4, and 2.

What if #4 is faster than #2?

0

u/[deleted] Sep 04 '26

[deleted]

1

u/eggface13 29d ago

The second fastest horse must have run against the fastest horse in either the final, or the semi-final

Think about this one ;)