Quant puzzles, solved step by step

Puzzles: 100
Traced to a firm: 71
Topics: 12
Hard: 30

Showing 1–8 of 8 · filtered from 100Clear filters

003Speed round, ninety seconds: you draw three cards from a well-shuffled 52-card deck without replacement. What is the probability that all three are of different suits?Counting and combinatoricsWarm upQuant tradingProp trading firms
Try it first
Closest answer, fast.
Show the worked solution
About 39.8%. The first card can be anything. The second must come from one of the three other suits: 39 of the 51 cards left. The third must avoid both suits already seen: 26 of the 50 left. Multiply: 39/51 x 26/50 = 1,014/2,550, just under 40%. Drawing with replacement would give 3/4 x 1/2 = 37.5%.
Why does the first card cost nothing?
Picture three guests arriving at a party with four dress colours in the wardrobe, and you want no two to match. The first guest cannot clash with anyone. A condition about the cards differing only bites from the second card on, so the first card contributes a factor of 1 and you start counting from card two. Candidates who write 13/52 for the first card have fixed a particular suit and then have to multiply by the number of suit orders to recover, which is where the slips happen.
The first card is free, the second must avoid one used suit with 39 of 51 cards still good, and the third must avoid two with 26 of 50 still good, so three different suits happen with probability 39.8%.
How do you check it a second way in the time?
Count unordered hands. Choose which three suits appear, 4 ways, then one card from each, 13 cubed, and divide by all three-card hands, 52 choose 3. That is 4 x 2,197 = 8,788 over 22,100, which is the same 0.3976. In a speed round you do not have time for both, but knowing the counting route exists lets you sanity-check the product: 0.765 x 0.52 is a little under 0.40.
The relationship
$P = \frac{39}{51}\cdot\frac{26}{50} = \frac{4\cdot 13^3}{\binom{52}{3}} = \frac{8788}{22100} \approx 0.398$
39/51 cards of a new suit among those left after one draw
26/50 cards of a third suit after two draws
\binom{52}{3} the number of possible three-card hands
What it says in wordsSequential dodging and direct counting give the same 39.8%.
What is a speed round actually testing?
Thirty questions in forty-five minutes cannot all be worked in full. The skill being tested is choosing the shortest correct route and estimating the product well enough to pick from the options. Here, 39/51 is about 0.76 and 26/50 is 0.52; 0.76 x 0.52 is about 0.40, which eliminates every other option before you finish the exact fraction.
Where candidates lose it
The fast wrong answer is 37.5%, from treating the draws as if cards go back in the deck. It feels close enough, and in a multiple choice round it sits right next to the correct option on purpose.
The other slip is starting with 13/52 for the first card, which silently fixes that card's suit. You then need to multiply by 4 for the suit choice, and under time pressure most people forget.
What the interviewer asks next
What is the probability that four cards are all of different suits?
What is the probability that three cards share a suit?
Draw until you have seen all four suits. What is the expected number of cards?
015You roll three fair dice. Is a total of 9 or a total of 10 more likely, given that each can be written as exactly six unordered combinations of three faces?Counting and combinatoricsCoreQuant tradingProp trading firms
Try it first
Which total is more likely?
Show the worked solution
10 is more likely: 27 ways out of 216 against 25. The equally likely outcomes are the 216 ordered rolls, not the unordered combinations. A combination of three different faces covers six ordered rolls, one with a pair covers three, and a triple covers one. Total 9 includes 3 + 3 + 3, which counts once, and one fewer all-different combination, so it loses two orderings to 10.
Why are combinations the wrong thing to count?
Think of dealing two cards and asking whether a pair of kings or a king with a queen is more likely. There is one combination of each, but king and queen can arrive in either order while two kings are just two kings. Probability comes from counting outcomes that are equally likely, and with dice those are the ordered rolls: first die, second die, third die, 6 x 6 x 6 = 216 of them. Unordered combinations bundle different numbers of those outcomes, so counting combinations gives the wrong weights.
Totals of 9 and 10 each have six unordered combinations, but weighting each combination by its number of orderings gives 27 of 216 rolls for 10 against 25 for 9, mostly because 9 includes the triple 3, 3, 3, which happens only one way.
How do you count the orderings fast?
Classify each combination by its repeats. Three different faces give 3! = 6 orders, a pair gives 3 orders, one for each position of the odd die, and a triple gives 1. For 9: 1 2 6, 1 3 5 and 2 3 4 are all different, 18; 1 4 4 and 2 2 5 are pairs, 6; 3 3 3 is a triple, 1; total 25. For 10: 1 3 6, 1 4 5 and 2 3 5 give 18; 2 2 6, 2 4 4 and 3 3 4 give 9; total 27. So 10 comes up 12.5% of the time and 9 only 11.6%.
The relationship
$P(9) = \frac{3\cdot 6 + 2\cdot 3 + 1}{216} = \frac{25}{216} \qquad P(10) = \frac{3\cdot 6 + 3\cdot 3}{216} = \frac{27}{216}$
6, 3, 1 the orderings of an all-different, a pair and a triple combination
216 the ordered outcomes of three dice
What it says in wordsWeight each combination by its orderings and 10 beats 9 by two rolls in 216.
Is there a shortcut that avoids listing?
Yes: symmetry. Replacing each face x by 7 - x maps a total of t to 21 - t, so the distribution of three dice is symmetric about 10.5, and 10 and 11 are the two most likely totals, each 27/216. Anything further from 10.5, including 9, must be less likely or equal; a quick count confirms it is 25. Historically this is the question gamblers put to Galileo, who answered it by counting ordered outcomes, which is still the method.
Where candidates lose it
The trap is the question's own framing: six combinations each invites the answer that the totals are equally likely. The interviewer wants you to reject the framing, not accept it.
The second loss is listing all 216 rolls, or writing out every ordering. Classifying by repeats, six, three or one, gets both totals in under a minute.
What the interviewer asks next
What is the most likely total with four dice, and its probability?
What is P(total is 9) with two dice, and why does 9 behave differently?
How many ordered outcomes of three dice sum to 7?
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.
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(\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
043A 3 x 3 x 3 cube is painted on the outside and cut into 27 small cubes. How many small cubes have 3, 2, 1 and 0 painted faces? You pick a small cube at random and roll it like a die: what is the probability the top face is painted?Counting and combinatoricsCoreJane StreetNew York · 2026
Try it first
What is the probability the top face is painted?
Show the worked solution
8 cubes have 3 painted faces, 12 have 2, 6 have 1 and 1 has none; the chance the top face is painted is exactly 1/3. Corners carry three, edge middles two, face centres one, and the core none. Picking a random cube and rolling it picks a random small face out of 27 x 6 = 162. The painted ones are the big cube's surface, 6 x 9 = 54, so the probability is 54/162 = 1/3.
Where do the 8, 12, 6 and 1 come from?
Think of a Rubik's cube: its pieces are corners, edges and centres, plus a hidden core. A small cube's painted faces equal the number of outer walls it touches: a corner touches three, an edge middle two, a face centre one, the core none. A cube has 8 corners, 12 edges with one middle piece each, and 6 faces with one centre each. That accounts for 8 + 12 + 6 = 26 cubes; the 27th is the core.
Slicing the cube into three layers shows 8 corner cubes with three painted faces, 12 edge cubes with two, 6 face centres with one and a single unpainted core, which together carry 54 painted faces out of 162, exactly one third.
Why is the roll probability exactly one third?
Do it the long way first: weight each cube type by its share of cubes and its share of painted faces. 8/27 x 3/6 + 12/27 x 2/6 + 6/27 x 1/6 + 1/27 x 0 = (24 + 24 + 6)/162 = 54/162. Then notice the shortcut: a random cube with a random face up is a uniform pick from all 162 small faces, and the painted small faces are exactly the big cube's surface, 6 x 9 = 54. That gives 1/3 without any case split, and it works for any size: an n x n x n cube gives 6n squared over 6n cubed, which is 1/n.
The relationship
$P(\text{painted top}) = \frac{8\cdot 3 + 12\cdot 2 + 6\cdot 1 + 1\cdot 0}{27\cdot 6} = \frac{54}{162} = \frac13$
8, 12, 6, 1 numbers of corner, edge, face-centre and core cubes
3, 2, 1, 0 painted faces on each type
27 x 6 all small faces, each equally likely to land on top
What it says in wordsCount painted small faces over all small faces, because the roll makes every small face equally likely.
Interviewers use the second part to see whether you look for the structure before the arithmetic. Counting faces instead of cubes turns a four-case weighted average into one division. Say both routes: the case split proves you can count, the face count proves you can see.
Where candidates lose it
The common loss is answering about cubes when the question is about faces: 26 of 27 cubes have paint, so candidates say 26/27, forgetting that a painted cube still shows an unpainted face most of the time.
The second is miscounting edges, using 8 or 24 instead of 12. Say the cube's shape out loud, 8 corners, 12 edges, 6 faces, and check 8 + 12 + 6 + 1 = 27.
What the interviewer asks next
For a 4 x 4 x 4 cube, how many small cubes have exactly two painted faces?
You roll a random small cube and see a painted top. What is the chance it is a corner cube?
For which n does an n x n x n cube have more unpainted small cubes than painted ones?
Asked at Jane Street, Engineering, New York, 2026 (Wall Street Oasis): How you got to the answer matters even if you got the question right. Strawberry question + 3x3 cube question
055In how many ways can three positive integers, in order, sum to 10? To 11? Give the general formula for any total n of at least 3.Counting and combinatoricsWarm upOld Mission CapitalNew York · 2018
Try it first
How many ordered triples of positive integers sum to 10?
Show the worked solution
36 for 10, 45 for 11, and (n - 1)(n - 2)/2 in general. Write n as a row of n stars. Splitting it into three positive parts means placing two bars in two different gaps among the n - 1 gaps between stars. Each choice gives exactly one ordered triple, so the count is n - 1 choose 2: 9 choose 2 = 36 and 10 choose 2 = 45.
Why turn the sum into a row of stars?
Think of ten sweets in a line to be shared among three children in order, each getting at least one. You do not need to decide amounts; you only need to decide where to cut the line. Every ordered split of n into three positive parts is exactly one choice of two cut points among the n - 1 gaps between items, and every choice of two gaps gives a valid split. That one-to-one match is the whole argument, and it is what the interviewer wants to hear you state.
Ten stars have nine gaps between them; putting bars in two different gaps, here gaps 3 and 7, splits the stars into 3, 4 and 3, so the ordered triples summing to 10 number 9 choose 2, which is 36, and those summing to 11 number 45.
What if the interviewer meant something slightly different?
Ask two quick questions before you answer: are zeros allowed, and does order matter. The word numbers hides three different questions, and each has a different count. If zeros are allowed, add one to each part first so they become positive and sum to n + 3: for 10 that is 12 choose 2 = 66. If order does not matter, the count for 10 drops to 8 unordered triples, and for 11 to 10, which you would list rather than compute. Asking which one is wanted takes five seconds and is part of the answer.
The relationship
$\#\{(a,b,c)\ge 1:\ a+b+c=n\} = \binom{n-1}{2} = \frac{(n-1)(n-2)}{2} \qquad \binom{9}{2}=36,\ \ \binom{10}{2}=45$
n - 1 the number of gaps between n stars
2 the number of bars needed to make three parts
What it says in wordsChoose two of the gaps between the stars; each choice is one ordered triple.
How do you check 36 without the formula?
Fix the first number and count the rest. If the first part is a, the other two must sum to 10 - a, which can be done in 9 - a ordered ways. For a from 1 to 8 that is 8 + 7 + ... + 1 = 36. The counts for each total are the triangular numbers 1, 3, 6, 10 and so on, which is the same formula read another way.
Where candidates lose it
The fast wrong answer comes from listing unordered triples such as 1, 1, 8 and 2, 3, 5, getting 8, and not noticing the question counts order. The opposite slip is counting zeros and getting 66.
Both are avoided by one clarifying question at the start. Then give the stars and bars picture in a sentence, because the interviewer's next question is usually four or five parts.
What the interviewer asks next
How many ways can four positive integers sum to 10?
How many ordered triples of non-negative integers sum to 10?
How many ordered triples of positive integers sum to 10 with every part at most 5?
Asked at Old Mission Capital, Finance, New York, 2018 (Wall Street Oasis): In how many ways can you have three numbers that sum to 10? What about 11?
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 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(\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_n the 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?
080A path moves one unit right or one unit up at a time, from (0,0) to (6,4). Every shortest path is equally likely. The point (3,2) is blocked. How many valid paths remain, and what is the probability that a random shortest path avoids the blocked point?Counting and combinatoricsCoreSusquehanna International GroupLondon · 2026
Try it first
How many of the shortest paths pass through (3,2)?
Show the worked solution
110 paths avoid the block, so the probability is 110/210 = 11/21, about 52.4%. All shortest paths use 6 rights and 4 ups in some order: C(10,4) = 210. Paths through (3,2) combine 10 ways in with 10 ways out, 100 in all. Subtract, and 110 survive.
How do you count all the shortest paths?
A shortest path is a string of 10 moves with exactly 6 rights and 4 ups, like a ten-letter word made of R and U. Choosing which 4 of the 10 slots are ups fixes the path completely, so there are C(10,4) = 210 shortest paths. That is the whole sample space, and every one of those strings is equally likely by the question's rule.
Why multiply for the paths through the blocked point?
Think of a trip from home to the office with a stop at a coffee shop. If there are 10 routes to the shop and 10 routes from the shop to the office, there are 10 x 10 = 100 full trips, because every first half pairs with every second half. Paths through (3,2) split the same way: C(5,2) = 10 in and C(5,2) = 10 out, so 100 of the 210 pass through the block. Subtract and 110 remain.
Adding the count from the left and the count from below at every point, with the blocked point set to zero, gives 110 paths at (6,4), which matches 210 total paths minus the 100 that pass through (3,2).
The relationship
$\binom{10}{4} - \binom{5}{2}\binom{5}{2} = 210 - 100 = 110, \qquad P = \frac{110}{210} = \frac{11}{21}$
C(10,4) ways to place 4 ups among 10 moves
C(5,2) ways to place 2 ups among the 5 moves on each side of the block
What it says in wordsCount everything, subtract the paths forced through the block, and divide by everything.
The grid method in the figure is the check, and it is also what you would code. Each point's count is the count from the left plus the count from below, because the last step into any point came from one of those two neighbours. Setting the block to zero removes every path through it automatically, and the same method handles several blocks, where the subtraction formula needs inclusion and exclusion.
Does the answer change if the walker flips a coin at each step?
Yes, and interviewers often ask this next. If the walker flips a fair coin for right or up at each step, any visit to (3,2) happens on move five, and a walker still able to get there has not yet touched the top or right edge, so all five of those moves were free coin flips. The chance of standing on (3,2) after five flips is C(5,2)/2^5 = 10/32 = 5/16, so the coin-flip walker avoids the block with probability 11/16, about 68.8%, well above 11/21. Choosing uniformly among complete paths is not the same as flipping coins: conditioning on the end point (6,4) pulls paths towards the diagonal that leads there, and (3,2) sits on it. Say which model the question means before you answer.
Where candidates lose it
The usual slip is adding the ways in and out, 10 + 10 = 20, instead of multiplying. Paths through a point are pairs of half-paths, and pairs multiply.
The second loss is quietly switching models, treating each step as a coin flip while using the uniform-path count, or the reverse. State that the question picks among all 210 shortest paths with equal chance, and the answer 11/21 follows.
What the interviewer asks next
What if both (3,2) and (2,3) are blocked?
How many shortest paths pass through (3,2) or (4,3), counting each path once?
How many paths from (0,0) to (6,4) never go above the line y = x?
Asked at Susquehanna International Group, Quantitative Research, London, 2026 (Wall Street Oasis): Probability about crossing from (0,0) to (6,4). Some point in the middle cannot pass through
092You climb a staircase of 10 steps, taking either one step or two steps at a time. In how many different ways can you reach the top?Counting and combinatoricsWarm upTower Research CapitalNew York · 2012
Try it first
Pick the number of ways.
Show the worked solution
89 ways. Split by the last move: you arrive at step 10 with a single from step 9 or a double from step 8, so ways(10) = ways(9) + ways(8). With 1 way to reach step 1 and 2 ways to reach step 2, the counts run 1, 2, 3, 5, 8, 13, 21, 34, 55, 89: the Fibonacci numbers, with 89 at the top.
How do you count without listing every route?
Imagine a friend at the top of the stairs asks how you got there. There is one thing you can say for certain about your last move: it was either a single from step 9 or a double from step 8, and never both. Every route to step 10 is a route to step 9 followed by a single, or a route to step 8 followed by a double, so the count at step 10 is the sum of the counts at steps 9 and 8. The same holds at every step, which turns the puzzle into a running sum.
Writing the number of ways on each step, each step is the sum of the two below it, so the counts follow the Fibonacci sequence and step 10 collects 55 routes ending with a single and 34 ending with a double, 89 in all.
The relationship
$w(n) = w(n-1) + w(n-2), \qquad w(1) = 1,\; w(2) = 2 \;\Rightarrow\; w(10) = 89$
w(n) the number of ways to reach step n
w(n-1) routes whose last move is a single step
w(n-2) routes whose last move is a double step
What it says in wordsSort every route by its last move; the two groups do not overlap and together cover everything.
Can you check 89 a second way?
Count by how many double steps you take. With k doubles, you make 10 - 2k singles, so 10 - k moves in all, and you only have to choose which k of those moves are the doubles. Summing the binomial counts over k = 0 to 5 gives 1 + 9 + 28 + 35 + 15 + 1 = 89, the same answer by a completely different road. Saying a second check aloud is worth more than the answer itself in a first round, because it shows you do not trust a pattern you have not tested.
Double steps k Moves in total Ways to place the doubles
0 10 C(10, 0) = 1
1 9 C(9, 1) = 9
2 8 C(8, 2) = 28
3 7 C(7, 3) = 35
4 6 C(6, 4) = 15
5 5 C(5, 5) = 1
total 89
Counting routes by the number of double steps gives 89 again, which confirms the Fibonacci running sum.
What does the interviewer usually ask next?
Two things. First, allow steps of one, two or three: the same last-move argument gives w(n) = w(n - 1) + w(n - 2) + w(n - 3), and the count for ten steps becomes 274. Second, the coding version. A recursive function that calls itself for n - 1 and n - 2 recomputes the same steps again and again: for 30 steps it makes 1,664,079 calls to return 1,346,269. Storing each step's count once, or just keeping the last two numbers in a loop, does the job in 30 additions. The counts grow by about 1.618, the golden ratio, per step, which is the limitation of any approach that lists routes rather than counting them.
Where candidates lose it
The fast wrong answer is 2^10 = 1,024, treating each of ten stairs as a binary choice. A double step consumes two stairs, so routes have different numbers of moves and the choices are not ten independent coin flips.
The second loss is an off-by-one in the starting values, which lands on 55 or 144. Write the first three steps out by hand: 1 way to step 1, 2 ways to step 2, 3 ways to step 3. Anchor the sequence there and the tenth term is 89.
What the interviewer asks next
What if you can also take three steps at a time?
How many ways are there if step 5 is broken and cannot be stood on?
Write code that counts the ways for 1,000 steps without the recursion blowing up.
Asked at Tower Research Capital, Intern Interview -, New York, 2012 (Wall Street Oasis): How many ways can you jump up stairs if you can only jump either 1 or 2 steps?

39/51	cards of a new suit among those left after one draw
26/50	cards of a third suit after two draws
\binom{52}{3}	the number of possible three-card hands

6, 3, 1	the orderings of an all-different, a pair and a triple combination
216	the ordered outcomes of three dice

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

8, 12, 6, 1	numbers of corner, edge, face-centre and core cubes
3, 2, 1, 0	painted faces on each type
27 x 6	all small faces, each equally likely to land on top

Try it first

Why does the first card cost nothing?

How do you check it a second way in the time?

What is a speed round actually testing?

Where candidates lose it

What the interviewer asks next

Try it first

Why are combinations the wrong thing to count?

How do you count the orderings fast?

Is there a shortcut that avoids listing?

Where candidates lose it

What the interviewer asks next

Try it first

What does one pass actually do to each number?

Which orderings survive, and how do you count them?

Where candidates lose it

What the interviewer asks next

Try it first

Where do the 8, 12, 6 and 1 come from?

Why is the roll probability exactly one third?

Where candidates lose it

What the interviewer asks next

Try it first

Why turn the sum into a row of stars?

What if the interviewer meant something slightly different?

How do you check 36 without the formula?

Where candidates lose it

What the interviewer asks next

Try it first

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

How does inclusion and exclusion give 44?

How do you check 44 another way?

Where candidates lose it

What the interviewer asks next

Try it first

How do you count all the shortest paths?

Why multiply for the paths through the blocked point?

Does the answer change if the walker flips a coin at each step?

Where candidates lose it

What the interviewer asks next

Try it first

How do you count without listing every route?

Can you check 89 a second way?

What does the interviewer usually ask next?

Where candidates lose it

What the interviewer asks next