Amazon Locker
medium · allocation (best fit), pickup codes, expiry
Brief-reported interview attribution (unverified): Amazon
How to approach an LLD roundRequirements
- Functional: deposit a package into the best-fitting free locker (smallest locker that fits, lowest id), issue a 6-digit pickup code, pick up by code (expired codes return None and do NOT free the locker), expire packages by day, report free lockers and locker status.
- Non-functional: a package id is unique; allocation must be deterministic; the expiry rule must live on the ticket.
- Out of scope: payments, notifications, multi-site lockers.
Statement
Design an Amazon Locker bank. The bank has lockers in three sizes —
small, medium, large. Packages also have sizes; a package fits a locker of
its own size or larger. When a courier deposits a package, the system assigns the
smallest locker that fits (best fit, so large lockers stay free for large
packages) and returns a 6-digit pickup code. The customer enters the code to
collect the package, which frees the locker. A package not collected within
pickup_days (default 3) expires; an expired package is collected by a daily
expiry job (expire(day)), which frees its locker and returns the list of expired
package ids. Days are plain integers passed by the caller.
class AmazonLocker:
def __init__(self, lockers, pickup_days=3, allocation_strategy=None, code_generator=None):
# lockers: {"small": n, "medium": n, "large": n}
def deposit(self, package_id, package_size, day):
# -> (locker_id, code) or None (no fitting locker free / duplicate package / bad size)
# locker ids are "L1", "L2", ... in size order (small, then medium, then large);
# codes are 6-digit strings starting at "100000", one per successful deposit
def pickup(self, code, day):
# -> package_id if the code is valid and not expired, else None
# (a successful pickup frees the locker)
def expire(self, day):
# -> list of package ids that expired as of this day (in locker order); frees their lockers
def available_lockers(self, package_size=None):
# -> count of free lockers that fit the size (all free lockers if size is None; 0 for a bad size)
def status(self, locker_id):
# -> "available" | "occupied" | None for an unknown lockerRules. Best fit: among free lockers that fit, pick the smallest size, then the
lowest locker id. A package expires when day >= deposit_day + pickup_days.
pickup on an expired code returns None and does not free the locker — only
expire(day) frees expired packages (it is the daily job). A code is single-use.
Depositing a package_id that is already stored returns None. Codes are
assigned only on successful deposits.
Tests use explicit inputs and injected clocks/callbacks. No network, real threads or application-server execution is involved.
Class design (SOLID)
Size (IntEnum, ordered small < medium < large, so fit is a comparison). Ticket (a frozen dataclass: the immutable claim record — code, locker, package, deposit day, expiry — with the expiry rule; SRP). Locker (occupy/release with a guard against double-occupancy; SRP). CodeGenerator (ABC interface) + SequentialCodeGenerator (6-digit codes from 100000; OCP — swap the scheme without touching the system). AllocationStrategy (ABC interface) + BestFitStrategy (one min-heap per size keyed by locker id, pops the lowest-id fitting locker; OCP — first-fit is another strategy). AmazonLocker takes the strategy and the code generator as constructor arguments (DIP) and orchestrates. Pattern: Strategy (allocation and code generation).
Pass optional allocation_strategy and code_generator collaborators. The generator implements generate(); the allocation strategy implements allocate(package_size, available_by_size) and removes its chosen locker from the pool.
Public demo
# Public demo: run after implementing the class API above.
l = AmazonLocker({'small': 1, 'medium': 1, 'large': 1}, pickup_days=3)
print(l.deposit('P1', 'small', 0))Reference solution and hidden tests
Locked. Open the interactive editor and attempt the problem; the reference, hidden test descriptions, pattern explanation and complexity are available only after an explicit reveal.
Concurrency
Two deposits at once must not take the same locker: the strategy's heap pop and the locker's occupy must be atomic — one lock per locker bank around deposit/pickup/expire. The reference is single-threaded; the lock is described here.
Trade-offs & extensions
Best-fit keeps large lockers free for large packages, and the per-size min-heaps make allocation pick the lowest-id free locker of the smallest fitting size. The cost is the extra machinery (two small interfaces) — worth it because both the allocation rule and the code scheme are the parts that change. expire still scans the whole bank and reinserts each expired locker into a heap (O(lockers + expired·log lockers) worst case); for a huge bank it would keep its own expiry list. Extending: a PickupNotification (Observer) and a FirstFitStrategy.
Starter code
from abc import ABC, abstractmethod
from dataclasses import dataclass
from enum import IntEnum
import heapq
class Size(IntEnum):
SMALL = 1
MEDIUM = 2
LARGE = 3
@dataclass(frozen=True)
class Ticket:
code: str
locker_id: str
package_id: str
size: Size
deposited_at: int
expires_at: int
def is_expired(self, day):
"""Implement the return value and rules in the API contract."""
pass
class Locker:
def __init__(self, locker_id, size):
"""lockers: {"small": n, "medium": n, "large": n}"""
pass
def is_free(self):
"""Implement the return value and rules in the API contract."""
pass
def occupy(self, ticket):
"""Implement the return value and rules in the API contract."""
pass
def release(self):
"""Implement the return value and rules in the API contract."""
pass
class CodeGenerator(ABC):
@abstractmethod
def generate(self):
"""Implement the return value and rules in the API contract."""
pass
class SequentialCodeGenerator(CodeGenerator):
def __init__(self):
"""lockers: {"small": n, "medium": n, "large": n}"""
pass
def generate(self):
"""Implement the return value and rules in the API contract."""
pass
class AllocationStrategy(ABC):
@abstractmethod
def allocate(self, package_size, available_by_size):
"""Implement the return value and rules in the API contract."""
pass
class BestFitStrategy(AllocationStrategy):
def allocate(self, package_size, available_by_size):
"""Implement the return value and rules in the API contract."""
pass
class AmazonLocker:
def __init__(self, lockers, pickup_days=3, allocation_strategy=None, code_generator=None):
"""lockers: {"small": n, "medium": n, "large": n}"""
pass
def deposit(self, package_id, package_size, day):
"""-> (locker_id, code) or None (no fitting locker free / duplicate package / bad size) locker ids are "L1", "L2", ... in size order (small, then medium, then large); codes are 6-digit strings starting at "100000", one per successful deposit"""
pass
def pickup(self, code, day):
"""-> package_id if the code is valid and not expired, else None (a successful pickup frees the locker)"""
pass
def expire(self, day):
"""-> list of package ids that expired as of this day (in locker order); frees their lockers"""
pass
def available_lockers(self, package_size=None):
"""-> count of free lockers that fit the size (all free lockers if size is None; 0 for a bad size)"""
pass
def status(self, locker_id):
"""-> "available" | "occupied" | None for an unknown locker"""
pass
Each test has a five-second execution limit. Your practice drafts and solved progress stay in this browser.
Return to the Python interpreter