Upstart·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

First round technical screen for a Data Scientist role at Upstart. One probability puzzle, felt more like a math exam than a data science interview, but I guess that's just how it goes there.

Questions Asked (1)

A fair coin is tossed 1,000 times. A new streak begins on the first toss and every time the result differs from the previous toss. What is the expected number of streaks? Then generalize: what if the coin lands heads with probability p?

Algorithms & Data Structures

Author's notes

I stared at this for longer than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use linearity of expectation by defining indicator variables for each toss that starts a new streak. For the fair coin, each toss after the first has probability 1/2 of starting a streak, so the expected number is 1 + 999*(1/2) = 500.5. For general p, the probability that a toss starts a streak is 2p(1-p), so the expected number is 1 + 999*2p(1-p).

Pro tip: Emphasize that linearity of expectation holds regardless of dependence between indicator variables, which is key here since streak starts are not independent. Also, sanity-check the result: for p=0.5, it matches the fair coin case, and for p=0 or 1, it gives 1 streak.

1. Define indicator variables

Let X_i be 1 if a new streak starts at toss i, for i=1,...,1000. Note X_1=1 always.

2. Compute probability for each indicator

For i>1, a new streak starts if toss i differs from toss i-1. For fair coin, P(X_i=1)=1/2. For general p, P(X_i=1)=P(H then T)+P(T then H)=p(1-p)+(1-p)p=2p(1-p).

3. Apply linearity of expectation

The expected number of streaks is E[sum X_i] = sum E[X_i] = 1 + 999 * P(X_i=1).

4. Plug in values and simplify

For fair coin: 1 + 999*(1/2) = 500.5. For general p: 1 + 999*2p(1-p).

5. Sanity check and interpret

Verify edge cases: p=0.5 gives 500.5, p=0 or 1 gives 1, and the maximum occurs at p=0.5. Discuss implications for data science.

Key Points to Mention

Linearity of expectation does not require independence.
Indicator variables simplify complex counting problems.
Probability of a change at each step is 2p(1-p) for general p.
The first toss always starts a streak, so it contributes 1 to the expectation.
Edge cases: p=0, p=1, and p=0.5 validate the formula.
The result is intuitive: more changes occur when the coin is fair.

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