Quant puzzles, solved step by step

17 minutes. Send 1 and 2 over (2 minutes), 1 comes back (1), 5 and 10 cross together (10), 2 comes back (2), and 1 and 2 cross again (2). The obvious plan, where the fastest person escorts each of the others, takes 19. The saving comes from putting the two slowest walkers on the bridge at the same time.

Why does the obvious plan lose two minutes?

Think of two slow parcels going by the same courier. If each travels on its own trip you pay for both trips; if they share a van, you pay for the slower one only. Every crossing costs the slower walker's time, so a slow person paired with a fast one wastes the fast one, and two slow people paired together waste nothing. Escorting with the fastest person pays 10 and then 5 as separate crossings. Pairing 5 with 10 pays 10 once and the 5 minutes are free.

What is the price of pairing the slow two?

Somebody has to bring the torch back after the slow pair crosses, and it must not be one of them. So the plan first ferries two fast people over, leaves one on the far side to carry the torch back later, and spends the 2 minute walker's return trip to buy the 5 minute saving. The trade is 1 + 2 extra minutes of shuttling against 5 minutes saved on the slow side, a net gain of 2. With different speeds the trade can flip, which is the real content of the puzzle.

How do you convince the interviewer 17 cannot be beaten?

There must be at least five crossings, three over and two back, because each trip over moves at most two people and someone must return the torch. The 10 minute walker costs 10 on whatever crossing carries them. If 5 and 10 cross separately you already spend 15 on those two trips, and the three remaining crossings cost at least 1 + 1 + 2, which is 19; if they cross together, the best you can do with the other four crossings is 2 + 1 + 2 + 2. A brute force over every schedule gives the same minimum, 17 minutes.

8/11, about 72.7%. If it is raining, all three say yes with probability (2/3)^3 = 8/27. If it is dry, all three must be lying, (1/3)^3 = 1/27. Weight each by how often it happens: 1/4 x 8/27 against 3/4 x 1/27, which is 8 parts to 3. Three agreeing witnesses move a 25% prior a long way, but not to certainty.

Why is the answer not simply 8/9?

Picture a clinic where a test is quite reliable but the illness is uncommon. A positive result makes the illness more likely, but how much more depends on how rare it was to begin with. The friends' agreement tells you how much more likely rain makes their answer than dry does, eight times, but it does not erase the fact that dry days are three times as common. 8/9 is the answer you get if rain and dry start level. Here they do not.

How do you set it up so the arithmetic stays small?

Use odds rather than probabilities. Posterior odds are prior odds times the likelihood ratioHow many times more likely the evidence is if the hypothesis is true than if it is false., and both are easy numbers here. Prior odds of rain are 1 to 3. The likelihood ratio of three yeses is (2/3)^3 over (1/3)^3, which is 2 cubed, 8. So the posterior odds are 8 to 3, and the probability is 8 over 8 plus 3, 8/11. Each additional agreeing friend would double the odds again.

What assumption is doing the work, and should you say it?

The calculation needs the friends to lie independently. If they could be coordinating a joke, three yeses are really one piece of evidence, and the answer falls back towards the one-friend figure of 2/5. Say the independence assumption out loud, then give 8/11. Interviewers often follow up by making one friend unreliable or by letting them talk to each other.

The peak is 3 users. Turn every join into a +1 event and every leave into a -1 event, sort all ten events by time with leaves before joins at equal times, and keep a running total. It goes 1, 2, 1, 2, 3, then at time 7 down to 2 and back to 3, then 2, 1, 0. Sorting costs n log n, and the sweep itself is linear.

Why not check every moment in time?

A shopkeeper who wants to know the busiest moment of the day does not count heads every second; they note each time the door opens in or out and keep a tally. The count of users can change only at a join or a leave, so the maximum must occur just after some join, and you only need to look at the 2n event times. Checking every time step costs time proportional to the length of the day, and comparing every pair of users costs n squared; both are far too slow at a million users.

Why does the tie rule matter so much?

