Design an object-oriented SatelliteNetwork that processes a stream of instructions to simulate message propagation and determine report-back order and times. Implement these methods: 1) SatelliteConnected(SatelliteId): Add a satellite node to the network. 2) RelationshipEstablished(SatelliteId1, SatelliteId 2): Add an undirected connection between two satellites. 3) MessageReceived(M, SatelliteId_1, ..., SatelliteId_M): Treat the given M satellites as simultaneously notified at time t=0, then simulate propagation and return the list of (SatelliteId, reportTimeSeconds) ordered by the time they report back to Earth (ties broken by smaller SatelliteId). Simulation rules and constraints: - Forwarding latency: It takes exactly 10 seconds for a satellite to forward a message to one of its direct connections. Forwarding to neighbors is synchronous and atomic per sender: a sender can forward to only one neighbor at a time, each taking 10 seconds. - Forwarding order: Each satellite forwards to all direct connections it has not already notified, strictly in increasing SatelliteId order. - Single effective notify: Once a receiver is notified (by any source), it is considered notified; no further notification attempts change its state. However, concurrent attempts from other senders to notify the same receiver still each consume 10 seconds of the sender’s time. - No immediate back-edge: A satellite never notifies the satellite that most recently notified it. - Processing delay: After a satellite’s direct connections are all notified (from its perspective and per the ordered forwarding it performs), it waits 30 seconds, then it processes the message and reports back to Earth. - Reporting tie-breaker: If two satellites finish processing at the same time, the one with the smaller SatelliteId is considered to arrive first. - Multiple messages: Each call to MessageReceived represents a new message whose initial notified set is the provided satellites at t=0. Clarify whether propagation state resets per message (typical) or persists; implement accordingly and justify. Output and complexity: - MessageReceived should return a stable ordering of (SatelliteId, reportTimeSeconds) for all satellites that become notified in that propagation, ordered by increasing report time with SatelliteId tie-breakers. - Describe and justify your data structures (e.g., adjacency lists with sorted neighbors, event queue/simulator, per-node state with first-notify time, sender schedules), the event scheduling strategy (e.g., priority queue on next-available time and notify events), and the time/space complexities in terms of V (satellites), E (relationships), and degree distribution. Edge cases to cover: - Disconnected components; satellites never reached should not appear in the output. - Multiple concurrent attempts to notify the same target; ensure only the earliest arrival sets its notify time while all senders still incur 10 seconds. - Large hubs with many neighbors and the impact of strict SatelliteId ordering on timelines. - Re-entrant calls to MessageReceived with overlapping or disjoint initial sets.

This question evaluates object-oriented design, graph modeling, discrete-event/time-based simulation, and correctness under ordering, timing, and tie-breaking constraints in a stateful message-propagation scenario.

How do I approach System Design interview questions?

System Design questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master system design interviews.

What difficulty level is this interview question?

This is a hard difficulty System Design question, commonly asked during Take-home Project rounds at Optiver.

What role is this question designed for?

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

Design a satellite propagation simulator | Optiver Interview Question

Object-Oriented SatelliteNetwork: Message Propagation Simulator

Design and implement an object-oriented SatelliteNetwork that processes a stream of instructions to simulate message propagation and determine the report-back order and times for satellites.

Assumptions and scope:

The network topology (satellites and undirected relationships) persists across calls.
Propagation state resets per message: each call to MessageReceived starts a fresh propagation using the current topology (typical semantics for independent messages).
The graph is simple (no parallel edges); neighbor lists are maintained in strictly increasing SatelliteId order.

API

Implement the following methods:

SatelliteConnected(SatelliteId)
- Add the satellite node to the network if not already present.
RelationshipEstablished(SatelliteId1, SatelliteId2)
- Add an undirected connection between the two satellites.
- Maintain neighbors in strictly increasing SatelliteId order (stable over time).
MessageReceived(M, SatelliteId_1, ..., SatelliteId_M) → List[(SatelliteId, reportTimeSeconds)]
- Treat the given M satellites as simultaneously notified at time t=0.
- Simulate propagation according to the rules below.
- Return a list of (SatelliteId, reportTimeSeconds) for all satellites that become notified in this propagation, ordered by report time ascending, using SatelliteId as a tie-breaker.

Simulation rules

Forwarding latency:
- It takes exactly 10 seconds for a satellite to forward a message to one direct neighbor.
- A sender can forward to only one neighbor at a time (sequential), each attempt consuming 10 seconds.
- Forwarding to neighbors is synchronous and atomic per sender.
Forwarding order:
- Each satellite forwards to all of its direct neighbors it has not already notified (from its own perspective), strictly in increasing SatelliteId order.
Single effective notify:
- Once a receiver is notified (by any source), it is considered notified; further attempts do not change its state.
- However, concurrent or later attempts to the same receiver still consume 10 seconds of the sender’s time.
No immediate back-edge:
- A satellite never forwards to the specific neighbor that most recently notified it (its effective notifier). For initial satellites at t=0, there is no prior notifier, so nothing is excluded.
Processing and reporting delay:
- After a satellite completes all of its own forwarding attempts (per the ordered list it performs, with the above back-edge exclusion), it waits 30 seconds, then reports back to Earth.
Tie-breaking:
- Reporting: If two satellites finish processing at the same time, the smaller SatelliteId reports first.
- Simultaneous notify arrivals: If multiple notify attempts arrive to the same satellite at the exact same time, the attempt from the smaller sender SatelliteId is deemed the effective notifier.

