Katkat
Back

Track Missing Package IDs from Out-of-Order Receipts

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to track a range of sequential integers and identify gaps in a stream of incoming data using efficient data structures.

Track Missing Package IDs

Design a system that tracks incoming package IDs. Packages are assigned unique, nonnegative integer IDs starting from 0. You are receiving a stream of package IDs in arbitrary order. Write a function report_package(package_id) that accepts an integer ID and returns a list of all currently "missing" package IDs that have been superseded by the highest ID received so far.

Specifically, if the highest ID received so far is max_id, any integer i where 0 <= i < max_id that has not yet been reported is considered "missing."

Function Signature

class PackageTracker:
    def __init__(self):
        pass

    def report_package(self, package_id: int) -> List[int]:
        pass

Constraints

  • package_id is a nonnegative integer.
  • Total number of calls to report_package is up to 10^5.
  • package_id can be up to 10^9.

Examples

Example 1:

  • report_package(2): Received {2}, max is 2. Missing: [0, 1]. Returns [0, 1].
  • report_package(0): Received {0, 2}, max is 2. Missing: [1]. Returns [1].
  • report_package(1): Received {0, 1, 2}, max is 2. Missing: []. Returns [].

Edge Cases

  • Receiving duplicate IDs.
  • Receiving IDs significantly larger than previously received IDs (e.g., jump from 1 to 1000).
  • The first ID received is not 0.

Hints

Hint 1

Keep track of the maximum ID seen so far and store received IDs in a boolean set or hash map.

Hint 2

If you store received IDs in a set, you can identify missing IDs by iterating from 0 to the current maximum, but consider if this is efficient for large gaps.

Hint 3

Instead of returning all missing IDs every time, consider how you might efficiently manage a collection of ranges of missing IDs.

Follow-up questions

  • How would you optimize the return value if the caller only needs to know the number of missing packages rather than the list of IDs?
  • What is the time complexity of your solution if you receive N IDs spanning a range of size M?
  • How would you handle the memory constraints if IDs are extremely sparse (e.g., only 10 IDs are received, but the highest is 10^9)?