FastPrepExpected Number of Runs of Heads
Problems/Expected Number of Runs of Heads

Expected Number of Runs of Heads

Susquehanna International Group (SIG) logoSusquehanna International Group (SIG)● EasyNEW GRADINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Two SIG quant reports ask for the expected number of runs of heads when a biased coin is tossed 16 times. A new grad report from September 2022 (first phone round) says the author needed many hints and thinks this question cost them the round. An internship report from October 2021 (first round) adds a short example sequence to show how runs are counted. Neither report gives a value for the chance of heads.

Here, the number of tosses n (up to 10^6), the chance of heads p in whole percent, and a minimum run length k are inputs. The function returns the expected number of runs of heads that are at least k tosses long. k = 1 is the interview question, and 16 fair tosses is the first example. Answers within 10^-9 (absolute or relative) are accepted.

Our version is about 80% the same as the reported questions.

You toss a coin n times. Each toss is heads with probability p percent, independently of the other tosses.

A run of heads is a block of consecutive heads that cannot be made longer: the toss just before it and the toss just after it are tails, or do not exist. For example, HTTHHHTH has three runs of heads, of lengths 1, 3 and 1.

Return the expected number of runs of heads whose length is at least k.

Your answer is accepted if its absolute error or its relative error is at most 10^-9.

Function

expectedHeadRuns(n: int, p: int, k: int) → double

Examples

Example 1

n = 16p = 50k = 1return = 4.25

This is the interview question with a fair coin. With k = 1 every run counts, and each run has exactly one first toss.

A run starts at toss 1 when toss 1 is heads: chance 1/2. A run starts at a later toss i when toss i - 1 is tails and toss i is heads: chance 1/4, for each of the 15 tosses 2 to 16. The expected count is the sum of these chances: 1/2 + 15/4 = 4.25.

Example 2

n = 8p = 30k = 1return = 1.77

Heads now has chance 0.3. A run starts at toss 1 with chance 0.3, and at each of tosses 2 to 8 with chance 0.7 × 0.3 = 0.21. The answer is 0.3 + 7 × 0.21 = 1.77.

Example 3

n = 10p = 50k = 3return = 0.5625

Now only runs of at least 3 heads count. Such a run starts at toss 1 when tosses 1 to 3 are heads: chance 1/8. It starts at toss i for i = 2 to 8 when toss i - 1 is tails and tosses i to i + 2 are heads: chance 1/16 each. A run of 3 cannot start at toss 9 or 10. The answer is 1/8 + 7/16 = 9/16 = 0.5625.

Constraints

  • 1 <= k <= n <= 10^6
  • 0 <= p <= 100

More Susquehanna International Group (SIG) Phone Screen questions

  • Dice Sum That Is a Multiple of mPHONE SCREEN · Seen Nov 2026
  • Find Median from Data StreamPHONE SCREEN · Seen Nov 2026
  • Painting Arcs to Nearest Neighbors on a CirclePHONE SCREEN · Seen Sep 2026
  • Filter Movies by Inclusive Year RangePHONE SCREEN · Seen Jul 2026
  • Best Single Reroll for Five DicePHONE SCREEN · Seen Feb 2026
  • Catching the Bus to the MoviePHONE SCREEN · Seen Jan 2026
  • Two Dice Summing to a TargetPHONE SCREEN · Seen Jan 2026
  • Median of Uniform Draws in an IntervalPHONE SCREEN · Seen Oct 2025
  • One Number Is the Average of the Other TwoPHONE SCREEN · Seen Jun 2025
  • Which Coin Pattern Shows Up FirstPHONE SCREEN · Seen May 2025

Similar questions at other companies

  • Automation Pipeline, Part 1: Single WorkerPlaid · PHONE SCREENPlaid interview questions
  • Subtract Two Large Number StringsStackAdapt · PHONE SCREENStackAdapt interview questions
  • Circular Primes Below a LimitAmazon · PHONE SCREEN
  • Palindrome NumberKotak Mahindra Bank · PHONE SCREENKotak Mahindra Bank interview questions
  • Streaming AverageXantium · PHONE SCREEN
  • Fair Coin from a Biased CoinAnthropic · PHONE SCREENAnthropic interview questions
  • Stack Formula InterpreterTypeSafe AI · PHONE SCREEN
  • Employee Count Median, Mean and ModeClay · PHONE SCREEN
  • Newton Square Root to a Guaranteed ToleranceSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
  • Biased Coin: Probability of Exactly h HeadsAkuna Capital · PHONE SCREENAkuna Capital interview questions

Interview reports that mention this question

  • SIG Quant Research Intern Interviews: 60 Experiences
  • SIG Quant Researcher New Grad Interviews: 49 Experiences

Susquehanna International Group (SIG) interview experiences

  • SIG Quant Researcher Experienced Hire Interviews: 11 Experiences
  • SIG Quant Researcher Intern Interviews: 1 Experience
  • SIG Quant Second-Round Tech Screen: 1 Experience
All Susquehanna International Group (SIG) interview questionsSee Susquehanna International Group (SIG) hiring insights
Saved
class Solution {
    public double expectedHeadRuns(int n, int p, int k) {
        // Write your code here.
    }
}
Checking account…