Katkat
Back

Check Whether Every Parcel Finds a Locker With Forward Overflow

MercorMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

Parcels arrive one at a time for a bank of numbered lockers, each requesting a preferred locker and overflowing to the next higher-numbered empty one if it's taken. Decide whether every parcel finds a locker. Tests precise rule-following and an efficient alternative to simulating forward scans one slot at a time.

A parcel room holds m lockers lined up side by side, index 0 through m - 1 left to right. Parcels arrive one after another, processed strictly in the sequence listed in requested; whichever locker number sits at requested[i] is what the i-th parcel asks for first. Determine whether every parcel ends up in a locker.

def every_parcel_fits(m: int, requested: list[int]) -> bool:

Rules

  • Every locker starts empty, and once a parcel is placed in a locker it never moves.
  • A parcel first tries its preferred locker. If that locker is empty, the parcel goes there.
  • If the preferred locker is occupied, the parcel is placed in the first empty locker with a higher number.
  • A parcel can never be placed in a locker with a lower number than its preference. If every locker from the preference onward is already occupied, that parcel does not fit anywhere.
  • Return True only if every parcel finds a locker; return False as soon as one fails. An empty requested list returns True.

Constraints

  • 1 <= m <= 10^5
  • 0 <= len(requested) <= 10^5
  • 0 <= requested[i] <= m - 1

Examples

Input:  m = 5, requested = [2, 2, 0, 4]
Output: True

Parcel 0 takes locker 2. Parcel 1 wants 2 (taken) and takes locker 3. Parcel 2 wants 0 (empty) and takes it. Parcel 3 takes locker 4. Locker 1 stays empty, but every parcel fit.

Input:  m = 4, requested = [2, 2, 3]
Output: False

Parcel 0 takes locker 2. Parcel 1 wants 2 (taken) and takes locker 3. Parcel 2 wants locker 3, which is now taken, and there is no locker numbered higher than 3 — so it fails, even though lockers 0 and 1 are still empty.

Input:  m = 6, requested = [3, 0]
Output: True

Parcel 0 takes locker 3; parcel 1 takes locker 0. Lockers 1, 2, 4, 5 stay empty.

Aim for something faster than scanning forward one locker at a time per parcel in the worst case; be ready to explain why that scan can be slow and how your approach avoids it.

Hints

Hint 1

Simulating a linear forward scan for each parcel is correct but can degrade to O(m) per parcel if a long run of lockers is already full — think about what makes that repeated work avoidable.

Hint 2

Once a locker is filled, every future parcel preferring it (or scanning past it) needs the same answer: 'where's the next empty locker at or after this one?' — that question doesn't change until something later fills in gaps behind it, which never happens here since placement only ever moves forward.

Hint 3

A disjoint-set (union-find) structure where each occupied locker points to the next locker's representative answers 'next empty locker at or after x' in near O(1) amortized time.

Hint 4

Use one extra sentinel slot representing 'no locker available' so a parcel whose next-empty-lookup lands past the last real locker is immediately recognized as failing to fit.

Follow-up questions

  • How would you support a 'release locker x' operation later, given that union-find structures are normally built around merges, not splits?
  • How would you report which specific parcel was the first to fail, not just whether any parcel failed?
  • What would change if parcels could specify a small set of acceptable lockers instead of a single forward-only preference?
  • How would you adapt this if lockers were added to the far end of the row dynamically while parcels were still arriving?