Out-of-Order Package Receiver

Design `receivePackage(id)` for package IDs starting at 0 and a query API that returns the largest received ID together with every missing ID from 0 through that maximum, even when receipts arrive out of order. Requirements Package IDs start at 0, but packages may be received in any order. Design receivePackage(id) to record one incoming package ID. Design a second API that returns the largest package ID received so far and the complete list of missing IDs between 0 and that maximum. Notes Maintain a set of received IDs and a running maximum. A receipt inserts into the set and updates the maximum in O(1) average time; a query scans from 0 through that maximum and returns IDs absent from the set in O(maxId) time plus output space. Treat duplicate receipts as idempotent unless the interviewer specifies otherwise. If queries dominate and the ID range is very sparse, discuss maintaining missing intervals as the follow-up trade-off instead of rescanning the whole range. Clarify duplicate receipts, the ordering of the missing-ID list, and the result before any package has arrived. These interface details are not fixed by the prompt. Preparation Implement the received-set baseline in under 12 minutes and add tests for the empty state, the first receipt above 0, a duplicate receipt, and filling a previously missing gap. Derive the receive and query complexities aloud, then sketch an interval-based alternative and explain when its extra update complexity is justified by read-heavy traffic.