Track the Contiguous Package Frontier and Missing IDs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Track the Contiguous Package Frontier and Missing IDs
Design a `PackageTracker` for non-negative package IDs that are expected to begin at `0` but may arrive out of order.
The class supports:
- `receive(id)`, which records one delivered package.
- `report()`, which returns the largest ID in the contiguous delivered prefix beginning at `0`, together with every missing ID after that frontier and before the greatest ID received so far.
The missing IDs must be returned in ascending order. If no package has arrived, return frontier `-1` and an empty missing list. Repeated delivery of an ID must not change the result.
For example, after receiving `0`, `1`, `2`, `3`, and `100`, `report()` returns frontier `3` and the list `[4, 5, 6, ..., 99]`.
### Constraints & Assumptions
- IDs are non-negative integers, and arrival order is arbitrary.
- The tracker may receive an ID that is far ahead of the current frontier.
- Reporting the missing IDs necessarily takes time proportional to the number of IDs returned.
### Clarifying Questions to Ask
- Can the same package be delivered more than once?
- Should missing IDs above the greatest observed ID be reported, or is the observed maximum the reporting boundary?
- How should the empty state be represented?
```hint Advance only from the boundary
After an arrival, work forward from the first ID that is not yet part of the contiguous prefix; there is no need to rescan from zero.
```
```hint Separate tracking from materialization
The state needed to maintain the frontier can be compact even though producing a long missing list is output-sensitive.
```
### Evaluation Criteria
- Correct frontier advancement across out-of-order arrivals.
- Idempotent handling of duplicate IDs.
- A precise missing-range boundary based on the greatest received ID.
- Amortized analysis for updates and output-sensitive analysis for reports.
### Extensions to Discuss
- How would you avoid materializing a huge missing list if package `0` is followed by package `10^12`?
- Could the API return missing intervals instead of individual IDs?
- How would the design change if delivered-package state had to survive process restarts?
Quick Answer: Design a PackageTracker that handles out-of-order and duplicate package IDs while maintaining the contiguous delivered frontier from zero. Discuss how to report every missing ID up to the largest observed package, analyze amortized update and output-sensitive reporting costs, and scale the API for extremely sparse ranges.
Implement track_packages(received_ids), which applies the listed nonnegative package IDs as sequential receive calls. Return [frontier, missing], where frontier is the largest ID in the contiguous delivered prefix beginning at 0 and missing is the ascending list of undelivered IDs after the frontier and strictly before the greatest received ID. With no arrivals, return [-1, []]. Duplicate deliveries do not change the report.
Constraints
- 0 <= received_ids.length <= 20.
- Every received ID is an integer from 0 through 50.
- Arrival order is arbitrary and IDs may repeat.
- The missing list is materialized explicitly, so the console bounds IDs to keep output finite.
- Missing IDs are returned in strictly ascending order and stop before the greatest received ID.
Examples
Input: []
Expected Output: [-1, []]
Explanation: Before any delivery, the frontier is -1 and no bounded missing IDs exist.
Input: [0]
Expected Output: [0, []]
Explanation: Receiving package 0 establishes a one-package contiguous prefix.
Hints
- Keep a set of delivered IDs and advance only from the first ID beyond the current contiguous frontier.
- Track the greatest observed ID independently so report knows the exclusive upper boundary.
- Materialize missing IDs only after the final frontier is known.