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.

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.

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.

The next term is 312211. Each term describes the one before it, read aloud as runs of equal digits. 1 is one 1, written 11. 11 is two 1s, written 21. 21 is one 2 and one 1, written 1211. 111221 is three 1s, two 2s and one 1, written 312211. The sequence is known as look-and-say.

Why does no arithmetic rule fit?

Try the usual moves first, as you would with any number series: differences, ratios, squares. 11 minus 1 is 10 and 21 minus 11 is 10, but 1211 minus 21 is 1,190, and the pattern dies. When the gaps jump like that, stop treating the terms as quantities. These terms are strings of digits, not numbers, and the rule works on the digits one run at a time. Think of reading a phone number to someone on a bad line: you say double two, triple five. Each term here is the previous one said that way and then written down.

How do you produce the next term without slipping?

Mark the runs first, then speak each run as a count followed by its digit. The slip people make is merging two runs of the same digit that have something else between them. In 111221 the three 1s at the front and the single 1 at the end are separate runs, so the reading ends with one 1, not four 1s. Bracket the runs on paper or in your head and read left to right: three 1s, two 2s, one 1 gives 312211. One more turn for practice: 312211 reads one 3, one 1, two 2s, two 1s, which writes as 13112221.

What can you say about the sequence beyond the next term?

Two facts show you understand the rule rather than just ran it. First, starting from 1, no digit above 3 ever appears. Neighbouring runs always hold different digits, so four equal digits can never sit in a row, no run is longer than three, and no count above 3 is ever written. Second, the terms grow at a steady rate: the 40th term has 63,138 digits, and each term is about 1.30 times as long as the one before, a ratio John Conway studied. Run the rule in a short loop to see both, which is also the coding follow-up many firms ask next.

On a timed screen, the point of a question like this is speed at dropping a wrong frame. Candidates who spend a minute hunting for a formula lose the minute; candidates who ask what else the digits could be doing find the rule in seconds.

80 steps. At one step a second the climb takes 20 seconds; at two steps a second it takes 16. If the escalator moves v steps a second, the visible steps are 20 + 20v and also 32 + 16v. Setting them equal gives v = 3, so the escalator is 20 + 60 = 80 steps long, and the check 32 + 48 = 80 agrees.

What stays the same between the two walks?

On an airport moving walkway, walk slowly and the belt does most of the work; stride out and you do more of it yourself, but you reach the end sooner. The length of the walkway does not change. Every visible step is covered either by your legs or by the escalator, so your steps plus the escalator's movement during your climb always equal the same total. That fixed total is the unknown; the escalator's speed is the second unknown, and two walks give two equations.

How do you set up and solve the two equations?

Turn step counts into time first, because the escalator's contribution depends on time. The slow walk: 20 steps at one a second is 20 seconds. The fast walk: 32 steps at two a second is 16 seconds. The faster walk loses 4 seconds of escalator help and makes it up with 12 extra steps of its own, so the escalator moves 3 steps a second. Then the total is 20 + 20 x 3 = 80, and 32 + 16 x 3 = 80 confirms it.

Say the check aloud, then the sense check: the escalator at 3 steps a second is faster than either walking pace, which is plausible for a long escalator. If the question had you walking down an up escalator, the escalator's steps would subtract instead of add, and the same method still works. The trap in variants is mixing up steps and seconds; keep one unit for each quantity.

36 passengers started. Work backwards from 16 and undo each step with its inverse. Growing by a third multiplies by 4/3, so undo it by multiplying by 3/4: 16 becomes 12. Undo half getting off by doubling: 24. Then 3/4 again: 18. Double again: 36. Forwards it checks: 36, 18, 24, 12, 16.

Why work backwards instead of setting up an equation?

Retracing your route to find a dropped wallet works because you know where you ended up. Here you know the final count and every step, so the cheapest route is to run the film in reverse. Each step is a multiplication, so each can be undone by multiplying by its reciprocal, starting from the 16 and moving toward the depot. An equation also works, 4x/9 = 16, but the backward chain shows every intermediate count, which lets you check that each one is a whole number of people.

