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.
Process homogeneous `[opcode,value]` rows. Opcode zero receives nonnegative package ID `value` idempotently. Opcode one reports `[largest_received_id, missing_ids...]`, where missing IDs from zero through the observed maximum appear in ascending order. Before any receipt, status is `[-1]`. Return all status records in operation order.
Constraints
- 0 <= len(operations) <= 200000 and every row has two integers.
- Opcode 0 receives an ID from 0 through 200000; opcode 1 uses padding value zero.
- Duplicate receipt is idempotent and status records missing IDs in ascending order.
- The total number of integers returned across all status calls is at most 400000.
Examples
Input: ([],)
Expected Output: []
Explanation: No operations produce no status records.
Input: ([[1, 0]],)
Expected Output: [[-1]]
Explanation: Status before any receipt is exactly negative one.
Hints
- Test status before any receipt, receiving zero first, and receiving a large ID first.
- Include duplicate receipts and several status calls before and after filling a gap.
- Check that multiple missing IDs are always returned in ascending order.