Stateful Simulation And Event Ordering

What's being tested

These problems test stateful simulation and precise event ordering: you must model system state over time and produce correct outcomes as events (arrivals, completions, turns) interleave. Interviewers probe ability to convert rules into deterministic update steps, choose the right event structure, and reason about tie-breaking and time advancement.

Patterns & templates

• Event loop simulation — collect events, advance a simulation clock, process next event; common implementation: priority queue via heapq, O(m log m) for m events.

• Greedy single-server queue — track server availability time t_free; for each arrival, start = max(arrival, t_free); update t_free = start + duration.

• Sort-by-time then stable-tie-break — sort(events, key=(time, tie_key)) ensures deterministic handling of simultaneous events.

• Turn-based alternation — maintain an index or boolean flag to toggle collector/player; perform O(1) updates per turn until list exhausted.

• In-place state updates — mutate accumulators (e.g., queue length, collected count) rather than rebuilding structures; saves memory to O(1) beyond input.

• Use integers/64-bit for time — sum of durations can overflow 32-bit; prefer long/int64.

• Batch-processing vs per-event — when arrivals sorted, process contiguous arrivals before advancing completion to reduce heap operations, improving from O(m log m) to near O(m) in practice.

Common pitfalls

Pitfall: Treating simultaneous arrival and completion in arbitrary order — always define and implement a consistent tie-break (e.g., completions before arrivals or vice versa) and state it to the interviewer.

Pitfall: Forgetting server idle time — using only durations without max(arrival, t_free) yields negative waits and wrong completion times.

Pitfall: Using 32-bit integers for accumulated time — large sums cause overflow; use 64-bit types.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.