What is the inverse of growing by a third?

This is the step that catches people. Growing by a third means the new count is 4/3 of the old one. To undo a rise of a third you multiply by 3/4, which removes a quarter of the new number, not a third of it. Taking a third off 16 gives 10.67, which is not a whole person and is a red flag on its own. Multiplying by 3/4 gives 12, and 12 grown by a third is 16 again, so the step checks.

The whole-number check also tells you what starting counts are possible at all. Every intermediate count, x/2, 2x/3, x/3 and 4x/9, must be a whole number, so x must be a multiple of 18. A free consistency check is worth saying aloud: 36 is a multiple of 18, and every count on the way, 18, 24 and 12, is whole. The same structure appears on a desk whenever a number passes through several percentage changes: a price up 10% and then down 10% ends at 99% of where it began, and undoing a change always means dividing by the factor, never subtracting the percentage.

Two on a 4 by 4 board and 10 on a 5 by 5 board. Place one queen per row, trying columns left to right, and abandon a branch the moment the next row has no safe column. On 4 by 4 this visits 16 placements and finds columns 2, 4, 1, 3 and 3, 1, 4, 2. On 5 by 5 the same search visits 53 placements, against 3,125 boards for brute force.

How do you organise the search so it stays small?

Think of filling a seating plan for a wedding where some guests cannot sit near each other. You seat table by table, and the moment a table has no acceptable guest left you undo the previous choice instead of finishing a doomed plan. Backtracking builds the answer one decision at a time and abandons a partial answer as soon as it breaks a rule, so it never enumerates the boards that fail early. For queens, two rules come free from the structure: one queen per row, and one per column, which leaves only the diagonals to check at each step.

How does the 4 by 4 search actually run?

Start with the corner. A queen in column 1 of row 1 leaves row 2 only columns 3 and 4, and both paths run out of safe squares by row 3 or row 4, so no solution uses a corner queen. A queen in column 2 forces column 4 in row 2, then column 1 in row 3 and column 3 in row 4, which works. Columns 3 and 4 are mirror images of 2 and 1. So there are exactly two solutions, and they are reflections of each other. Saying the symmetry out loud halves the work and is exactly what an interviewer building up from a base case wants to hear.

What changes on 5 by 5, and how does the method scale?

The larger board has more room, and every row 1 column leads somewhere. The same search finds 10 solutions after 53 placements, while brute force over one queen per row would test 3,125 boards. On 8 by 8 it finds all 92 solutions in 2,056 placements out of 16,777,216 one-per-row boards. In code, keep three sets, used columns, used down-diagonals (row minus column) and used up-diagonals (row plus column), so each safety check is constant time.

200 miles. The car needs 100 / 50 = 2 hours to reach B, and the bird flies the whole time at 100 mph, so it covers 2 x 100 = 200 miles. Summing the zigzags gives the same answer: the first round trip is 133.3 miles, each later one is a third of the one before, and 133.3 / (1 - 1/3) = 200.

What is the question really asking you to count?

Think of a dog running back and forth between you and your front door while you walk home. You could trace every dash, or you could notice that the dog runs at a steady speed for exactly as long as your walk takes. Distance is speed times time, and the bird's flying time is fixed by the car, not by the zigzags, so the zigzag detail is a distraction. The car covers 100 miles at 50 mph in 2 hours; the bird flies at 100 mph for those same 2 hours. That is 200 miles, and it takes one sentence.

How do you check it by summing the zigzags?

The bird and car close the first 100 miles at a combined 150 mph, so they meet after 40 minutes, 33.3 miles from A. The bird flies back to B, 66.7 miles, arriving at 80 minutes, by which time the car is at 66.7 miles. Each round trip starts with the gap to the car one third of the previous gap, so the round trips form a geometric series with ratio 1/3. The first is 133.3 miles; the sum is 133.3 / (1 - 1/3) = 200. It agrees, and it shows why infinitely many turns still add to a finite distance.

