Optiver·Software Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Optiver software engineer interview with a meaty simulation problem that looks like a graph BFS question until you actually read it carefully. The propagation timing rules and concurrent notification logic made this way harder than I expected from the setup.

Questions Asked (1)

Design and implement a SatelliteNetwork class that simulates timed message propagation across an undirected graph, processing a stream of operations (register satellite, link satellites, broadcast message) and firing callbacks in chronological and lexicographic order as satellites receive messages and report back to Earth.

Algorithms & Data StructuresSystem Design

Author's notes

The setup sounds like a BFS with some extra steps but the concurrent forwarding rule is where things get messy.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the satellite network as an undirected graph and simulate message propagation using a priority queue (min-heap) ordered by arrival time and satellite ID. Process operations in order, scheduling broadcasts and firing callbacks when messages arrive, ensuring chronological and lexicographic ordering.

Pro tip: Clarify edge cases upfront: simultaneous arrivals, duplicate links, and broadcasts to already-informed satellites. Use a tie-breaking rule (e.g., satellite ID) in the priority queue to guarantee deterministic ordering.

1. Clarify Requirements and Assumptions

Ask about graph size, operation frequency, callback semantics, and tie-breaking rules. Confirm whether messages propagate only to directly linked satellites or through multiple hops.

2. Design Data Structures

Use an adjacency list for the graph, a map for satellite metadata, and a min-heap for pending message arrivals. Store callbacks in a list to fire in order.

3. Implement Core Operations

For register, add satellite to map. For link, update adjacency list. For broadcast, schedule message to all neighbors with current time + latency, pushing events into the heap.

4. Simulate Time and Fire Callbacks

Process events from the heap in order, updating current time. When a satellite receives a message, fire its callback and propagate to neighbors if not already informed.

5. Test and Validate

Write unit tests for edge cases: simultaneous arrivals, cycles, disconnected graphs, and multiple broadcasts. Verify callback order matches chronological and lexicographic rules.

Key Points to Mention

Graph representation: adjacency list for efficient neighbor traversal.
Priority queue (min-heap) for event scheduling with tie-breaking by satellite ID.
Handling simultaneous events: process in lexicographic order of satellite IDs.
Avoiding duplicate message processing: track informed satellites per broadcast.
Time complexity: O((V+E) log V) for broadcast propagation.
Callback management: ensure callbacks are fired exactly once per message receipt.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.