Track Missing Package IDs from Out-of-Order Receipts

Quick Overview

Packages have nonnegative integer IDs starting at `0`, but they may be received out of order. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

Track Missing Package IDs from Out-of-Order Receipts

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Packages have nonnegative integer IDs starting at `0`, but they may be received out of order. Support two operations: - `receive(id)` records that package as received. Receiving the same ID again is idempotent. - `status()` reports the largest received ID and the ascending IDs missing from `0..largest_received_id`. Before any package is received, the largest ID is `-1` and the missing list is empty. For console evaluation, implement `package_statuses(operations)` with homogeneous two-integer operation rows: - `[0, id]` means `receive(id)`. - `[1, 0]` means `status()`; the second value is padding. Return one flat integer list for each status call: `[largest_received_id, missing_id_1, ..., missing_id_m]`. Before any receipt, this record is `[-1]`. The full return type is therefore a portable list of integer lists. ### Constraints - At most `200000` operations are supplied. - `0 <= id <= 200000` - The total number of IDs returned across all status calls is at most `400000`. ### Example Operations `[[0,2], [1,0], [0,0], [1,0], [0,2]]` return `[[2,0,1], [2,1]]`. ```hint Distinguish the observed maximum from the contiguous prefix Receiving a large ID extends the range that status must describe, even when smaller IDs are missing. ``` ```hint Output cost is unavoidable A status call that returns many missing IDs takes at least proportional time; keep updates efficient and iterate missing IDs in sorted order. ```

Quick Answer: Packages have nonnegative integer IDs starting at `0`, but they may be received out of order. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

|Home/Coding & Algorithms/Amazon
Amazon logo
Amazon
Aug 1, 2026, 12:00 AM
mediumSoftware EngineerTechnical ScreenCoding & Algorithms
0
0

Packages have nonnegative integer IDs starting at 0, but they may be received out of order. Support two operations:

  • receive(id) records that package as received. Receiving the same ID again is idempotent.
  • status() reports the largest received ID and the ascending IDs missing from 0..largest_received_id . Before any package is received, the largest ID is -1 and the missing list is empty.

For console evaluation, implement package_statuses(operations) with homogeneous two-integer operation rows:

  • [0, id] means receive(id) .
  • [1, 0] means status() ; the second value is padding.

Return one flat integer list for each status call: [largest_received_id, missing_id_1, ..., missing_id_m]. Before any receipt, this record is [-1]. The full return type is therefore a portable list of integer lists.

Constraints

  • At most 200000 operations are supplied.
  • 0 <= id <= 200000
  • The total number of IDs returned across all status calls is at most 400000 .

Example

Operations [[0,2], [1,0], [0,0], [1,0], [0,2]] return [[2,0,1], [2,1]].

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...