Implement a SatelliteNetwork class to simulate message propagation over an undirected satellite graph. Provide these methods: ( 1) satellite_connected(satellite_id): register a new satellite; if satellite_id already exists, call ErrDuplicateSatelliteId(satellite_id). ( 2) relationship_established(satellite_id1, satellite_id 2): create a bidirectional link; if either ID does not exist, call ErrInvalidSatelliteId(offending_id). ( 3) message_received(satellite_ids): Earth sends the same message simultaneously at time t=0 to all listed satellites; if any ID does not exist, call ErrInvalidSatelliteId(offending_id). Propagation rules: When a satellite first receives the message at time t, it attempts to forward to each directly connected satellite that has not yet received it; each such neighbor receives at time t + 10s (forwarding takes 10s per sender). A satellite ignores receptions after its first. A satellite becomes eligible to report back once all of its direct neighbors have received the message (from any sender); its report is delivered at the earliest time this condition becomes true plus 30s. When multiple reports are delivered at the same time, invoke callbacks in increasing SatelliteId order. Side effects/output: For each report, call OnSatelliteReportedBack(satelliteId) in exact chronological order for that message. Do not return or print anything else. Assumptions/constraints: Satellite IDs are integers. There may be multiple calls to message_received; treat each call as an independent run. Design data structures/algorithms to handle large N satellites and M links efficiently, ensuring deterministic ordering. Provide code or pseudocode and analyze time and space complexity.

This question evaluates proficiency in graph algorithms, event-driven simulation, time-based propagation modeling, deterministic ordering, and efficient data structure design for large-scale networks within the Coding & Algorithms domain.

How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a Medium difficulty Coding & Algorithms 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

Implement a SatelliteNetwork class to simulate message propagation over an undirected satellite graph. Provide these methods: (

satellite_connected(satellite_id): register a new satellite; if satellite_id already exists, call ErrDuplicateSatelliteId(satellite_id). (
relationship_established(satellite_id1, satellite_id 2): create a bidirectional link; if either ID does not exist, call ErrInvalidSatelliteId(offending_id). (
message_received(satellite_ids): Earth sends the same message simultaneously at time t=0 to all listed satellites; if any ID does not exist, call ErrInvalidSatelliteId(offending_id). Propagation rules: When a satellite first receives the message at time t, it attempts to forward to each directly connected satellite that has not yet received it; each such neighbor receives at time t + 10s (forwarding takes 10s per sender). A satellite ignores receptions after its first. A satellite becomes eligible to report back once all of its direct neighbors have received the message (from any sender); its report is delivered at the earliest time this condition becomes true plus 30s. When multiple reports are delivered at the same time, invoke callbacks in increasing SatelliteId order. Side effects/output: For each report, call OnSatelliteReportedBack(satelliteId) in exact chronological order for that message. Do not return or print anything else. Assumptions/constraints: Satellite IDs are integers. There may be multiple calls to message_received; treat each call as an independent run. Design data structures/algorithms to handle large N satellites and M links efficiently, ensuring deterministic ordering. Provide code or pseudocode and analyze time and space complexity.

Implement a SatelliteNetwork class to simulate message propagation over an undirected satellite graph. Provide these methods: (

satellite_connected(satellite_id): register a new satellite; if satellite_id already exists, call ErrDuplicateSatelliteId(satellite_id). (
relationship_established(satellite_id1, satellite_id 2): create a bidirectional link; if either ID does not exist, call ErrInvalidSatelliteId(offending_id). (
message_received(satellite_ids): Earth sends the same message simultaneously at time t=0 to all listed satellites; if any ID does not exist, call ErrInvalidSatelliteId(offending_id). Propagation rules: When a satellite first receives the message at time t, it attempts to forward to each directly connected satellite that has not yet received it; each such neighbor receives at time t + 10s (forwarding takes 10s per sender). A satellite ignores receptions after its first. A satellite becomes eligible to report back once all of its direct neighbors have received the message (from any sender); its report is delivered at the earliest time this condition becomes true plus 30s. When multiple reports are delivered at the same time, invoke callbacks in increasing SatelliteId order. Side effects/output: For each report, call OnSatelliteReportedBack(satelliteId) in exact chronological order for that message. Do not return or print anything else. Assumptions/constraints: Satellite IDs are integers. There may be multiple calls to message_received; treat each call as an independent run. Design data structures/algorithms to handle large N satellites and M links efficiently, ensuring deterministic ordering. Provide code or pseudocode and analyze time and space complexity.

Design a satellite propagation simulator

Quick Overview

Comments (0)

Design a satellite propagation simulator

Quick Overview

Comments (0)