Optiver software engineer interviews cover algorithms, data structures, system design, and coding problems drawn from real interview rounds.
MessageScheduler. Each message has a globally unique identifier, a session identifier, a release timestamp, and an integer priority.Messages within a session form a FIFO queue in enqueue order. Only the first non-cancelled, undispatched message in each session may compete for dispatch. Consequently, a message whose release time has passed can still be blocked by an earlier message in its session.The scheduler's clock initially equals 0. Calling dispatch(now, limit) sets its clock to now; dispatch timestamps must be nondecreasing. Enqueueing and cancellation do not advance the clock.For each slot in a dispatch call:release_time <= now.limit messages or when no session head is eligible. Dispatch does not advance time beyond now, and there is no service duration.Cancellation removes a pending message logically. If it was a session head, the next non-cancelled message immediately becomes the head. Cancelling an unknown, already-cancelled, or already-dispatched identifier returns false.Support up to 200,000 operations efficiently. Do not scan every session on each dispatch or search linearly through a session to cancel a message.Function or class signatureMessageScheduler() — initialize an empty scheduler.enqueue(message_id: str, session_id: str, release_time: int, priority: int) -> Nonecancel(message_id: str) -> booldispatch(now: int, limit: int) -> list[str][ ["enqueue", "A1", "alpha", 10, 1], ["enqueue", "A2", "alpha", 0, 100], ["enqueue", "B1", "beta", 0, 5], ["dispatch", 0, 10], ["dispatch", 9, 10], ["dispatch", 10, 1], ["dispatch", 10, 10] ]Output, one result per operation:
[null, null, null, ["B1"], [], ["A1"], ["A2"]]Explanation: At time
0, A2 is blocked by A1, despite having priority 100 and release time 0. Only B1 can run. At time 9, A1 is still unreleased. The first call at time 10 dispatches A1 and reaches its limit; the next call dispatches A2.Example 2:Input, on a fresh scheduler:[ ["enqueue", "X1", "x", 20, 9], ["enqueue", "X2", "x", 5, 4], ["enqueue", "Y1", "y", 5, 4], ["enqueue", "Z1", "z", 3, 4], ["cancel", "X1"], ["dispatch", 5, 2], ["cancel", "X1"], ["dispatch", 5, 2] ]Output, one result per operation:
[null, null, null, null, true, ["Z1", "X2"], false, ["Y1"]]Explanation: Cancelling
X1 exposes X2. At time 5, the three session heads all have priority 4. Z1 wins first because its release time is 3; X2 wins next because it was enqueued before Y1, and both have release time 5. A second cancellation of X1 returns false.Constraints:200,000 total method calls and at most 200,000 enqueued messages.32 ASCII characters.0 <= release_time, now <= 10^18; -10^9 <= priority <= 10^9.0 <= limit <= 200,000; successive dispatch timestamps are nondecreasing.P messages are pending at any moment. How would you guarantee O(P + 1) retained space after every operation, while preserving efficient cancellation and dispatch even when cancelled messages have release times far in the future?Sign up for free to access walkthroughs, AI-generated questions, and more.
Get Started Free