Amazon Locker

Design a parcel locker: a delivery agent drops a parcel into a compartment that fits and gets a code, the customer opens it with the code, and parcels that wait too long go back. The interview is about fitting sizes and time.

Design a parcel locker station. It has compartments of different sizes. A delivery agent drops a parcel and the system picks a compartment that fits and gives a pickup code. The customer enters the code to open the compartment and take the parcel. A parcel that is not collected in time expires, and the agent returns it.

Questions to ask first

Which sizes exist? Assume SMALL, MEDIUM and LARGE. A parcel has one of these sizes, and each compartment has one of them.
Can a small parcel go into a big compartment? Assume yes, when no compartment of its own size is free. A parcel never goes into a smaller compartment.
Which compartment is chosen when several fit? Assume the smallest size that fits, and the lowest number among equals. Big compartments stay free for big parcels.
How long can a parcel wait? Assume a fixed window, such as one day. Time is passed in as a number of minutes so the design does not read a real clock.
What happens at expiry? Assume the parcel stays in its compartment until the delivery agent empties expired compartments. The code stops working at once.
Are the codes secret? Assume yes. A code opens exactly one parcel, once, and is hard to guess. Several delivery agents can drop at the same time.

Requirements

Add compartments of a given size to the station.
Drop a parcel: choose a free compartment that fits, store the parcel and return a pickup code. Refuse with a clear reason when no compartment fits, the size is not known, or the parcel is already inside.
Pick up: open the compartment for a valid code that has not expired, hand over the parcel and free the compartment. A code works once.
Treat a parcel as expired after a fixed window and refuse its code from then on.
Let the agent collect expired parcels, which frees their compartments.
Keep the rule that picks the compartment, and the way codes are made, behind interfaces so each can change.

Out of scope

Doors, locks, scanners and the screen.
Sending SMS or email to the customer (see the extensions).
Payments, returns and pickups by someone other than the customer.
Many stations and finding the nearest one.
Saving data to a database.

Entities

Locker: the station; addCompartment(size), store(parcel, minute), pickup(code, minute), collectExpired(minute)
Compartment: number, size and the delivery inside; fill(delivery), empty(), isFree()
Size: SMALL, MEDIUM, LARGE; fits(parcelSize) tells whether a compartment of this size can hold the parcel
Parcel: id and size
Delivery: the link between a code, a parcel, a compartment and the minute it expires; isExpired(minute)
AllocationStrategy: choose(compartments, parcelSize), the rule for picking a compartment
CodeGenerator: next(), makes pickup codes

Classes in the model design

Locker (class)
Compartment (class)
Size (enum)
Parcel (class)
Delivery (class)
AllocationStrategy (interface)
SmallestFitStrategy (class)
CodeGenerator (interface)
SequentialCodeGenerator (class)

The main use case, step by step

An agent arrives at minute 0 with parcel P1, size SMALL. The caller runs `locker.store(parcel, 0)`. The station first checks that no parcel with this id is already inside.
`Locker` asks its `AllocationStrategy` for a compartment: `choose(compartments, SMALL)`. `SmallestFitStrategy` keeps the free compartments whose `size.fits(SMALL)` is true, and returns the one with the smallest size and then the lowest number.
If the strategy returns nothing, the drop is refused with NO_SPACE and nothing has changed. Otherwise `Locker` asks the `CodeGenerator` for the next code, such as 1001.
`Locker` builds a `Delivery` with the code, the parcel, the compartment and the expiry minute, which is the drop minute plus the hold time. It puts the delivery in the compartment and in the map of codes, and returns the code and the compartment number.
The customer enters 1001 at minute 100. `pickup` finds the delivery in the map. A missing code is INVALID_CODE. A delivery whose expiry minute has passed is EXPIRED. Otherwise `Locker` empties the compartment and removes the code, so it cannot be used again.
At minute 1500 the agent calls `collectExpired`. `Locker` finds every compartment whose delivery has expired, empties each one and returns the deliveries, so the agent can take the parcels back.

Patterns used

