Katkat
Back

Track the Contiguous Package Frontier and Missing IDs

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage sparse, out-of-order data using data structures like sets or priority queues and finding gaps within a contiguous range.

Problem Statement

You are building a PackageTracker class that receives delivery notifications as individual integers (package IDs). Packages arrive in an arbitrary order and may contain duplicates. The system needs to track the "delivered frontier" (the largest integer k such that all package IDs from 0 to k have been received) and identify all missing IDs between 0 and the current maximum observed ID.

Implement the following methods:

  • void receive(int packageId): Records that a package has arrived.
  • int getFrontier(): Returns the largest k such that all IDs 0 through k are present.
  • List getMissing(): Returns a sorted list of all missing IDs between 0 and the maximum observed packageId.

Constraints

  • packageId can be any non-negative integer up to 1,000,000.
  • receive is called frequently; getMissing is called occasionally.

Example

tracker = PackageTracker()
tracker.receive(0)
tracker.receive(2)
tracker.receive(1)
# Frontier is 2. Missing is [].
tracker.receive(4)
# Frontier is 2. Missing is [3].

Edge Cases

  • Receiving the same packageId multiple times.
  • Receiving a packageId that is smaller than the current frontier.
  • Large gaps between IDs (e.g., receiving 0, then 1,000,000).

Hints

Hint 1

Use a boolean array or a set to track which packages have been received so far.

Hint 2

Maintain a pointer for the frontier that only increments when the next expected integer is found in your tracker.

Hint 3

For `getMissing`, iterate from the frontier + 1 up to the maximum observed ID and check your tracking structure.

Follow-up questions

  • How would you optimize `getMissing` if the range is extremely sparse and the maximum ID is very large?
  • If memory were limited, how could you handle millions of package IDs arriving in a distributed system?
  • What is the time complexity of `receive` and `getMissing`, and can you improve them using a segment tree or a disjoint set union?