Implement obstacle-course run statistics
Company: Karat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a TypeScript codebase for tracking race results on an obstacle course.
- A `Course` has a fixed number of obstacles.
- A `Run` stores the times completed so far in `obstacleTimes: number[]`.
- A run is **complete** only when it contains times for all obstacles in the course.
- A `RunCollection` contains historical runs for one course. Some runs may be incomplete.
Complete and fix the following methods in `RunCollection`:
1. **Fix `personalBest(): number`**
Return the minimum total time among **complete runs only**. Incomplete runs must not be treated as valid finish times.
2. **Implement `bestOfBests(): number`**
For each obstacle index, look at every run that has a recorded time for that obstacle, take the minimum such time, and return the sum of those per-obstacle minima. Incomplete runs should contribute for the obstacles they actually reached.
Example for a 4-obstacle course:
- `[3, 4, 5, 6]`
- `[4, 4, 4, 5]`
- `[4, 5, 4, 6]`
- `[5, 5, 3]` (incomplete)
`personalBest()` should return `17`, and `bestOfBests()` should return `15` because the per-obstacle minima are `3, 4, 3, 5`.
3. **Implement `chanceOfPersonalBest(inProgressRun: Run): number` using simulation**
Given an in-progress run, estimate the probability that it will finish with a total time less than or equal to the current personal best.
Use Monte Carlo simulation with **10,000 trials**:
- For every obstacle not yet completed in `inProgressRun`, independently sample a time uniformly at random from the historical times recorded for that obstacle across runs already in the collection.
- Historical samples should include times from incomplete runs if those runs reached that obstacle.
- After filling in all remaining obstacles, compute the total simulated finish time.
- Count the trial as a success if the simulated finish time is less than or equal to `personalBest()`.
- Return `successes / 10000`.
Assume:
- `inProgressRun` belongs to the same course as the collection.
- There is at least one complete historical run.
- Every missing obstacle has at least one historical recorded time available for sampling.
- The returned estimate should usually be within `0.02` of the true probability.
Example: if historical runs are `[3, 3, 2]` and `[3, 3, 3]`, and the current in-progress run is `[3, 3]`, then the chance of matching or beating the personal best is about `0.5` because the last obstacle is sampled uniformly from `{2, 3}`.
Quick Answer: This question evaluates implementation skills in array aggregation, handling incomplete records, per-obstacle minima computation, and Monte Carlo simulation for probabilistic estimation.
Part 1: Personal Best Only Counts Complete Runs
An obstacle course has a fixed number of obstacles. Each recorded run is a list of obstacle times in order. A run is complete only if it contains exactly obstacle_count times. Incomplete runs may have a smaller total so far, but they must not be considered when computing a personal best. Return the minimum total time among complete runs. If there are no complete runs, return -1.
Constraints
- 1 <= obstacle_count <= 10^5
- 0 <= len(runs) <= 10^5
- 0 <= len(run) <= obstacle_count for each run
- Each obstacle time is a positive integer
Examples
Input: (4, [[3, 4, 5, 6], [4, 4, 4, 5], [4, 5, 4, 6], [5, 5, 3]])
Expected Output: 17
Explanation: The incomplete run [5, 5, 3] totals 13 so far, but it is not complete and must be ignored. The best complete total is 17.
Input: (2, [[5, 5], [3, 4], [2]])
Expected Output: 7
Explanation: The run [2] is incomplete and cannot beat the complete run [3, 4], whose total is 7.
Input: (3, [[1], [2, 2], []])
Expected Output: -1
Explanation: No run has exactly 3 obstacle times, so there is no complete run.
Input: (1, [])
Expected Output: -1
Explanation: Edge case: there are no runs at all.
Hints
- A run should only be considered if its length is exactly obstacle_count.
- Track the minimum of sum(run) over only the valid complete runs.
Part 2: Best of Bests Across Obstacles
You are given times from multiple attempts on the same obstacle course. For each obstacle position, find the fastest time ever recorded at that position among all runs that reached it. Incomplete runs still count for the obstacles they completed. Return the sum of these per-obstacle best times. If at least one obstacle has never been reached by any run, return -1.
Constraints
- 1 <= obstacle_count <= 10^5
- 0 <= len(runs) <= 10^5
- 0 <= len(run) <= obstacle_count for each run
- Each obstacle time is a positive integer
Examples
Input: (4, [[3, 4, 5, 6], [4, 4, 4, 5], [4, 5, 4, 6], [5, 5, 3]])
Expected Output: 15
Explanation: Per obstacle minima are [3, 4, 3, 5], which sum to 15.
Input: (4, [[10, 1], [2, 9, 8, 7]])
Expected Output: 18
Explanation: Best times by obstacle are [2, 1, 8, 7]. The incomplete run contributes the best time for obstacle 2.
Input: (3, [[5], [4, 4]])
Expected Output: -1
Explanation: No run ever reached obstacle 3, so the best-of-bests value is undefined.
Input: (1, [[7], [9], []])
Expected Output: 7
Explanation: Only obstacle 1 matters, and its fastest recorded time is 7.
Hints
- Think column by column: obstacle 1, obstacle 2, and so on.
- An incomplete run can still contribute to earlier obstacles that it reached.
Part 3: Simulate the Chance of a Personal Best
You are given historical runs on an obstacle course and a current run that has finished only the first few obstacles. Estimate the chance that the current run will finish with a total time less than or equal to the current personal best.
A historical run is complete if its length is exactly obstacle_count. The personal best is the minimum total time among complete historical runs.
To simulate one completion of the current run, fill each remaining obstacle independently by sampling one recorded time for that obstacle from the historical runs that reached that obstacle. Incomplete historical runs are allowed to contribute samples for the obstacles they reached. Duplicate values count multiple times.
For reproducible testing, you must use this deterministic pseudo-random generator and keep one shared state across all trials:
state = (1103515245 * state + 12345) mod 2^31
When sampling from a bucket of size k, choose bucket[state % k].
Rules:
- Build each obstacle's sample bucket using historical_runs in the given order.
- Run exactly trials simulations.
- Count a trial as successful if the simulated final total is <= personal best.
- If a required future obstacle has no historical samples, return 0.0.
- If current_run is already complete, return 1.0 if it is a personal best (or there is no historical complete run yet), otherwise return 0.0.
- If there is no historical complete run but the current run can still be simulated to a completion, every simulated completion counts as a new personal best.
Constraints
- 1 <= obstacle_count <= 50
- 0 <= len(historical_runs) <= 1000
- 0 <= len(run) <= obstacle_count for each historical run
- 0 <= len(current_run) <= obstacle_count
- 1 <= trials <= 100000
- Each obstacle time is a positive integer
- 0 <= seed < 2^31
Examples
Input: (3, [[3, 3, 2], [3, 3, 3]], [3, 3], 4, 0)
Expected Output: 0.5
Explanation: The final obstacle is sampled from [2, 3]. With the required generator and seed 0, the four choices alternate between 3 and 2, giving 2 successes out of 4.
Input: (3, [[4, 1, 1], [5, 1, 1]], [1], 5, 42)
Expected Output: 1.0
Explanation: All future sampled times are always 1, so every simulated completion totals 3, which beats the historical best of 6.
Input: (3, [[1, 1, 1], [2, 2, 2]], [3], 7, 99)
Expected Output: 0.0
Explanation: The current run already has total 3, and every completion adds at least 2 more seconds, so it can never match the personal best of 3.
Input: (4, [[2, 2, 2], [3, 3]], [1, 1], 10, 7)
Expected Output: 0.0
Explanation: No historical run ever reached obstacle 4, so the current run cannot be simulated to a full completion.
Input: (2, [[3]], [2, 2], 10, 7)
Expected Output: 1.0
Explanation: Edge case: current_run is already complete, and there is no historical complete run yet, so it is automatically a new personal best.
Hints
- First compute the current personal best using only complete historical runs.
- Precompute the sample bucket for each future obstacle before running the trials.