At time 7 user 1 leaves and user 5 joins. If a user's session is taken to end just before the moment they leave, then a leave and a join at the same instant never overlap, and the leave must be sorted first; sorting the other way invents a user who was never there. In code this is one comparison in the sort key, and it is exactly the detail interviewers use to separate a working answer from a nearly working one. Ask which convention applies before writing any code.

Is there a version that avoids building the event list?

Sort the join times and the leave times separately and walk two pointers through them. At each step take the earlier of the next join and the next leave, taking the leave on a tie, and adjust the count; this is the same sweep without allocating 2n tuples. If times are small integers you can go further: add +1 and -1 into an array indexed by time and take a running sum, which is linear. Mention both and say which you would use for a million users with timestamps in milliseconds.

About 12.7%. A skilled manager wins exactly 8 of 10 with probability 0.1209; an unskilled one with 0.0439, a likelihood ratio of about 2.75. Prior odds of skill are 5 to 95, 1 to 19. Posterior odds are 2.75 to 19, so the probability is 0.05 x 0.1209 / (0.05 x 0.1209 + 0.95 x 0.0439) = 0.127. The record helps, but luck has far more players.

Why does an impressive record move the needle so little?

Imagine a thousand people each tossing a coin ten times. About 55 of them will get eight heads or better with a fair coin. If a handful of the thousand had slightly biased coins, you still could not pick them out from the lucky crowd by one run of ten. Evidence moves a belief in proportion to how much more likely it is under one explanation than the other, and 8 wins in 10 is not much more likely from a 60% manager than from a 50% one. The ratio is about 2.75.

How do you set it up quickly?

Use odds. Prior odds of skill are 1 to 19; the likelihood ratioHow many times more likely the evidence is under one hypothesis than under the other. of the record is (0.6/0.5) to the 8 times (0.4/0.5) squared, which is 1.2 to the 8 times 0.64, about 2.75; multiply to get posterior odds of about 0.145. Converting, 2.75 over 2.75 + 19 is 12.7%. The binomial coefficient, 45, is the same in both likelihoods and cancels, so you never need it.

What does this say about picking managers?

When skill is rare and its edge is small, even a long, strong track record leaves luck as the likelier explanation. Using 8 or more wins instead of exactly 8 barely changes things: the answer becomes 13.9%. The honest limitation is that the model is stylised: real skill is not a fixed 60%, and survivorship means the managers you hear about were already filtered for good records, which pushes the true figure lower still.

Rs 2. Without information the bet is worth 0.5 x 10 - 6 = -1, so you decline and your value is 0. With the colour known, you play on red and make 4, and skip black and make 0, which averages 2. Information is worth the improvement in your best decision: 2 - 0 = 2. If it would not change what you do, it is worth nothing.

How do you value a piece of information?

Suppose a weather forecast costs money and you are deciding whether to carry an umbrella. If you would carry it anyway, the forecast is worthless to you; it is valuable only if some answer would change what you do. The value of information is the expected value of your best decision with it, minus the expected value of your best decision without it. Work out both decision trees separately and subtract. Never value information by the size of the payout it relates to.

Why is it not worth Rs 4 or Rs 5?

Rs 4 is what you make when the card is red, but it is red only half the time. Rs 5 is half the payout, which ignores the Rs 6 you pay to play. The information saves you from the losing half of the bet and lets you keep the winning half, and that is worth half of Rs 4, which is Rs 2. Pay more than Rs 2 and you would do better declining the offer of information and declining the bet.

When is information worth the most?

Vary the price of the bet. At a price of 5 you are exactly indifferent blind, and the information is worth 2.50, its maximum; at a price of 0 you would always play, and it is worth 0. Information is valuable when you are close to indifferent and the decision could go either way. The formula also has the shape of an option payoff: knowing first lets you exercise only when it pays, which is why traders talk about paying for optionality and paying for information in the same breath.

