Design a satellite propagation simulator
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
Implement a `SatelliteNetwork` class that simulates message propagation over an **undirected** satellite graph. The class consumes a stream of instructions online and triggers callbacks as the simulation unfolds. Implement the following methods:
1. **`satellite_connected(satellite_id)`** — Register a new satellite. If `satellite_id` already exists, call `ErrDuplicateSatelliteId(satellite_id)` and do not add it again.
2. **`relationship_established(satellite_id1, satellite_id2)`** — Create a bidirectional (undirected) link between the two satellites. If either ID does not exist, skip the instruction and call `ErrInvalidSatelliteId(offending_id)` for the invalid ID.
3. **`message_received(satellite_ids)`** — Earth sends the same message simultaneously at time `t = 0` to all listed satellites. If any listed ID does not exist, call `ErrInvalidSatelliteId(offending_id)`. Treat each call to `message_received` as an independent run (reset all per-message state between runs).
**Propagation rules**
- When a satellite first receives the message at time `t`, it attempts to forward it to each directly connected neighbor that has not yet received it. Forwarding is done one neighbor at a time, in increasing `SatelliteId` order, and each send takes exactly **10 seconds** (so the first neighbor is reached at `t + 10`, the second at `t + 20`, and so on).
- A satellite never attempts to notify the satellite that notified it.
- Different satellites may concurrently attempt to notify the same neighbor; each attempt still consumes 10 seconds, but as soon as **any** attempt completes, that neighbor is considered notified and no further attempts to it should proceed (the neighbor takes its earliest arrival time).
- A satellite ignores all receptions after its first.
**Reporting back to Earth**
- A satellite becomes eligible to report back once **all** of its direct neighbors have received the message (from any sender). At the earliest time this condition becomes true, the satellite spends **30 seconds** processing and then reports back — i.e. its report is delivered at `(time the last neighbor was notified) + 30`.
- For each report, call `OnSatelliteReportedBack(satellite_id)` in exact chronological order for that message.
- When multiple reports are delivered at the same time, invoke the callbacks in increasing `SatelliteId` order.
- Do not return or print anything else.
**Assumptions / constraints**
- Satellite IDs are integers.
- There may be multiple calls to `message_received`; each is an independent run.
- Handle duplicate and invalid references exactly as specified via the error callbacks.
- Design your data structures and algorithm to handle large `N` satellites and `M` links efficiently, while guaranteeing deterministic output ordering.
Provide code or pseudocode and analyze the time and space complexity.
Quick Answer: Optiver software-engineer take-home: implement a SatelliteNetwork that simulates timed message propagation over an undirected graph and fires OnSatelliteReportedBack callbacks in deterministic order. It tests graph modeling, discrete-event simulation, priority-queue scheduling, and careful handling of 10s-per-hop forwarding and 30s report timing with tie-breaking by SatelliteId.
Implement a simulator for message propagation over an undirected satellite graph. You are given a stream of instructions. Instead of implementing callbacks directly, return a list of callback events in the order they would be invoked.
Supported instructions:
1. ("satellite_connected", satellite_id): Register a new satellite. If satellite_id already exists, append ["ErrDuplicateSatelliteId", satellite_id] and do not add it again.
2. ("relationship_established", satellite_id1, satellite_id2): Create a bidirectional link. If either ID does not exist, skip the link and append ["ErrInvalidSatelliteId", offending_id] for each invalid ID, checking satellite_id1 first and then satellite_id2. Duplicate links do not create duplicate edges.
3. ("message_received", satellite_ids): Earth sends the same message at time t = 0 to all valid listed satellites. If a listed ID does not exist, append ["ErrInvalidSatelliteId", offending_id]. Valid listed satellites still participate in the simulation. Duplicate valid starting satellites count only once.
Each message_received instruction is an independent propagation run: all per-message receive/report state is reset.
Propagation rules:
- When a satellite first receives the message at time t, it determines which of its directly connected neighbors have not received the message at that time.
- It attempts to forward to those neighbors one at a time, in increasing satellite ID order.
- The first attempted neighbor receives at t + 10, the second at t + 20, and so on.
- A satellite never attempts to notify the satellite that notified it.
- If multiple attempts reach the same satellite, only the earliest arrival counts. If several attempts arrive at the same earliest time, the smallest sender ID is treated as the notifier.
- All receptions at the same timestamp are considered simultaneous before any of those satellites begin forwarding.
Reporting rules:
- A satellite can report only after it has received the message and all of its direct neighbors have received the message.
- Its report is delivered 30 seconds after that condition first becomes true.
- For an isolated satellite, this is 30 seconds after it receives the message.
- Return ["OnSatelliteReportedBack", satellite_id] for each report.
- Reports for a single message must be ordered by delivery time; ties are ordered by increasing satellite ID.
- Finish all callbacks for one message_received instruction before processing the next instruction.
Constraints
- 0 <= len(instructions) <= 200000
- Satellite IDs are integers and may be negative, zero, or positive
- The total number of unique satellites is at most 200000
- The total number of successful undirected relationships is at most 200000
- The total number of satellite IDs appearing inside all message_received lists is at most 200000
- Duplicate relationship instructions are allowed and should not create duplicate edges
Examples
Input: ([],)
Expected Output: []
Explanation: There are no instructions, so no callbacks are invoked.
Input: ([("satellite_connected", 1), ("message_received", [1])],)
Expected Output: [["OnSatelliteReportedBack", 1]]
Explanation: Satellite 1 is isolated. It receives the message at t=0 and reports at t=30.
Hints
- Use an adjacency set for each satellite, and process message arrivals with a min-heap ordered by time, receiver ID, and sender ID.
- Process all arrivals with the same timestamp as a batch. After all receive times are known, a satellite's report time is max(its receive time, all neighbor receive times) + 30.