Track simulations and report timeouts
Company: Applied
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are implementing a monitoring component for many concurrent simulations.
Each simulation produces a stream of **event objects** of the form:
- `sim_id` (string or integer): identifies the simulation
- `type` (string): one of `"start"`, `"ping"`, or `"end"`
- `timestamp` (integer or long): the event time in seconds (or milliseconds), monotonically non-decreasing across all events
Semantics:
- `start`: the simulation `sim_id` has started at this `timestamp`. Its **last activity timestamp** becomes this `timestamp`.
- `ping`: the simulation `sim_id` is still running; update its **last activity timestamp** to this `timestamp`.
- `end`: the simulation `sim_id` has finished normally at this `timestamp`; after this it should no longer be considered active.
You are also given a **timeout limit** `T` (e.g., 3 seconds). A simulation should be considered **timed out** and automatically ended if:
\[
\text{current_time} - \text{last\_activity\_timestamp(sim)} > T
\]
where `current_time` is the timestamp of the most recently processed event.
Design a function with the following behavior:
- The function receives events one by one in time order: `processEvent(event)`.
- Upon receiving a new event with timestamp `ts_current`, it should:
1. Update internal state according to the event (`start`, `ping`, or `end`).
2. Determine which simulations have **just become timed out** at or before `ts_current`, i.e., simulations that:
- Have not already ended (neither by `end` event nor by a previous timeout), and
- Satisfy `ts_current - last_activity_timestamp > T`.
3. Mark these simulations as ended due to timeout so they will not be returned again.
4. Return the set (or list) of all `sim_id`s that are now considered timed out.
Your function should be efficient for large numbers of simulations and events (aim for close to \(O(\log n)\) time per event, where \(n\) is the number of active simulations).
Specify the data structures you would use, and describe the key operations your implementation must support (no need to provide full code). Assume the process is long-running and must handle many events over time without restarting.
Quick Answer: This question evaluates competency in algorithms and data-structure design for real-time stream processing, including maintaining per-simulation state, handling time-based expirations, and reasoning about performance and correctness.
Process ordered simulation events and return [sim_id,timestamp] when active simulations time out before each new event.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([("a","start",0),("b","start",1),("b","ping",3),("c","start",5)], 3)
Expected Output: [['a', 5]]
Explanation: Simulation a times out when current time reaches 5.
Input: ([("a","start",0),("a","end",2),("b","start",10)], 3)
Expected Output: []
Explanation: Ended simulations are not timed out.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.