Why do interviewers still ask a puzzle this well known?

Because the way you answer tells them more than the answer. A candidate who starts summing legs has reached for the first method that fits; a candidate who asks what quantity is fixed has found the invariant, and that is the habit the interviewer is hiring. The story about von Neumann summing the series in his head is part of the folklore; you get more credit for the one-line method and the series as a check. The same move, looking for a quantity that does not depend on the messy path, solves many expected-value and stopping questions on this page.

The two largest drawdowns are 130 to 80, 38.5%, and 120 to 90, 25.0%. Walk through the prices once, keeping the highest price seen so far. At each step the drawdown is one minus price over that running peak; the maximum drawdown is the largest value seen. For the n largest, close an episode each time a new high is set, record its trough, and sort the episodes.

What exactly is a drawdown measured from?

Think of a hiker measuring how far below the highest point reached so far she has dropped. A drop only counts from a summit already climbed, not from a peak further along the trail. A drawdown is the fall from the running maximum to a later price, so the order of the prices matters and the overall high and low cannot simply be paired. Here the 140 comes after the 80, so the tempting 42.9% never happened.

How do you get the n largest drawdowns rather than just the worst?

Split the path into episodes. An episode opens at a running peak and closes when the price makes a new high; its size is the fall from that peak to the lowest price inside it. Here the 120 episode closes when the price reaches 130, with a trough of 90, so it is 25%. The 130 episode closes at 140 with a trough of 80, 38.5%. The 140 episode never closes, so report it as open at 20.0%. Sorting the episodes gives the n largest in one pass plus a sort, O(N log N) at worst, and a heap of size n keeps it at O(N log n).

Say the edge cases, because the interviewer is testing code judgement as much as arithmetic. Two drawdowns from the same peak must not be counted twice: the fall to 80 and the later level of 110 belong to one episode. An episode still open at the end of the data is real risk and should be reported with a flag. And drawdown on a price series is not the same as drawdown on a strategy's cumulative P&L, where you would use the equity curve, not the price.

Days 5 to 7, the run 8, -2, 3, which totals Rs 9 lakh. Walk through the days keeping the best total of a run ending today: either today alone or today added to yesterday's best run, whichever is larger. Record the largest value you see. The run 2, 4 looks attractive but totals only 6, and the -9 day makes it pointless to carry anything before it.

How do you find the best run without checking every start and end day?

Picture walking along a road with toll booths that either pay you or charge you. You may choose where to start and stop collecting. If the purse you have carried from earlier booths is in the red, the sensible move is to drop it and start fresh at the next booth. A run ending today is worth extending from yesterday only if the best run ending yesterday is positive; if it is negative it can only drag today down, so today starts a new run. That rule looks at each day once. Checking every pair of start and end days means 28 runs for seven days and 31,375 for a trading year of 250 days.

Why does the tempting run 2, 4 lose?

Because one later day beats it on its own. After the -9, the best run ending on day 4 is 6 - 9 = -3, so the rule drops the past and day 5 starts fresh at 8. The -2 on day 6 dips the run to 6, but the 3 on day 7 lifts it to 9. The best run can contain a losing day: 8, -2, 3 beats 8 alone because the day after the loss more than repays it. A candidate who stops a run at the first red day misses this, and the brute-force check over all 28 runs confirms 9 is the maximum.

What edge cases does the interviewer probe?

Three. If every day is a loss, the answer should be the least bad single day, so start the best at the first day's value, not at zero, or you will report an empty run worth 0. To report which days, store the start index whenever you restart and copy it when you record a new best. The same pass with the signs flipped finds the worst run, here -9, the single -9 day. The limitation on a desk is that the best run in hindsight is a selected statistic: a strategy that is judged by its best stretch will always look better than it trades.