About 5.3% to 16.7%. The standard error of a 30-year average is 16% divided by the square root of 30, 2.92 points. A 95% interval is 1.96 standard errors either side: 11% plus or minus 5.7. With a t value for 29 degrees of freedom it is a touch wider, plus or minus 6.0. Thirty years of data still leave the expected return very uncertain.

Why is the band so wide after thirty years?

Imagine judging a new cricketer's true batting average from a handful of innings. Scores swing wildly from one innings to the next, so a few innings tell you little. The precision of an average grows only with the square root of the number of observations, and yearly returns swing by 16 points, so 30 years give a standard error of about 2.9 points. That is large next to an average of 11%: the true figure could plausibly be 6% or 16%.

How do you set it up in the room?

State the assumption, then compute. Treat the 30 annual returns as independent draws with a standard deviation of 16%, so the sample average has a standard error of 16 over root 30. Root 30 is about 5.48, so the standard error is 2.92. Multiply by 1.96: 5.73. The interval is 5.3% to 16.7%. If the interviewer pushes, note that with only 30 observations a t distributionThe distribution used for an average when the standard deviation is estimated from the same small sample; it has fatter tails than the normal. with 29 degrees of freedom gives a multiplier of about 2.045, widening the band slightly.

What limitation should you add?

Halving the band needs four times the data: 120 years still only pins the average to within about 2.9 points, and markets change over such spans. Returns are also not quite independent from year to year, fat tails make the normal multiplier optimistic, and the arithmetic average overstates the compound growth rate. The practical lesson is that expected returns are the hardest input in finance to estimate, far harder than volatility, which is why many quant processes lean on risk estimates and treat return forecasts with caution.

f'(x) = x to the x times (ln x + 1), and the minimum is at x = 1/e, about 0.368, where f is about 0.692. Take logs: ln f = x ln x. Differentiating, f'/f = ln x + 1, so f' = x to the x (ln x + 1). The derivative is zero when ln x = -1, that is x = 1/e, negative before it and positive after, so this is a minimum.

Why do both standard rules fail?

The power rule, n x to the (n - 1), treats the exponent as fixed; the exponential rule, a to the x times ln a, treats the base as fixed. In x to the x both the base and the exponent move, so neither rule applies on its own, and each one gives half of the right answer. Indeed the correct derivative is the sum of the two: x times x to the (x - 1), which is x to the x, plus x to the x ln x. That sum is a quick check on your final answer.

How does taking logs make it routine?

Think of converting a messy multiplication into addition before doing it, the way a slide rule does. Write ln f = x ln x; the right-hand side is a product of two simple functions, and the product rule gives ln x + x times 1/x = ln x + 1. The left side differentiates to f'/f by the chain rule, so f' = f (ln x + 1). This is logarithmic differentiationDifferentiating the logarithm of a function instead of the function, then multiplying back; useful when the variable sits in an exponent., and it works for any function of the form g(x) to the h(x).

How do you confirm it is a minimum and state the value?

Check the sign of ln x + 1, since x to the x is always positive. For x below 1/e, ln x is below -1 and the slope is negative; above 1/e it is positive, so the function falls and then rises: a minimum. The value is (1/e) to the (1/e) = e to the (-1/e), about 0.692. Also say what happens at the edges: as x shrinks towards zero, x ln x tends to zero, so x to the x tends to 1, and at x = 1 it is exactly 1 again.

They leave in the order 2, 4, 1, 3. Person 1 takes 4 and rejoins with 3; person 2 takes 3 and leaves; person 3 takes 4 and rejoins with 6; person 4 takes 2 and leaves. Then person 1 takes 3 and leaves, and person 3 needs two more visits. The shortcut: each person leaves in round amount divided by 4, rounded up, and ties go to whoever stood first.

How do you simulate it cleanly?

Model the line as a queueA first-in, first-out list: items join at the back and leave from the front, as in a real line. of pairs, person and amount still wanted. Pop the front, subtract the lesser of the cap and what they still want, and if anything is left push them onto the back; otherwise record them as leaving. The four people take seven visits in all. This is the answer most interviewers expect first, and it is correct, but its cost grows with the total number of visits, which is the sum of each amount over the cap.

