← Jane Street Interview Insights

Jane Street·Data Scientist·Technical Phone Screen·Intermediate

Intermediate
Jul 2026

Summary

Two pretty intense quant/algo questions for a Data Scientist role at Jane Street. Both required actual derivations and working code, not just hand-waving. The kind of interview where you either know the math or you don't.

Questions Asked (2)

Q1

You're at position k in a 100-person queue when a second checkout counter opens. Each other customer independently moves to the new queue with probability 1/2, and if you also move, your spot among the movers is uniformly random. Both counters serve at the same rate. Derive your expected wait time for staying vs. switching, and find the threshold k where switching becomes the better choice.

Algorithms & Data StructuresProduct Analytics & Metrics
Author's notes

This one took me a while to set up properly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the expected wait time as proportional to the number of people ahead of you in each queue. For staying, you have k-1 people ahead; for switching, the number of movers ahead of you is Binomial(k-1, 1/2) plus the movers from behind you, so compute the expected number of people ahead in the new queue. Compare the two expectations to find the threshold k where switching yields a shorter expected wait.

Pro tip: Emphasize that the expected wait time is linear in the number of people ahead, so you only need to compare expected queue lengths. Also note that the decision is based on expected values, but in practice you might consider risk or variance, though the question asks for expected wait.

1. Define the model

Let your position be k (1-indexed, so k-1 people ahead). Assume each of the other 99 customers independently moves to the new counter with probability 1/2. Both counters serve at the same rate, so wait time is proportional to the number of people ahead of you in your chosen queue.

2. Compute expected wait if you stay

If you stay, your position remains k, so the number of people ahead is k-1. Thus expected wait is proportional to k-1.

3. Compute expected wait if you switch

If you switch, your new position among the movers is uniformly random. The total number of movers is 1 (you) plus a Binomial(99, 1/2) number of others. The number of people ahead of you in the new queue is the number of movers who were originally ahead of you plus the number of movers from behind you who end up ahead of you due to the random ordering. By symmetry, the expected number of people ahead is (total movers - 1)/2. So expected wait is proportional to (E[total movers] - 1)/2 = (1 + 99/2 - 1)/2 = (99/2)/2 = 99/4 = 24.75.

4. Compare and find threshold

Set expected wait if stay < expected wait if switch: k-1 < 24.75 => k < 25.75. Since k is integer, switching is better when k <= 25? Wait, careful: if k-1 < 24.75, then k < 25.75, so k <= 25. But check: if k=25, stay wait=24, switch wait=24.75, so staying is better. Actually, switching is better when k-1 > 24.75, i.e., k > 25.75, so k >= 26. Let's re-evaluate: The expected number of people ahead if you switch is 24.75 regardless of k? That seems independent of k, which is suspicious. The derivation above assumed that the number of movers from behind you is Binomial(99-(k-1), 1/2) and from ahead is Binomial(k-1, 1/2). The total movers is 1 + Binomial(k-1,1/2) + Binomial(99-(k-1),1/2). The expected number of movers ahead of you in the new queue is not simply (total movers -1)/2 because the movers from ahead are all ahead of you, while movers from behind are randomly placed relative to you. So we need to compute E[number ahead] = E[number of movers from original ahead] + E[number of movers from original behind who are placed ahead of you]. The first term is (k-1)/2. The second term: if there are m movers from behind, your position among the m+1 movers (including you) is uniform, so expected number ahead from behind is m/2. So E[second term] = (1/2) * E[m] = (1/2) * ((99-(k-1))/2) = (100-k)/4. Thus total expected ahead = (k-1)/2 + (100-k)/4 = (2k-2 + 100 - k)/4 = (k+98)/4. Set this less than k-1: (k+98)/4 < k-1 => k+98 < 4k-4 => 102 < 3k => k > 34. So switching is better when k >= 35. Check k=34: stay=33, switch=(34+98)/4=132/4=33, equal. So threshold is k=35.

5. Interpret and conclude

For k <= 34, staying is at least as good as switching; for k >= 35, switching yields a shorter expected wait. The threshold is k=35.

Key Points to Mention

  • Linearity of expectation: wait time is proportional to number of people ahead.
  • Independence of each customer's decision (Binomial distribution).
  • Symmetry: your position among movers is uniformly random, so expected number of movers from behind who end up ahead is half of them.
  • The expected number of people ahead if you switch depends on k: (k+98)/4.
  • Comparison of expected waits leads to a linear inequality.
  • Threshold k=35: for k>=35, switching is better; for k<=34, staying is better (or equal at k=34).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q2

Given an integer n in cents and coin denominations of 1, 5, 10, 25, and 100 cents, count the number of distinct combinations (order doesn't matter) that sum to exactly n. Formalize it, design an algorithm for n up to 10,000, and analyze time and space complexity.

Algorithms & Data Structures
Author's notes

Classic DP, basically the unbounded knapsack variant.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by formalizing the problem as counting the number of ways to make change for n cents using an unlimited supply of coins with denominations {1,5,10,25,100}. Then present a dynamic programming solution where dp[i] represents the number of combinations to make i cents, iterating over each coin and updating dp in increasing order of i. Finally, analyze the time complexity as O(n * k) and space complexity as O(n), where k=5 is the number of denominations.

Pro tip: Mention that the order of iteration (coins outer, amount inner) ensures combinations are counted once, and note that for n=10,000 the DP table is small enough to fit in memory, but you could also optimize space to O(n) using a 1D array.

1. Formalize the problem

Define the input: n (integer, 0 ≤ n ≤ 10,000) and coin denominations D = {1,5,10,25,100}. Define the output: the number of distinct multisets of coins from D that sum to n.

2. Choose an algorithmic approach

Recognize this as a classic coin change problem (counting combinations). Use dynamic programming to avoid exponential enumeration, as brute force is infeasible for n=10,000.

3. Design the DP recurrence

Let dp[i] be the number of ways to make i cents. Initialize dp[0]=1. For each coin c in D, for i from c to n, update dp[i] += dp[i-c]. This counts each combination once.

4. Analyze complexity

Time complexity: O(n * |D|) = O(5n) = O(n). Space complexity: O(n) for the DP array. For n=10,000, this is efficient.

5. Consider edge cases and optimizations

Handle n=0 (return 1, the empty combination). Mention that the DP array can be of size n+1, and that using a 1D array is sufficient. Optionally, discuss that the result may exceed 32-bit integer for large n, so use 64-bit integers.

Key Points to Mention

  • Dynamic programming with a 1D array to count combinations, not permutations.
  • Iterating coins in the outer loop and amounts in the inner loop ensures each combination is counted once.
  • Time complexity O(n * k) and space complexity O(n), where k=5.
  • Base case: dp[0] = 1 (one way to make 0 cents: use no coins).
  • The result can be large; for n=10,000, the number of combinations is within 64-bit integer range.
  • Edge case: n=0 returns 1; n<0 is not possible per problem statement.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.