Design test-run logging and query functions
Company: Vanta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Implement log(test_id, timestamp, status) to record a test run, where timestamps are strictly increasing across all test IDs. Implement get_min_time_to_pass(test_id) that returns the minimum time length for the specified test to change from failing to passing status, using the first failure in any consecutive failure series, or null if the test never passes. Implement log(test_id, timestamp, status) as above for a follow-up scenario. Implement get_longest_failure_window(min_tests) that returns {start_timestamp, end_timestamp} for the maximum contiguous period where at least min_tests tests are failing simultaneously; return null if no such window exists.
Quick Answer: This question evaluates proficiency in time-series logging, event-driven state transitions, interval and sliding-window algorithms, and efficient data-structure design for streaming updates.
Part 1: Minimum Time for a Test to Recover
You are given a chronologically sorted list of test-run logs. Each log is [test_id, timestamp, status], where status is 0 for fail and 1 for pass. Timestamps are strictly increasing across all logs.
For one test, multiple consecutive fail logs belong to the same failure series. If a pass later appears for that test, the recovery time for that series is:
pass_timestamp - first_fail_timestamp_of_that_series
After processing all logs, answer queries for specific test IDs. For each queried test_id, return the minimum recovery time across all of its completed fail-to-pass series. If the test never completes a fail-to-pass series, return -1.
Constraints
- 0 <= len(logs) <= 200000
- 0 <= len(query_test_ids) <= 200000
- 1 <= test_id <= 10^9
- 1 <= timestamp <= 10^9
- Timestamps in logs are strictly increasing
- status is always 0 or 1
Examples
Input: ([[1, 1, 0], [2, 2, 0], [1, 4, 0], [1, 5, 1], [2, 6, 1], [1, 10, 0], [1, 13, 1]], [1, 2, 3])
Expected Output: [3, 4, -1]
Explanation: Test 1 has recovery times 5-1=4 and 13-10=3, so the minimum is 3. Test 2 has one recovery time 6-2=4. Test 3 never recovers.
Input: ([[1, 1, 1], [1, 2, 1], [1, 3, 0], [1, 7, 1], [1, 10, 0], [1, 12, 1]], [1])
Expected Output: [2]
Explanation: Initial pass logs do not start a failure series. The completed fail-to-pass durations are 7-3=4 and 12-10=2.
Hints
- Track, for each test, the first timestamp of its current consecutive fail streak.
- Only when a pass closes an active fail streak do you get a candidate recovery time.
Part 2: Longest Window with At Least K Failing Tests
You are given a chronologically sorted list of test-run logs. Each log is [test_id, timestamp, status], where status is 0 for fail and 1 for pass. Timestamps are strictly increasing across all logs.
A test is considered failing after a fail log until a later pass log for the same test appears. Consecutive fail logs for a test do not create extra failing tests; that test simply remains in the failing set.
Find the longest contiguous window of observed time during which at least min_tests tests are failing simultaneously.
Use these boundary rules:
- A window starts at the timestamp of the log that causes the number of failing tests to become at least min_tests.
- A window ends at the timestamp of the later log that causes the number of failing tests to drop below min_tests.
- If the count is still at least min_tests after the final log, use the final log's timestamp as the end.
- If multiple windows have the same length, return the one with the earliest start.
- If no such window exists, return an empty list.
Constraints
- 0 <= len(logs) <= 200000
- 1 <= min_tests <= 200000
- 1 <= test_id <= 10^9
- 1 <= timestamp <= 10^9
- Timestamps in logs are strictly increasing
- status is always 0 or 1
Examples
Input: ([[1, 1, 0], [2, 2, 0], [1, 5, 1], [3, 6, 0], [2, 8, 1], [3, 10, 1]], 2)
Expected Output: [2, 5]
Explanation: At least 2 tests are failing from timestamp 2 until the log at timestamp 5 drops the count below 2. Another valid window is [6, 8], but it is shorter.
Input: ([[1, 2, 0], [2, 4, 0], [1, 6, 0]], 2)
Expected Output: [4, 6]
Explanation: The threshold is first reached at timestamp 4 and remains satisfied through the final log, so the window ends at timestamp 6.
Hints
- Maintain the current set of failing tests while you scan the logs from left to right.
- A candidate window only starts when the failing count crosses the threshold upward, and only ends when it crosses downward.