Strategy (compartment choice): AllocationStrategy with SmallestFitStrategy, held by Locker.. Which compartment a parcel gets is a rule that operations change: nearest to the door, fewest wasted sizes, or even spread. A new rule is a new class and Locker does not change.
Strategy (code generation): CodeGenerator with SequentialCodeGenerator, passed to Locker.. Real codes are random and hard to guess, which makes tests unrepeatable. A generator behind an interface gives tests fixed codes and gives production a secure one.
Association class: Delivery holds the code, the parcel, the compartment and the expiry minute.. These four facts belong to the link between a parcel and a compartment, not to either of them. A Parcel that held the code would break the moment a parcel moved to another compartment.

Key code

Sizes, the allocation strategy and the code generator

public enum Size {
    SMALL, MEDIUM, LARGE;

    /** A compartment of this size holds a parcel of the other size if it is the same size or bigger. */
    public boolean fits(Size parcel) { return this.ordinal() >= parcel.ordinal(); }
}

public interface AllocationStrategy {
    Optional<Compartment> choose(List<Compartment> compartments, Size parcel);
}

/** The smallest free compartment that fits, and the lowest number among equals. */
public final class SmallestFitStrategy implements AllocationStrategy {
    @Override
    public Optional<Compartment> choose(List<Compartment> compartments, Size parcel) {
        return compartments.stream()
            .filter(c -> c.isFree() && c.size().fits(parcel))
            .min(Comparator.comparing(Compartment::size).thenComparingInt(Compartment::number));
    }
}

public interface CodeGenerator {
    String next();
}

Delivery and Locker.store

public final class Delivery {
    private final String code;
    private final Parcel parcel;
    private final Compartment compartment;
    private final int expiresAt;                 // fixed when the parcel is dropped

    public Delivery(String code, Parcel parcel, Compartment compartment, int expiresAt) {
        this.code = code;
        this.parcel = parcel;
        this.compartment = compartment;
        this.expiresAt = expiresAt;
    }

    public String code() { return code; }
    public Parcel parcel() { return parcel; }
    public Compartment compartment() { return compartment; }
    public boolean isExpired(int minute) { return minute >= expiresAt; }
}

public final class Locker {
    private final List<Compartment> compartments = new ArrayList<>();
    private final Map<String, Delivery> byCode = new HashMap<>();
    private final AllocationStrategy strategy;
    private final CodeGenerator codes;
    private final int holdMinutes;
    // the constructor sets the strategy, the code generator and the hold time

    /** Nothing changes when no compartment fits. */
    public Optional<Delivery> store(Parcel parcel, int minute) {
        Optional<Compartment> chosen = strategy.choose(compartments, parcel.size());
        if (chosen.isEmpty()) return Optional.empty();
        Delivery d = new Delivery(codes.next(), parcel, chosen.get(), minute + holdMinutes);
        chosen.get().fill(d);
        byCode.put(d.code(), d);
        return Optional.of(d);
    }
}

Locker: pickup and collectExpired

public final class Locker {
    // compartments, byCode, strategy and codes as above

    /** Hands over the delivery for a valid code, empties the compartment and uses up the code. */
    public Delivery pickup(String code, int minute) {
        Delivery d = byCode.get(code);
        if (d == null) throw new InvalidCodeException();
        if (d.isExpired(minute)) throw new ExpiredCodeException();   // stays inside until collected
        release(d);
        return d;
    }

    /** The agent empties every compartment whose parcel has expired. Returns what was inside, in compartment order. */
    public List<Delivery> collectExpired(int minute) {
        List<Delivery> expired = compartments.stream()
            .filter(c -> !c.isFree() && c.delivery().isExpired(minute))
            .map(Compartment::delivery)
            .toList();
        expired.forEach(this::release);
        return expired;
    }

    private void release(Delivery d) {
        d.compartment().empty();
        byCode.remove(d.code());                 // a code works once
    }
}

public class InvalidCodeException extends RuntimeException { }

public class ExpiredCodeException extends RuntimeException { }

Deep dives

Which compartment does a parcel get?

Weak: Take the first free compartment in the list. A small parcel can fill the only large compartment while small ones are free, and the next large parcel is refused. Or the opposite mistake: allow only the exact size, and refuse a small parcel when only a large compartment is free.

Good: A parcel fits its own size or a bigger one, and the system picks the smallest compartment that fits. Among equal sizes take the lowest number so the answer is the same every time. Put the size rule in Size.fits, so no if on sizes spreads around the code.

