Which Coin Pattern Shows Up First
Updated
Problem statement
You flip a fair coin again and again and write down each result: H for heads and T for tails.
You are given two patterns, first and second. You stop as soon as your most recent flips spell out one of the two patterns. For example, with patterns HHT and HTT, the flips T H T H H T stop at the sixth flip, because the last three flips are HHT.
Return the probability that first shows up before second. The patterns are different and neither one appears inside the other, so exactly one of them comes first. Your answer is accepted if its absolute error or its relative error is at most 10^-9.
Function
firstPatternWinsProbability(first: String, second: String) → doubleExamples
Example 1
first = "HHT"second = "HTT"return = 0.6666666666666666This is the first interview pair. Flips of T before the first H do not help either pattern, so wait for the first H.
From H: if the next flip is H, you have HH. More heads keep HH, and the first tail completes HHT, so first wins for sure. If the next flip is T, you have HT. Then T completes HTT and second wins, while H takes you back to H.
So the win chance p from H satisfies p = 1/2 × 1 + 1/2 × (1/2 × 0 + 1/2 × p), which gives p = 2/3, about 0.6667.
Example 2
first = "HTH"second = "HHT"return = 0.3333333333333333This is the second interview pair. Again wait for the first H.
From H: another H gives HH, and from there HHT always comes first, so first loses. A T gives HT. Then H completes HTH and wins, while T gives HTT, which helps neither pattern, so you are back at the start.
The win chance p satisfies p = 1/2 × 0 + 1/2 × (1/2 × 1 + 1/2 × p), so p = 1/3.
Example 3
first = "THH"second = "HHH"return = 0.875HHH can only win if the first three flips are all heads, which has probability 1/8. Otherwise a tail comes before any HHH, and then the first HHH must follow a tail, so THH appears first. The answer is 1 - 1/8 = 7/8.
Constraints
1 <= first.length, second.length <= 20firstandsecondcontain only the letters'H'and'T'.firstandsecondare different, and neither one appears inside the other.
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
- Random Points Inside One ArcPHONE SCREEN · Seen Jan 2025
Similar questions at other companies
- Evaluate an Arithmetic Expression Written in WordsBrex · PHONE SCREEN
- Integer to English Words in USD and INR StylesVeeam · PHONE SCREEN
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions
- Basic Calculator IISnap Inc. · PHONE SCREENSnap Inc. interview questions
- Bit at an Index After Repeated Binary ExpansionAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Text Embedding and Vector SearchNike, Inc. · PHONE SCREEN · ONSITE INTERVIEWNike, Inc. interview questions
- Add Signed Character ArraysByteDance · PHONE SCREENByteDance interview questions
- Per-Segment SpeedingOnePay · PHONE SCREENOnePay interview questions
- Evaluate a Flat Expression or Report Invalid InputMeta · PHONE SCREENMeta interview questions
- Find Accounts with Negative Converted BalancesStripe · PHONE SCREENStripe interview questions