Overlapping Random Time Windows
Updated
Problem statement
Two pop-up shops will each open once. Shop A opens at a moment chosen uniformly at random between time 0 and time days, and then stays open for exactly firstLength days. Shop B, independently, opens at a moment chosen uniformly at random between time 0 and time days, and stays open for exactly secondLength days.
Time is continuous, so a shop can open at any real moment in that range, not only at the start of a day. A shop may stay open past time days.
Return the probability that both shops are open at the same moment at some point. The chance that one shop opens at the exact moment the other one closes is 0, so it does not matter whether that case counts. Answers within 10^-9 of the exact value are accepted.
Function
overlapProbability(days: int, firstLength: int, secondLength: int) → doubleExamples
Example 1
days = 20firstLength = 4secondLength = 8return = 0.5This is the interview case. Put shop A's opening time on one axis and shop B's on the other, so every outcome is a point in a 20 by 20 square of area 400.
The shops miss each other in two ways. Shop A opens more than 8 days after shop B opens: that is a corner triangle with both legs 20 - 8 = 12, area 12 * 12 / 2 = 72. Shop B opens more than 4 days after shop A opens: a triangle with legs 20 - 4 = 16, area 16 * 16 / 2 = 128.
The answer is 1 - (72 + 128) / 400 = 0.5.
Example 2
days = 10firstLength = 2secondLength = 2return = 0.36The square has area 10 * 10 = 100. Each way to miss is a triangle with legs 10 - 2 = 8, so each has area 32. The answer is 1 - 64 / 100 = 0.36.
Example 3
days = 5firstLength = 7secondLength = 1return = 0.68Shop A stays open for 7 days, which is longer than the whole 5-day span. Shop B opens by time 5, before shop A can close, so the shops can only miss if shop A opens after shop B has closed.
That is one triangle with legs 5 - 1 = 4 and area 8. The answer is 1 - 8 / 25 = 0.68.
Constraints
1 <= days <= 10^61 <= firstLength, secondLength <= 10^6
More Susquehanna International Group (SIG) Online Assessment questions
- Catch Fish with Reusable BaitsOA · Seen Nov 2026
- Bold Play to Reach a GoalOA · Seen Nov 2026
- Cats, Truth and Who Has MoreOA · Seen Nov 2026
- Counting Cows by Their LegsOA · Seen Nov 2026
- Enough Muffins for the LineOA · Seen Nov 2026
- Expected Consecutive Pairs Among Chosen NumbersOA · Seen Nov 2026
- Four-by-Four Boundary GridOA · Seen Nov 2026
- Frog Paths Without Long RunsOA · Seen Nov 2026
- Higher Roll, or Lose the SumOA · Seen Nov 2026
- Is a Popular Story Fake?OA · Seen Nov 2026
Similar questions at other companies
- Squared Frobenius Norm of a Reflect-and-Stretch MapWalleye Capital · OA
- Triangle and PointsGreyOrange · OA
- Circles RelationshipIBM · OAIBM interview questions
- Slope of a Nonvertical LineMorgan Stanley · OAMorgan Stanley interview questions
- Cyber Beacon DetectionRippling · OARippling interview questions
- Do They Belong?Goldman Sachs · OAGoldman Sachs interview questions
- Closest Point to a LineAdobe · OAAdobe interview questions
- Range of a Third CorrelationTower Research Capital · PHONE SCREEN
- Three Points in a Semicircle: Monte Carlo EstimateSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Union Area of Two RectanglesDocuSign · PHONE SCREENDocuSign interview questions