Applied intuition·Software Engineer·Onsite - System Design / Architecture·Senior

SeniorPrefer not to say

May 2026

Summary

Applied Intuition system design round, one meaty question about building a timeout detector for a job scheduler. Spent most of the time on edge cases and data structure tradeoffs, which I think is where they actually wanted to see me go.

Questions Asked (1)

Design and implement an event-timeout detector for a job scheduler. You get a global timeout T and a stream of events with an ID, a type (start, end, or ping), and a timestamp. An event times out if it started but never ended and the time since its last update exceeds T. Pings reset the update clock, ends remove the event. Implement process(event) and get_timed_out(now_ts). Also cover edge cases: duplicates, out-of-order events, events with no prior start, multiple starts, and zero or negative timeouts. Analyze time and space complexity.

System DesignAlgorithms & Data StructuresTechnical Trade-offs

Author's notes

This one took a while to get my footing on.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and edge cases, then propose a data structure like a hash map combined with a min-heap or balanced BST to track events by ID and expiry times. Explain how to handle each edge case and analyze time/space complexity, emphasizing trade-offs between different approaches.

Pro tip: Mention that using a lazy deletion strategy with a heap avoids O(n) removals and keeps operations efficient, and explicitly state how you'd handle clock skew or out-of-order events by comparing timestamps rather than relying on arrival order.

1. Clarify requirements and edge cases

Ask questions to confirm the definitions of timeout, how pings and ends affect state, and the expected behavior for duplicates, out-of-order events, and invalid timeouts. Explicitly list the edge cases you will handle.

2. Design data structures

Propose a hash map from event ID to its last update timestamp and status (active/inactive), plus a priority queue (min-heap) keyed by expiry time (last_update + T) for efficient timeout detection. Discuss alternatives like balanced BST or timing wheel.

3. Implement process(event)

For start: create or reset the event's last update and add to heap. For ping: update last update and push new expiry. For end: mark event as ended and optionally remove from heap lazily. Handle duplicates and out-of-order by comparing timestamps.

4. Implement get_timed_out(now_ts)

Pop from the heap while the top's expiry <= now_ts, validate that the event is still active and its last update + T <= now_ts (to handle stale heap entries), and collect timed-out event IDs. Return the list.

5. Analyze complexity and edge cases

State that process is O(log n) due to heap insertion, get_timed_out is O(k log n) where k is number of timed-out events (amortized O(log n) per event), and space is O(n). Explain how each edge case is handled and any assumptions.

Key Points to Mention

Use a hash map for O(1) access to event state and a min-heap for efficient timeout ordering.
Lazy deletion: don't remove from heap on end/ping; instead validate when popping.
Handle out-of-order events by comparing timestamps: ignore events with timestamp older than last update.
For zero or negative timeouts, define behavior (e.g., immediate timeout) and ensure no infinite loops.
Duplicates: if same ID and type, treat as idempotent or update based on timestamp; multiple starts: reset timer.
Events with no prior start: ignore or treat as invalid; document assumption.
Complexity: process O(log n), get_timed_out O(k log n) worst-case, space O(n).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.