Quant puzzles, solved step by step

Puzzles
100
Traced to a firm
71
Topics
12
Hard
30
Topic
All topicsLogic and algorithmic reasoning10Conditional probability and Bayes7Counting and combinatorics8Continuous and geometric probability9Correlation, regression and linear algebra9Market making, betting and sizing9Expected value and optimal stopping9Statistics and estimation9Pricing, options and index maths7Games and strategic reasoning8Markov chains and random walks7Mental maths and number sense8
Level
AnyWarm upCoreHard
Source
AnyReported at a firmStandard
Showing 1–2 of 2 · filtered from 100Clear filters
  1. 031Take a random ordering of n distinct numbers and run exactly one left-to-right pass of bubble sort, swapping each adjacent pair that is out of order. What is the probability the list is fully sorted afterwards? Work it for n = 5.Counting and combinatoricsHardJump TradingChicago · 2018

    Try it first

    For n = 5, how likely is the list sorted after one pass?

    Show the worked solution

    2 to the power (n - 1) divided by n factorial, which is 16/120 = 2/15 for n = 5. One pass moves every number that is not carried rightwards exactly one place left. So the list ends sorted only if no number starts more than one place right of its final spot. Placing 1, then 2, then 3 and so on, each has two allowed spots and the largest takes the last one, giving 2 to the power (n - 1) orderings.

    What does one pass actually do to each number?

    Picture a queue at a ticket window where the tallest person seen so far keeps stepping back past anyone shorter. That person travels a long way to the right; everyone they pass shifts one step forward. In one pass, the running maximum is carried right until it meets something larger, and every number it passes moves exactly one place left. Nothing moves left by two in a single pass. That limit is the whole problem.

    One pass moves a number left by one place at most3 1 2 5 4: sorts in one pass3125412345beforeaftersorted: every number is home2 3 1 4 5: does not2314521345beforeafternot sorted: the 1 needed two stepsRule: each number may start at most one place right of its home.Place 1, 2, 3, 4 in turn: 2 allowed spots each. The 5 takes the last spot.2 x 2 x 2 x 2 x 1 = 16 orderings out of 5! = 12016/120 = 2/15
    In 3 1 2 5 4 every number starts at most one place right of its home, so one pass sorts it; in 2 3 1 4 5 the 1 starts two places right of home and ends one short, so only 16 of the 120 orderings of five numbers, 2 in 15, sort in one pass.

    Which orderings survive, and how do you count them?

    Because a number can shift left by one at most, the list sorts only if each number starts no more than one place right of its home. The converse also holds: when every number meets that condition, the pass carries each big number to exactly where it belongs. For five numbers, a brute-force check of all 120 orderings finds exactly the 16 that meet the condition, and all 16 sort.

    Now count them without listing. Place the numbers in increasing order. The 1 may sit in position 1 or 2. The 2 may sit anywhere in positions 1 to 3, one of which the 1 already took: two choices. The same holds for 3 and 4: each has k + 1 allowed spots, k - 1 of them already used by smaller numbers, so two choices each. The 5 fills the one position left. That is 2 x 2 x 2 x 2 x 1 = 16.

    The relationship
    P(sorted after one pass)=2 n−1n!n=5: 16120=215P(\text{sorted after one pass}) = \frac{2^{\,n-1}}{n!} \qquad n = 5:\ \frac{16}{120} = \frac{2}{15}
    2^(n-1)orderings where no number starts more than one place right of its home
    n!all orderings of n distinct numbers, equally likely
    What it says in wordsTwo choices for each number except the largest, over all possible orderings.

    Check small cases out loud: for n = 2 both orderings sort, 2 of 2; for n = 3 it is 4 of 6. The probability collapses fast, because n factorial outruns 2 to the power n: about 4.4% for n = 6 and 1.3% for n = 7.

    Where candidates lose it

    The common wrong start is to think one pass only fixes the largest number, and answer that the other n - 1 must already be sorted, which gives 1/(n - 1)! and 1/24 for n = 5. It misses that every passed number also moves left one place, which rescues many orderings.

    The other loss is guessing a rule from one example. State the one-step-left limit, derive the condition from it, then count by placing numbers in increasing order.

    What the interviewer asks next

    • What is the probability the list is sorted after two passes?
    • How many passes does bubble sort need on average for a random list of n numbers, roughly?
    • What if the pass runs right to left instead?

    Asked at Jump Trading, Research, Chicago, 2018 (Wall Street Oasis): one iteration of bubble sort, what's the probability that the array will be sorted

  2. 067Five traders drop their business cards in a bowl and each draws one at random. What is the probability that nobody draws their own card, and what does it approach as the number of traders grows?Counting and combinatoricsHardQuant tradingQuant research

    Try it first

    As the number of traders grows very large, the chance nobody gets their own card...

    Show the worked solution

    44/120, about 36.7%, and it tends to 1/e, about 36.8%. Count the orderings with no fixed point by inclusion and exclusion: 5! times (1 - 1 + 1/2! - 1/3! + 1/4! - 1/5!) = 44 of the 120 ways. The bracket is the start of the series for e^(-1), so the answer barely moves with the number of traders: it is within about 0.001 of 1/e at five people and closer still after that.

    Why does the answer not go to 0 or to 1?

    Think of a secret gift exchange at the office. With more people, each person is less likely to draw their own name, but there are more people who could. Each trader matches with chance 1/n and there are n traders, so the expected number of matches is exactly 1 at every size, and the chance of zero matches settles rather than vanishing. That is why the answer converges to a constant. It is also why the question is asked: it checks whether you can count an event defined by an absence, which needs inclusion and exclusion.

    The no-match chance settles at 1/e almost at once1/e = 0.3680.10.20.30.40.50n = 10/10.500n = 21/20.333n = 32/60.375n = 49/240.3667n = 544/1200.3681n = 6265/7200.3679n = 71854/50400.3679n = 814833/40320Five traders: 1 - 1 + 1/2 - 1/6 + 1/24 - 1/120 = 44/120Each extra trader adds a smaller correction, alternating in signNumber of traders, with derangements over all orderings
    The chance that nobody draws their own card swings above and below 1/e for small groups and is 44/120 = 0.3667 for five traders, against 1/e = 0.3679, so the number of traders barely matters once there are more than four.

    How does inclusion and exclusion give 44?

    Count the orderings where at least one trader gets their own card, then subtract. Fix any one trader: 4! orderings each, five traders, 120 in total, but that counts orderings with two fixed traders twice. Alternately subtract and add the counts with one, two, three, four and five traders fixed, and you get 120 - 120 + 60 - 20 + 5 - 1 = 44 orderings with no match. Dividing by 120 gives the probability as 1 - 1 + 1/2 - 1/6 + 1/24 - 1/120, and each term is the e^(-1) series truncated.

    The relationship
    P(no match)=Dnn!=∑k=0n(−1)kk!  ⟶  e−1D55!=44120=0.3667P(\text{no match}) = \frac{D_n}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!} \;\longrightarrow\; e^{-1} \qquad \frac{D_5}{5!} = \frac{44}{120} = 0.3667
    D_nthe number of orderings of n items with no item in its own place, a derangement count
    (-1)^k / k!the inclusion and exclusion term for k traders fixed
    What it says in wordsThe chance of no match is the alternating series for e to the minus 1, cut off after n terms.

    How do you check 44 another way?

    Use the recursion. Trader 1 takes some other trader's card, say trader j's, in n - 1 ways. Either j takes trader 1's card back, leaving n - 2 traders to derange, or j does not, which is the same as deranging n - 1 traders. So D(n) = (n - 1)(D(n - 1) + D(n - 2)), and from D(1) = 0 and D(2) = 1 you get 2, 9 and then 4 x (9 + 2) = 44. The number of matches is close to Poisson with mean 1 for any decent n, so exactly one match has about the same chance as none: for five traders it is 3/8 = 45/120.

    Where candidates lose it

    The trap is answering (4/5)^5, about 33%, by treating each trader's miss as independent. The draws are without replacement, so the events are linked; the right answer is close but not equal, and the reasoning is wrong.

    The second loss is getting 44/120 and stopping, when the follow-up about large groups is the point. Say the series is the start of e^(-1), so the answer is about 37% for any number of traders.

    What the interviewer asks next

    • What is the expected number of traders who draw their own card?
    • What is the probability that exactly one trader draws their own card?
    • With 100 traders, roughly what is the chance that at least two draw their own card?