Output and complexity expectations

MessageReceived returns a stable ordering of (SatelliteId, reportTimeSeconds) for all satellites reached during that propagation.
Describe and justify your data structures (e.g., adjacency lists with sorted neighbors, event queue/simulator, per-node state with first-notify time and effective notifier) and the event scheduling strategy (e.g., priority queue of notify-attempt completions).
Provide time and space complexity in terms of V (satellites), E (relationships), and the degree distribution.

Edge cases to handle

Disconnected components: satellites never reached must not appear in the output.
Multiple concurrent attempts to notify the same target: only the earliest arrival sets its notify time; all senders still incur 10 seconds per attempt.
Large hubs with many neighbors: honoring strict SatelliteId order significantly impacts timelines.
Re-entrant calls to MessageReceived with overlapping or disjoint initial sets: topology persists; propagation state resets.

Object-Oriented SatelliteNetwork: Message Propagation Simulator

Design and implement an object-oriented SatelliteNetwork that processes a stream of instructions to simulate message propagation and determine the report-back order and times for satellites.

Assumptions and scope:

The network topology (satellites and undirected relationships) persists across calls.
Propagation state resets per message: each call to MessageReceived starts a fresh propagation using the current topology (typical semantics for independent messages).
The graph is simple (no parallel edges); neighbor lists are maintained in strictly increasing SatelliteId order.

API

Implement the following methods:

SatelliteConnected(SatelliteId)
- Add the satellite node to the network if not already present.
RelationshipEstablished(SatelliteId1, SatelliteId2)
- Add an undirected connection between the two satellites.
- Maintain neighbors in strictly increasing SatelliteId order (stable over time).
MessageReceived(M, SatelliteId_1, ..., SatelliteId_M) → List[(SatelliteId, reportTimeSeconds)]
- Treat the given M satellites as simultaneously notified at time t=0.
- Simulate propagation according to the rules below.
- Return a list of (SatelliteId, reportTimeSeconds) for all satellites that become notified in this propagation, ordered by report time ascending, using SatelliteId as a tie-breaker.

Simulation rules

Forwarding latency:
- It takes exactly 10 seconds for a satellite to forward a message to one direct neighbor.
- A sender can forward to only one neighbor at a time (sequential), each attempt consuming 10 seconds.
- Forwarding to neighbors is synchronous and atomic per sender.
Forwarding order:
- Each satellite forwards to all of its direct neighbors it has not already notified (from its own perspective), strictly in increasing SatelliteId order.
Single effective notify:
- Once a receiver is notified (by any source), it is considered notified; further attempts do not change its state.
- However, concurrent or later attempts to the same receiver still consume 10 seconds of the sender’s time.
No immediate back-edge:
- A satellite never forwards to the specific neighbor that most recently notified it (its effective notifier). For initial satellites at t=0, there is no prior notifier, so nothing is excluded.
Processing and reporting delay:
- After a satellite completes all of its own forwarding attempts (per the ordered list it performs, with the above back-edge exclusion), it waits 30 seconds, then reports back to Earth.
Tie-breaking:
- Reporting: If two satellites finish processing at the same time, the smaller SatelliteId reports first.
- Simultaneous notify arrivals: If multiple notify attempts arrive to the same satellite at the exact same time, the attempt from the smaller sender SatelliteId is deemed the effective notifier.

Output and complexity expectations

MessageReceived returns a stable ordering of (SatelliteId, reportTimeSeconds) for all satellites reached during that propagation.
Describe and justify your data structures (e.g., adjacency lists with sorted neighbors, event queue/simulator, per-node state with first-notify time and effective notifier) and the event scheduling strategy (e.g., priority queue of notify-attempt completions).
Provide time and space complexity in terms of V (satellites), E (relationships), and the degree distribution.

Edge cases to handle

Disconnected components: satellites never reached must not appear in the output.
Multiple concurrent attempts to notify the same target: only the earliest arrival sets its notify time; all senders still incur 10 seconds per attempt.
Large hubs with many neighbors: honoring strict SatelliteId order significantly impacts timelines.
Re-entrant calls to MessageReceived with overlapping or disjoint initial sets: topology persists; propagation state resets.

Design a satellite propagation simulator

Quick Overview

Object-Oriented SatelliteNetwork: Message Propagation Simulator

API

Simulation rules

Output and complexity expectations

Edge cases to handle

Solution

Comments (0)

Design a satellite propagation simulator

Quick Overview

Object-Oriented SatelliteNetwork: Message Propagation Simulator

API

Simulation rules

Output and complexity expectations

Edge cases to handle

Solution

Comments (0)