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–1 of 1 · 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