Stateful Event-Driven Simulation And Allocation

What's being tested

These questions test deterministic event-driven simulation and time-ordered state management: advancing a timeline, processing timestamped events, and maintaining mutable resource state (capacities, temperatures, positions). Interviewers expect correct event ordering, efficient data structures for time/priority queries, and clear tradeoffs between greedy, exact, and approximate allocation algorithms.

Patterns & templates

• Discrete-event simulation: keep an event queue sorted by timestamp, process events in non-decreasing order; use stable ordering for simultaneous events.

• Sweep-line / sort-by-time: sort arrivals/departures O(n log n) then scan, updating state incrementally to avoid per-timestep loops.

• Priority queue / heap for allocation: push candidate resources, pop best-fit in O(log n) per allocation; maintain lazy deletions when state changes.

• Greedy allocation by earliest-departure or best-fit: simple, fast, O(n log n), often optimal for interval-capacity problems.

• Knapsack / DP for exact selection: use capacity-indexed DP when capacities × items reasonable; memory O(capacity) or O(n·capacity).

• Approximation / heuristics: sort by value density or use FPTAS when exact DP is too slow; quantify error guarantees.

• State snapshots & rollbacks: snapshot only mutable fields you need; for rollback use copy-on-write or version timestamps to keep O(1) revert where possible.

Tip: prefer lazy updates (mark stale entries) over eager deletions in heaps to simplify concurrency and state changes.

Common pitfalls

Pitfall: mishandling simultaneous events — failing to define and implement a stable tie-breaker leads to non-deterministic behavior.

Pitfall: forgetting to decrement capacity or marking resources stale in the heap, causing over-allocation or duplicated assignments.

Pitfall: using per-timestep simulation for long intervals — O(time_span) loops blow up; prefer event-driven advances based on event timestamps.

Practice these

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