Track simulations and report timeouts

Q: Track simulations and report timeouts

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Applied.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Applied during technical interviews.

Question

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.

Track simulations and report timeouts

Quick Overview

Comments (0)