Is there a faster way than simulating?

Yes. Think of a canteen that serves one plate per person per pass: someone wanting three plates leaves on the third pass, whatever the others want. Person i leaves in round ceiling(a_i / k), and within a round the queue keeps its original order, so the exit order is simply the people sorted by their round number, ties broken by starting position. Here the rounds are 2, 1, 3 and 1, which sorts to 2, 4, 1, 3. That costs n log n, however large the amounts are, instead of the number of visits.

Why does queue order survive between rounds?

Everyone still waiting after a round rejoins in the same relative order they were served, because the queue is first in, first out. So round two serves the survivors of round one in their original order, and so on. That invariant is what lets you replace the simulation with a sort, and saying it out loud is what separates an answer that works from one you can defend. If a very large cap or tiny amounts made most people finish in round one, the sort still costs n log n, and a counting sort on round numbers can make it linear.

90%. Each die starts at one in three. The chance of two sixes is 1/36 for the fair die, 1/4 for the loaded die and zero for the die with no six. Weight each by its prior: 1/108 for the fair die, 1/12 for the loaded die, nothing for the third. The loaded die's weight is nine times the fair die's, so its probability is 9/10.

What does the die that never shows six do to the answer?

A neighbour tells you a red car blocked the gate this morning. If one of your suspects owns only a blue scooter, that suspect is out, however likely they looked before. A hypothesis that cannot produce the evidence gets zero weight afterwards, no matter what its prior was. The no-six die could never give two sixes, so it drops out, and the question becomes a contest between the fair die and the loaded die, which started level at one third each.

How much does each surviving die's likelihood count?

Now compare how easily each remaining die produces what you saw. The fair die gives two sixes 1 time in 36. The loaded die gives a six half the time, so two in a row 1 time in 4. With equal priors, the posterior odds are just the ratio of the likelihoodsThe probability of the observed evidence under each hypothesis, before any prior is applied.: 1/4 against 1/36, which is 9 to 1. Nine parts in ten is 90%.

Check it by counting, the safer habit under pressure. Imagine 108 rounds of drawing a die and rolling it twice, 36 rounds with each die. The fair die gives two sixes once, the loaded die 9 times, the no-six die never. Of the 10 double sixes, 9 came from the loaded die, and the prior of one third cancels because every die got the same number of rounds. The loaded die's other faces, 1 in 10 each, never enter, because only sixes were seen.

161/36, about Rs 4.47. The larger face equals k in 2k minus 1 of the 36 equally likely outcomes: 1, 3, 5, 7, 9 and 11 cells for k from 1 to 6. Multiply each value by its count and add: 1 + 6 + 15 + 28 + 45 + 66 = 161. Divided by 36, that is 4.47, almost a full point above a single die's 3.5.

Why is the answer well above 3.5?

When two friends each suggest a restaurant and you always go with the better rated one, your average dinner beats either friend's average. Taking the larger of two draws pulls the result toward the top, because a low result survives only if both draws are low. A payout of 1 needs both dice on 1, one cell in 36. A payout of 6 needs just one six, and 11 cells in 36 contain at least one.

How do you count the cells without listing all 36?

Count the outcomes where the larger face is at most k: both dice must be at most k, which is k squared cells. The cells where the larger face is exactly k are k squared minus (k - 1) squared, which is 2k - 1. That is the L-shaped band in the grid: a new row and a new column, sharing one corner cell. The bands are 1, 3, 5, 7, 9 and 11, and they add to 36, which is the check that nothing was double counted.

A second route helps when the interviewer changes the dice. Add up the chance that the payout reaches each level: the payout is at least k unless both dice are below k, so the sum of 1 minus (k - 1) squared over 36, for k from 1 to 6, is 6 minus 55/36, which is 161/36 again. Two methods landing on the same fraction is the check worth saying out loud. By symmetry the smaller face averages 7 minus 4.47, about 2.53, and with three dice the larger face rises to 4.96.