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.