Great: Put the choice behind an AllocationStrategy. The station scans all compartments in the first version. When there are thousands, keep one sorted set of free compartments for each size. The strategy then takes the first of the smallest set that fits, and the scan disappears. Make choosing and filling one atomic step, or two agents can pick the same compartment.

Trade-off: A scan is simple and fine for fifty compartments. The free sets cost updates on every drop and pickup and are worth it only at scale. Smallest fit saves the large compartments but can fill the small ones first. Say that this is a policy, and offer another strategy if the interviewer prefers one.

Expiry without a clock or a timer thread

Weak: One timer thread for each parcel that frees the compartment when time runs out. Threads pile up, tests have to sleep, and a compartment can be freed in the middle of a pickup. The code also reads the real clock inside the domain classes.

Good: Pass the time in as a number of minutes, or inject a Clock. Each parcel stores its expiry minute when it is dropped. Every call compares the given minute with the stored one. Tests choose any minute they like and never wait.

Great: Check expiry lazily and clean up in one place. pickup refuses an expired code, and collectExpired(minute) frees the compartments, because the agent has to carry the parcels away anyway. The expired state is never stored: it is worked out from the minute and the expiry time, so there is nothing to fall out of step. Storing the expiry minute on the Delivery means a later change to the hold time does not change parcels already inside.

Trade-off: Until the agent collects, an expired parcel still fills its compartment. Some designs run the collection step before each drop to free space sooner. That is a business decision, because a customer who arrives one minute late finds the parcel gone. Ask the interviewer, and keep the sweep as a separate method either way.

Pickup codes

Weak: Use the compartment number as the code, or a counter. Anyone can open anyone's parcel by guessing. Finding the parcel means scanning every compartment for a matching code.

Good: A random code, and a map from code to delivery for a direct lookup. A successful pickup removes the entry, so a code works once. If a new code is already in the map, make another.

Great: Hide the making of codes behind a CodeGenerator. Production uses a secure random six-digit number, and tests use a sequential one so expected output is fixed. A six-digit code has a million values, so a thief could try many guesses. Count wrong codes at the station and slow down or lock after a few. Return the same message for a wrong code at every point where the reason does not help the customer.

Trade-off: A short code is easy to type, and a long one is safer. Six digits with a lock after a few wrong tries is a common balance. A separate EXPIRED answer helps a customer who comes too late, and costs a little secrecy: it tells a guesser that the code was real.

Now add one more feature

Now add many stations and let the customer choose one near their home. A `LockerNetwork` holds the stations and picks one with another strategy, such as the nearest station with space. `Locker` does not change, because it already answers for one station.
Now tell the customer by SMS or email when the parcel arrives and again one day before it expires. `Locker` publishes events such as `ParcelStored` to listeners (the observer pattern). A notifier subscribes. The locker does not know about SMS.
Now let a compartment be out of order. Add a flag to `Compartment` and make `isFree` return false while it is on. `SmallestFitStrategy` already skips compartments that are not free, so the strategy does not change.
Now let some customers keep parcels longer, such as a subscription plan. Replace the fixed hold time with a `HoldPolicy` that answers for each parcel. `Delivery` stores the expiry minute that the policy gave when the parcel was dropped.

What each level is expected to show

SDE-1: Clear classes for Locker, Compartment, Parcel and Delivery, a size rule that lets a parcel use the same or a bigger compartment, a code that works once, and expiry that takes the time in as a number. Every refusal leaves the station unchanged.

SDE-2: All of SDE-1, plus the compartment rule and the code maker behind interfaces, an expiry minute stored at drop time, a reason for choosing when expired parcels are cleared, and a plan for two agents dropping together. Answers extensions by naming the one class that changes.

Common mistakes

Letting a parcel go into a smaller compartment, or refusing it when only a bigger one is free.
Taking the first free compartment, so one small parcel fills the only large one.
Reading the real clock inside Locker, so tests have to wait and cannot check the last minute of the window.
Freeing the compartment at the moment of expiry with no agent step, so the parcel is lost with no one to take it back.
Leaving the code in the map after pickup, so one code opens the compartment again for the next parcel.
Computing the expiry from the current hold time at every check, so a change to the hold time moves the expiry of parcels already inside.
Choosing the compartment and filling it in two separate steps, so two agents can get the same one.