Design a Movie Ticket Booking System

package com.androidinterview.movieticket.lock;

// The identity of one seat at one show. A record rather than a joined string,
// so a typo is a compile error instead of a silent miss, and so nothing has to
// agree on a separator.
public record SeatKey(String showId, String seatId) {
}

package com.androidinterview.movieticket.lock;

public record SeatKey(String showId, String seatId) {
}

package com.androidinterview.movieticket.lock;

import java.time.Instant;
import java.util.List;

// A temporary claim on some named seats. The user is on the record because
// release has to check it, and the expiry is an absolute instant so any process
// that reads the lock can judge it without a timer of its own.
public record SeatLock(
        String id,
        String showId,
        List<String> seatIds,
        String userId,
        Instant expiresAt) {

    public boolean isExpiredAt(Instant now) {
        return !now.isBefore(expiresAt);
    }
}

package com.androidinterview.movieticket.lock;

import java.time.Instant;
import java.util.List;

public record SeatLock(
        String id,
        String showId,
        List<String> seatIds,
        String userId,
        Instant expiresAt) {

    public boolean isExpiredAt(Instant now) {
        return !now.isBefore(expiresAt);
    }
}

package com.androidinterview.movieticket.lock;

import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.UUID;

import com.androidinterview.movieticket.model.Seat;
import com.androidinterview.movieticket.model.Show;

// The whole problem lives here. A seat for one show is in exactly one of three
// states, free, locked by somebody who is paying, or sold. This class owns all
// three and owns the only lock, because splitting that across two classes is
// how you get two half correct ones.
//
// A hotel counts rooms and this counts nothing, because seats are named. That
// difference is why this is a map of seat keys and not a set of counters.
//
// Be honest about the lock. This is one process. A real ticketing platform runs
// many servers behind a load balancer, so the guarantee has to come from a
// shared store, either a row per seat updated conditionally in a transaction or
// a short lived key per seat in Redis.
public final class SeatLockManager {

    private final Clock clock;
    private final Duration ttl;
    private final Map<SeatKey, SeatLock> locksBySeat = new HashMap<>();
    private final Map<String, SeatLock> byLockId = new HashMap<>();
    private final Set<SeatKey> sold = new HashSet<>();
    private final Object monitor = new Object();

    public SeatLockManager(Clock clock, Duration ttl) {
        this.clock = clock;
        this.ttl = ttl;
    }

    // A seat the caller is holding is shown as available to that caller, because
    // refreshing the seat map in the middle of your own checkout should not tell
    // you your seats are gone.
    public List<Seat> availableSeats(Show show, String userId) {
        synchronized (monitor) {
            sweepExpired();
            List<Seat> free = new ArrayList<>();
            for (Seat seat : show.screen().seats()) {
                SeatKey key = new SeatKey(show.id(), seat.id());
                SeatLock held = locksBySeat.get(key);
                boolean lockedByOther = held != null && !held.userId().equals(userId);
                if (!sold.contains(key) && !lockedByOther) {
                    free.add(seat);
                }
            }
            return free;
        }
    }

    // All the seats or none of them. Four friends given three seats together is
    // worse than four friends given nothing, so this checks every seat before it
    // writes anything.
    //
    // The seat ids are sorted first, and repeats are dropped. That canonical
    // order is not needed while one lock covers the whole map, but it is exactly
    // what a per seat locking scheme would need to avoid deadlock, so it belongs
    // in the design now.
    public Optional<SeatLock> lockSeats(String showId, List<String> seatIds, String userId) {
        List<String> ordered = seatIds.stream().distinct().sorted().toList();
        synchronized (monitor) {
            sweepExpired();
            for (String seatId : ordered) {
                SeatKey key = new SeatKey(showId, seatId);
                if (sold.contains(key) || locksBySeat.containsKey(key)) {
                    return Optional.empty();
                }
            }
            SeatLock seatLock = new SeatLock(UUID.randomUUID().toString(), showId,
                    ordered, userId, clock.instant().plus(ttl));
            for (String seatId : ordered) {
                locksBySeat.put(new SeatKey(showId, seatId), seatLock);
            }
            byLockId.put(seatLock.id(), seatLock);
            return Optional.of(seatLock);
        }
    }

    // Owner checked. Without this comparison the sweeper, or a stale request
    // from an abandoned tab, can free seats that a different user acquired a
    // moment ago and is already paying for.
    public boolean release(String lockId, String userId) {
        synchronized (monitor) {
            SeatLock held = byLockId.get(lockId);
            if (held == null || !held.userId().equals(userId)) {
                return false;
            }
            remove(held);
            return true;
        }
    }

    // The compare and set. It judges the expiry itself rather than trusting the
    // sweeper to have run, so the payment callback and the sweeper cannot both
    // believe they won. If this returns false the money has already been taken
    // and has to be refunded, which is a real outcome and not an edge case.
    public boolean confirm(String lockId, String userId) {
        synchronized (monitor) {
            SeatLock held = byLockId.get(lockId);
            if (held == null || !held.userId().equals(userId)) {
                return false;
            }
            remove(held);
            if (held.isExpiredAt(clock.instant())) {
                return false;
            }
            for (String seatId : held.seatIds()) {
                sold.add(new SeatKey(held.showId(), seatId));
            }
            return true;
        }
    }

    public void releaseSold(String showId, List<String> seatIds) {
        synchronized (monitor) {
            seatIds.forEach(seatId -> sold.remove(new SeatKey(showId, seatId)));
        }
    }

    // A scheduled job in production. Called at the top of every read here, so a
    // test can advance a fixed Clock instead of sleeping.
    public int sweepExpired() {
        synchronized (monitor) {
            Instant now = clock.instant();
            Set<SeatLock> stale = new HashSet<>();
            for (SeatLock held : byLockId.values()) {
                if (held.isExpiredAt(now)) {
                    stale.add(held);
                }
            }
            stale.forEach(this::remove);
            return stale.size();
        }
    }

    private void remove(SeatLock held) {
        held.seatIds().forEach(seatId -> locksBySeat.remove(new SeatKey(held.showId(), seatId)));
        byLockId.remove(held.id());
    }
}

package com.androidinterview.movieticket.lock;

import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.UUID;

import com.androidinterview.movieticket.model.Seat;
import com.androidinterview.movieticket.model.Show;

public final class SeatLockManager {

    private final Clock clock;
    private final Duration ttl;
    private final Map<SeatKey, SeatLock> locksBySeat = new HashMap<>();
    private final Map<String, SeatLock> byLockId = new HashMap<>();
    private final Set<SeatKey> sold = new HashSet<>();
    private final Object monitor = new Object();

    public SeatLockManager(Clock clock, Duration ttl) {
        this.clock = clock;
        this.ttl = ttl;
    }

    public List<Seat> availableSeats(Show show, String userId) {
        synchronized (monitor) {
            sweepExpired();
            List<Seat> free = new ArrayList<>();
            for (Seat seat : show.screen().seats()) {
                SeatKey key = new SeatKey(show.id(), seat.id());
                SeatLock held = locksBySeat.get(key);
                boolean lockedByOther = held != null && !held.userId().equals(userId);
                if (!sold.contains(key) && !lockedByOther) {
                    free.add(seat);
                }
            }
            return free;
        }
    }

    public Optional<SeatLock> lockSeats(String showId, List<String> seatIds, String userId) {
        List<String> ordered = seatIds.stream().distinct().sorted().toList();
        synchronized (monitor) {
            sweepExpired();
            for (String seatId : ordered) {
                SeatKey key = new SeatKey(showId, seatId);
                if (sold.contains(key) || locksBySeat.containsKey(key)) {
                    return Optional.empty();
                }
            }
            SeatLock seatLock = new SeatLock(UUID.randomUUID().toString(), showId,
                    ordered, userId, clock.instant().plus(ttl));
            for (String seatId : ordered) {
                locksBySeat.put(new SeatKey(showId, seatId), seatLock);
            }
            byLockId.put(seatLock.id(), seatLock);
            return Optional.of(seatLock);
        }
    }

    public boolean release(String lockId, String userId) {
        synchronized (monitor) {
            SeatLock held = byLockId.get(lockId);
            if (held == null || !held.userId().equals(userId)) {
                return false;
            }
            remove(held);
            return true;
        }
    }

    public boolean confirm(String lockId, String userId) {
        synchronized (monitor) {
            SeatLock held = byLockId.get(lockId);
            if (held == null || !held.userId().equals(userId)) {
                return false;
            }
            remove(held);
            if (held.isExpiredAt(clock.instant())) {
                return false;
            }
            for (String seatId : held.seatIds()) {
                sold.add(new SeatKey(held.showId(), seatId));
            }
            return true;
        }
    }

    public void releaseSold(String showId, List<String> seatIds) {
        synchronized (monitor) {
            seatIds.forEach(seatId -> sold.remove(new SeatKey(showId, seatId)));
        }
    }

    public int sweepExpired() {
        synchronized (monitor) {
            Instant now = clock.instant();
            Set<SeatLock> stale = new HashSet<>();
            for (SeatLock held : byLockId.values()) {
                if (held.isExpiredAt(now)) {
                    stale.add(held);
                }
            }
            stale.forEach(this::remove);
            return stale.size();
        }
    }

    private void remove(SeatLock held) {
        held.seatIds().forEach(seatId -> locksBySeat.remove(new SeatKey(held.showId(), seatId)));
        byLockId.remove(held.id());
    }
}

package com.androidinterview.movieticket.model;

import java.util.List;

// A confirmed set of seats for one show. There is no pending state here on
// purpose. Pending is what the seat lock is, and it lives in the lock manager
// where it can expire.
//
// Two states and one transition, so a boolean is the whole state machine. A
// status enum with a transition table would be ceremony around one flag.
public final class Booking {

    private final String id;
    private final String showId;
    private final String userId;
    private final List<String> seatIds;
    private final Money total;
    private boolean cancelled;

    public Booking(String id, String showId, String userId, List<String> seatIds, Money total) {
        this.id = id;
        this.showId = showId;
        this.userId = userId;
        this.seatIds = List.copyOf(seatIds);
        this.total = total;
    }

    public String id() { return id; }
    public String showId() { return showId; }
    public String userId() { return userId; }
    public List<String> seatIds() { return seatIds; }
    public Money total() { return total; }
    public synchronized boolean cancelled() { return cancelled; }

    public synchronized void cancel() {
        if (cancelled) {
            throw new IllegalStateException("this booking is already cancelled");
        }
        cancelled = true;
    }
}

package com.androidinterview.movieticket.model;

import java.util.List;

public final class Booking {

    private final String id;
    private final String showId;
    private final String userId;
    private final List<String> seatIds;
    private final Money total;
    private boolean cancelled;

    public Booking(String id, String showId, String userId, List<String> seatIds, Money total) {
        this.id = id;
        this.showId = showId;
        this.userId = userId;
        this.seatIds = List.copyOf(seatIds);
        this.total = total;
    }

    public String id() { return id; }
    public String showId() { return showId; }
    public String userId() { return userId; }
    public List<String> seatIds() { return seatIds; }
    public Money total() { return total; }
    public synchronized boolean cancelled() { return cancelled; }

    public synchronized void cancel() {
        if (cancelled) {
            throw new IllegalStateException("this booking is already cancelled");
        }
        cancelled = true;
    }
}

package com.androidinterview.movieticket.model;

import java.util.List;

public record Cinema(String id, String name, String city, List<Screen> screens) {
}

package com.androidinterview.movieticket.model;

import java.util.List;

public record Cinema(String id, String name, String city, List<Screen> screens) {
}

package com.androidinterview.movieticket.model;

public record Money(String currency, long amount) {

    public Money plus(Money other) {
        return new Money(currency, amount + other.amount);
    }

    public Money scale(double factor) {
        return new Money(currency, Math.round(amount * factor));
    }
}

package com.androidinterview.movieticket.model;

public record Money(String currency, long amount) {

    public Money plus(Money other) {
        return new Money(currency, amount + other.amount);
    }

    public Money scale(double factor) {
        return new Money(currency, Math.round(amount * factor));
    }
}

package com.androidinterview.movieticket.model;

import java.time.Duration;

public record Movie(String id, String title, String language, Duration runtime) {
}

package com.androidinterview.movieticket.model;

import java.time.Duration;

public record Movie(String id, String title, String language, Duration runtime) {
}

package com.androidinterview.movieticket.model;

import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

// A screen and the seats in it. The lookup by id is built once, because pricing
// a basket of seats should not walk the whole auditorium per seat, and because
// an id nobody recognises has to be rejected rather than quietly skipped.
public final class Screen {

    private final String id;
    private final String name;
    private final List<Seat> seats;
    private final Map<String, Seat> byId = new LinkedHashMap<>();

    public Screen(String id, String name, List<Seat> seats) {
        this.id = id;
        this.name = name;
        this.seats = List.copyOf(seats);
        for (Seat seat : this.seats) {
            byId.put(seat.id(), seat);
        }
    }

    public String id() { return id; }
    public String name() { return name; }
    public List<Seat> seats() { return seats; }

    public Seat seatById(String seatId) {
        return byId.get(seatId);
    }
}

package com.androidinterview.movieticket.model;

import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public final class Screen {

    private final String id;
    private final String name;
    private final List<Seat> seats;
    private final Map<String, Seat> byId = new LinkedHashMap<>();

    public Screen(String id, String name, List<Seat> seats) {
        this.id = id;
        this.name = name;
        this.seats = List.copyOf(seats);
        for (Seat seat : this.seats) {
            byId.put(seat.id(), seat);
        }
    }

    public String id() { return id; }
    public String name() { return name; }
    public List<Seat> seats() { return seats; }

    public Seat seatById(String seatId) {
        return byId.get(seatId);
    }
}

package com.androidinterview.movieticket.model;

// A physical seat in a screen. It carries no availability of its own, and that
// is the point. The same seat is free for the six o'clock show and taken for
// the nine, so availability belongs to the pair of a show and a seat, never to
// the seat alone.
public record Seat(String id, String row, int number, SeatTier tier) {
}

package com.androidinterview.movieticket.model;

public record Seat(String id, String row, int number, SeatTier tier) {
}

package com.androidinterview.movieticket.model;

// The price multiplier lives on the tier, so nothing else writes a switch over
// seat classes. Adding a recliner tier is one line.
public enum SeatTier {
    SILVER(1.0),
    GOLD(1.5),
    PLATINUM(2.0);

    private final double multiplier;

    SeatTier(double multiplier) {
        this.multiplier = multiplier;
    }

    public double multiplier() {
        return multiplier;
    }
}

package com.androidinterview.movieticket.model;

public enum SeatTier {
    SILVER(1.0),
    GOLD(1.5),
    PLATINUM(2.0);

    private final double multiplier;

    SeatTier(double multiplier) {
        this.multiplier = multiplier;
    }

    public double multiplier() {
        return multiplier;
    }
}

package com.androidinterview.movieticket.model;

import java.time.Instant;

// A movie on a screen at a time. This is the thing tickets are actually sold
// against, and its id is half of every inventory key in the system.
public record Show(String id, Movie movie, Screen screen, Instant startsAt, Money basePrice) {
}

package com.androidinterview.movieticket.model;

import java.time.Instant;

public record Show(String id, Movie movie, Screen screen, Instant startsAt, Money basePrice) {
}

package com.androidinterview.movieticket.pricing;

import com.androidinterview.movieticket.model.Money;
import com.androidinterview.movieticket.model.Seat;
import com.androidinterview.movieticket.model.Show;

// Priced per seat, not per booking, because a booking can mix tiers.
public interface PricingStrategy {
    Money priceFor(Show show, Seat seat);
}

package com.androidinterview.movieticket.pricing;

import com.androidinterview.movieticket.model.Money;
import com.androidinterview.movieticket.model.Seat;
import com.androidinterview.movieticket.model.Show;

public interface PricingStrategy {
    Money priceFor(Show show, Seat seat);
}

package com.androidinterview.movieticket.pricing;

import com.androidinterview.movieticket.model.Money;
import com.androidinterview.movieticket.model.Seat;
import com.androidinterview.movieticket.model.Show;

// The show's base price scaled by the tier of the seat. A weekend or a
// matinee rule wraps this rather than replacing it, the same way surge wraps
// ride pricing.
public final class TierPricing implements PricingStrategy {

    @Override
    public Money priceFor(Show show, Seat seat) {
        return show.basePrice().scale(seat.tier().multiplier());
    }
}

package com.androidinterview.movieticket.pricing;

import com.androidinterview.movieticket.model.Money;
import com.androidinterview.movieticket.model.Seat;
import com.androidinterview.movieticket.model.Show;

public final class TierPricing implements PricingStrategy {

    @Override
    public Money priceFor(Show show, Seat seat) {
        return show.basePrice().scale(seat.tier().multiplier());
    }
}

package com.androidinterview.movieticket.service;

import java.time.Clock;
import java.util.List;
import java.util.Optional;
import java.util.UUID;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.function.BiPredicate;

import com.androidinterview.movieticket.lock.SeatLock;
import com.androidinterview.movieticket.lock.SeatLockManager;
import com.androidinterview.movieticket.model.Booking;
import com.androidinterview.movieticket.model.Money;
import com.androidinterview.movieticket.model.Seat;
import com.androidinterview.movieticket.model.Show;
import com.androidinterview.movieticket.pricing.PricingStrategy;

// The one class the app talks to. It sequences selection, payment and
// confirmation, and it owns none of the rules.
//
// Payment is a two argument predicate rather than a gateway interface, because
// card handling is a different interview. The first argument is the idempotency
// key, which is what makes a retried charge safe.
public final class BookingService {

    private final SeatLockManager locks;
    private final PricingStrategy pricing;
    private final BiPredicate<String, Money> charge;
    private final Clock clock;

    // One entry per idempotency key, claimed before the card is touched. A
    // plain map read followed by a write would let two copies of the same
    // request both miss and both charge, which is the exact bug this map is
    // here to prevent.
    private final ConcurrentMap<String, CompletableFuture<ConfirmResult>> attempts =
            new ConcurrentHashMap<>();

    public BookingService(SeatLockManager locks, PricingStrategy pricing,
                          BiPredicate<String, Money> charge, Clock clock) {
        this.locks = locks;
        this.pricing = pricing;
        this.charge = charge;
        this.clock = clock;
    }

    public List<Seat> availableSeats(Show show, String userId) {
        return locks.availableSeats(show, userId);
    }

    // Every requested seat has to exist in this screen. Skipping the ones that
    // do not would quote a lower total and then charge it.
    public Money quote(Show show, List<String> seatIds) {
        Money total = new Money(show.basePrice().currency(), 0);
        for (String seatId : seatIds) {
            Seat seat = show.screen().seatById(seatId);
            if (seat == null) {
                throw new IllegalArgumentException("no seat " + seatId + " in this screen");
            }
            total = total.plus(pricing.priceFor(show, seat));
        }
        return total;
    }

    // Selection takes the lock. Nothing is charged and nothing is sold yet, and
    // the clock is now running. A show that has already started sells nothing,
    // so the request is refused here rather than ten minutes later.
    public Optional<SeatLock> selectSeats(Show show, List<String> seatIds, String userId) {
        if (hasStarted(show)) {
            return Optional.empty();
        }
        return locks.lockSeats(show.id(), seatIds, userId);
    }

    // The order here is the answer to the hardest follow up in this problem.
    // Charge first, then confirm, because a cinema seat cannot be sold twice
    // and a refund is a real remedy. If the lock died while the bank was
    // thinking, the seats may already belong to somebody else, so the honest
    // result is that a refund is owed.
    //
    // The key is claimed before any of that. One key, one answer, so a retry
    // that arrives while the first request is still at the bank waits for it
    // and reads its outcome rather than charging the card a second time.
    public ConfirmResult confirm(Show show, SeatLock seatLock, String userId, String idempotencyKey) {
        CompletableFuture<ConfirmResult> mine = new CompletableFuture<>();
        CompletableFuture<ConfirmResult> running = attempts.putIfAbsent(idempotencyKey, mine);
        if (running != null) {
            ConfirmResult first = running.join();
            return first instanceof ConfirmResult.Confirmed done
                    ? new ConfirmResult.AlreadyConfirmed(done.booking())
                    : first;
        }
        try {
            ConfirmResult result = attemptConfirm(show, seatLock, userId, idempotencyKey);
            mine.complete(result);
            return result;
        } catch (RuntimeException failure) {
            // Nothing was decided, so the key must not be poisoned by it.
            attempts.remove(idempotencyKey, mine);
            mine.completeExceptionally(failure);
            throw failure;
        }
    }

    private ConfirmResult attemptConfirm(Show show, SeatLock seatLock, String userId, String key) {
        // Ten minutes is long enough for a show to begin, so the clock is
        // checked again here and before the card rather than only at selection.
        if (hasStarted(show)) {
            locks.release(seatLock.id(), userId);
            return new ConfirmResult.ShowStarted();
        }
        Money total = quote(show, seatLock.seatIds());
        if (!charge.test(key, total)) {
            locks.release(seatLock.id(), userId);
            return new ConfirmResult.PaymentDeclined();
        }
        if (!locks.confirm(seatLock.id(), userId)) {
            return new ConfirmResult.RefundNeeded("the seat lock expired while payment was in flight");
        }
        Booking booking = new Booking(UUID.randomUUID().toString(), show.id(), userId,
                seatLock.seatIds(), total);
        return new ConfirmResult.Confirmed(booking);
    }

    // Abandoning checkout should not make three other people wait ten minutes.
    public boolean abandon(SeatLock seatLock, String userId) {
        return locks.release(seatLock.id(), userId);
    }

    public void cancel(Booking booking) {
        booking.cancel();
        locks.releaseSold(booking.showId(), booking.seatIds());
    }

    private boolean hasStarted(Show show) {
        return !clock.instant().isBefore(show.startsAt());
    }
}

package com.androidinterview.movieticket.service;

import java.time.Clock;
import java.util.List;
import java.util.Optional;
import java.util.UUID;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.function.BiPredicate;

import com.androidinterview.movieticket.lock.SeatLock;
import com.androidinterview.movieticket.lock.SeatLockManager;
import com.androidinterview.movieticket.model.Booking;
import com.androidinterview.movieticket.model.Money;
import com.androidinterview.movieticket.model.Seat;
import com.androidinterview.movieticket.model.Show;
import com.androidinterview.movieticket.pricing.PricingStrategy;

public final class BookingService {

    private final SeatLockManager locks;
    private final PricingStrategy pricing;
    private final BiPredicate<String, Money> charge;
    private final Clock clock;

    private final ConcurrentMap<String, CompletableFuture<ConfirmResult>> attempts =
            new ConcurrentHashMap<>();

    public BookingService(SeatLockManager locks, PricingStrategy pricing,
                          BiPredicate<String, Money> charge, Clock clock) {
        this.locks = locks;
        this.pricing = pricing;
        this.charge = charge;
        this.clock = clock;
    }

    public List<Seat> availableSeats(Show show, String userId) {
        return locks.availableSeats(show, userId);
    }

    public Money quote(Show show, List<String> seatIds) {
        Money total = new Money(show.basePrice().currency(), 0);
        for (String seatId : seatIds) {
            Seat seat = show.screen().seatById(seatId);
            if (seat == null) {
                throw new IllegalArgumentException("no seat " + seatId + " in this screen");
            }
            total = total.plus(pricing.priceFor(show, seat));
        }
        return total;
    }

    public Optional<SeatLock> selectSeats(Show show, List<String> seatIds, String userId) {
        if (hasStarted(show)) {
            return Optional.empty();
        }
        return locks.lockSeats(show.id(), seatIds, userId);
    }

    public ConfirmResult confirm(Show show, SeatLock seatLock, String userId, String idempotencyKey) {
        CompletableFuture<ConfirmResult> mine = new CompletableFuture<>();
        CompletableFuture<ConfirmResult> running = attempts.putIfAbsent(idempotencyKey, mine);
        if (running != null) {
            ConfirmResult first = running.join();
            return first instanceof ConfirmResult.Confirmed done
                    ? new ConfirmResult.AlreadyConfirmed(done.booking())
                    : first;
        }
        try {
            ConfirmResult result = attemptConfirm(show, seatLock, userId, idempotencyKey);
            mine.complete(result);
            return result;
        } catch (RuntimeException failure) {
            attempts.remove(idempotencyKey, mine);
            mine.completeExceptionally(failure);
            throw failure;
        }
    }

    private ConfirmResult attemptConfirm(Show show, SeatLock seatLock, String userId, String key) {
        if (hasStarted(show)) {
            locks.release(seatLock.id(), userId);
            return new ConfirmResult.ShowStarted();
        }
        Money total = quote(show, seatLock.seatIds());
        if (!charge.test(key, total)) {
            locks.release(seatLock.id(), userId);
            return new ConfirmResult.PaymentDeclined();
        }
        if (!locks.confirm(seatLock.id(), userId)) {
            return new ConfirmResult.RefundNeeded("the seat lock expired while payment was in flight");
        }
        Booking booking = new Booking(UUID.randomUUID().toString(), show.id(), userId,
                seatLock.seatIds(), total);
        return new ConfirmResult.Confirmed(booking);
    }

    public boolean abandon(SeatLock seatLock, String userId) {
        return locks.release(seatLock.id(), userId);
    }

    public void cancel(Booking booking) {
        booking.cancel();
        locks.releaseSold(booking.showId(), booking.seatIds());
    }

    private boolean hasStarted(Show show) {
        return !clock.instant().isBefore(show.startsAt());
    }
}

package com.androidinterview.movieticket.service;

import com.androidinterview.movieticket.model.Booking;

// Five outcomes, not a boolean and not a nullable booking. Refund needed is the
// one everybody forgets, and it is the whole reason this is a type rather than
// an if statement.
public sealed interface ConfirmResult {

    record Confirmed(Booking booking) implements ConfirmResult {}

    record AlreadyConfirmed(Booking booking) implements ConfirmResult {}

    record PaymentDeclined() implements ConfirmResult {}

    // The house lights are already down. Nothing has been charged, because the
    // clock is checked before the card is.
    record ShowStarted() implements ConfirmResult {}

    // The seats were gone by the time the money arrived. The charge has to be
    // reversed and the user has to be told, and neither of those is optional.
    record RefundNeeded(String reason) implements ConfirmResult {}
}

package com.androidinterview.movieticket.service;

import com.androidinterview.movieticket.model.Booking;

public sealed interface ConfirmResult {

    record Confirmed(Booking booking) implements ConfirmResult {}

    record AlreadyConfirmed(Booking booking) implements ConfirmResult {}

    record PaymentDeclined() implements ConfirmResult {}

    record ShowStarted() implements ConfirmResult {}

    record RefundNeeded(String reason) implements ConfirmResult {}
}

package com.androidinterview.movieticket.lock

import com.androidinterview.movieticket.model.Seat
import com.androidinterview.movieticket.model.Show
import java.time.Clock
import java.time.Duration
import java.time.Instant
import java.util.UUID
import java.util.concurrent.locks.ReentrantLock
import kotlin.concurrent.withLock

// The identity of one seat at one show. A data class rather than a joined
// string, so a typo is a compile error instead of a silent miss.
data class SeatKey(val showId: String, val seatId: String)

// A temporary claim on some named seats. The user is on the record because
// release has to check it, and the expiry is an absolute instant so any process
// can judge it without a timer of its own.
data class SeatLock(
    val id: String,
    val showId: String,
    val seatIds: List<String>,
    val userId: String,
    val expiresAt: Instant,
) {
    fun isExpiredAt(now: Instant) = now >= expiresAt
}

// The whole problem lives here. A seat at a show is free, locked by somebody who
// is paying, or sold. This class owns all three and owns the only lock.
//
// A hotel counts rooms and this counts nothing, because seats are named. That is
// why this is a map of seat keys rather than a set of counters.
//
// Be honest about the lock. This is one process. A real ticketing platform runs
// many servers, so the guarantee has to come from a shared store, either a row
// per seat updated conditionally in a transaction or a short lived key per seat.
class SeatLockManager(private val clock: Clock, private val ttl: Duration) {

    private val locksBySeat = mutableMapOf<SeatKey, SeatLock>()
    private val byLockId = mutableMapOf<String, SeatLock>()
    private val sold = mutableSetOf<SeatKey>()
    private val guard = ReentrantLock()

    // A seat the caller is holding is shown as available to that caller, because
    // refreshing the seat map in the middle of your own checkout should not tell
    // you your seats are gone.
    fun availableSeats(show: Show, userId: String): List<Seat> = guard.withLock {
        sweepExpired()
        show.screen.seats.filter { seat ->
            val key = SeatKey(show.id, seat.id)
            val held = locksBySeat[key]
            key !in sold && (held == null || held.userId == userId)
        }
    }

    // All the seats or none of them. Four friends given three seats together is
    // worse than four friends given nothing, so every seat is checked before
    // anything is written.
    //
    // The ids are sorted first and repeats are dropped. That canonical order is
    // not needed while one lock covers the whole map, but it is exactly what a
    // per seat scheme would need to avoid deadlock, so it belongs in the design
    // now.
    fun lockSeats(showId: String, seatIds: List<String>, userId: String): SeatLock? = guard.withLock {
        sweepExpired()
        val ordered = seatIds.distinct().sorted()
        val keys = ordered.map { SeatKey(showId, it) }
        if (keys.any { it in sold || it in locksBySeat }) return@withLock null

        SeatLock(UUID.randomUUID().toString(), showId, ordered, userId, clock.instant().plus(ttl))
            .also { held ->
                keys.forEach { locksBySeat[it] = held }
                byLockId[held.id] = held
            }
    }

    // Owner checked. Without this comparison the sweeper, or a stale request
    // from an abandoned tab, frees seats that a different user acquired a moment
    // ago and is already paying for.
    fun release(lockId: String, userId: String): Boolean = guard.withLock {
        val held = findById(lockId)
        if (held == null || held.userId != userId) return@withLock false
        remove(held)
        true
    }

    // The compare and set. It judges the expiry itself rather than trusting the
    // sweeper to have run, so the payment callback and the sweeper cannot both
    // believe they won. A false here means money has been taken and has to go
    // back, which is a real outcome and not an edge case.
    fun confirm(lockId: String, userId: String): Boolean = guard.withLock {
        val held = findById(lockId)
        if (held == null || held.userId != userId) return@withLock false
        remove(held)
        if (held.isExpiredAt(clock.instant())) return@withLock false
        held.seatIds.forEach { sold += SeatKey(held.showId, it) }
        true
    }

    fun releaseSold(showId: String, seatIds: List<String>) = guard.withLock {
        seatIds.forEach { sold -= SeatKey(showId, it) }
    }

    // A scheduled job in production. Driven from every read here so a test can
    // advance a fixed Clock instead of sleeping.
    fun sweepExpired(): Int = guard.withLock {
        val now = clock.instant()
        val stale = byLockId.values.filter { it.isExpiredAt(now) }.toList()
        stale.forEach { remove(it) }
        stale.size
    }

    // Keyed by lock id as well as by seat, so confirm is a lookup rather than a
    // walk over every locked seat in a full house.
    private fun findById(lockId: String) = byLockId[lockId]

    private fun remove(held: SeatLock) {
        held.seatIds.forEach { locksBySeat.remove(SeatKey(held.showId, it)) }
        byLockId.remove(held.id)
    }
}

package com.androidinterview.movieticket.lock

import com.androidinterview.movieticket.model.Seat
import com.androidinterview.movieticket.model.Show
import java.time.Clock
import java.time.Duration
import java.time.Instant
import java.util.UUID
import java.util.concurrent.locks.ReentrantLock
import kotlin.concurrent.withLock

data class SeatKey(val showId: String, val seatId: String)

data class SeatLock(
    val id: String,
    val showId: String,
    val seatIds: List<String>,
    val userId: String,
    val expiresAt: Instant,
) {
    fun isExpiredAt(now: Instant) = now >= expiresAt
}

class SeatLockManager(private val clock: Clock, private val ttl: Duration) {

    private val locksBySeat = mutableMapOf<SeatKey, SeatLock>()
    private val byLockId = mutableMapOf<String, SeatLock>()
    private val sold = mutableSetOf<SeatKey>()
    private val guard = ReentrantLock()

    fun availableSeats(show: Show, userId: String): List<Seat> = guard.withLock {
        sweepExpired()
        show.screen.seats.filter { seat ->
            val key = SeatKey(show.id, seat.id)
            val held = locksBySeat[key]
            key !in sold && (held == null || held.userId == userId)
        }
    }

    fun lockSeats(showId: String, seatIds: List<String>, userId: String): SeatLock? = guard.withLock {
        sweepExpired()
        val ordered = seatIds.distinct().sorted()
        val keys = ordered.map { SeatKey(showId, it) }
        if (keys.any { it in sold || it in locksBySeat }) return@withLock null

        SeatLock(UUID.randomUUID().toString(), showId, ordered, userId, clock.instant().plus(ttl))
            .also { held ->
                keys.forEach { locksBySeat[it] = held }
                byLockId[held.id] = held
            }
    }

    fun release(lockId: String, userId: String): Boolean = guard.withLock {
        val held = findById(lockId)
        if (held == null || held.userId != userId) return@withLock false
        remove(held)
        true
    }

    fun confirm(lockId: String, userId: String): Boolean = guard.withLock {
        val held = findById(lockId)
        if (held == null || held.userId != userId) return@withLock false
        remove(held)
        if (held.isExpiredAt(clock.instant())) return@withLock false
        held.seatIds.forEach { sold += SeatKey(held.showId, it) }
        true
    }

    fun releaseSold(showId: String, seatIds: List<String>) = guard.withLock {
        seatIds.forEach { sold -= SeatKey(showId, it) }
    }

    fun sweepExpired(): Int = guard.withLock {
        val now = clock.instant()
        val stale = byLockId.values.filter { it.isExpiredAt(now) }.toList()
        stale.forEach { remove(it) }
        stale.size
    }

    private fun findById(lockId: String) = byLockId[lockId]

    private fun remove(held: SeatLock) {
        held.seatIds.forEach { locksBySeat.remove(SeatKey(held.showId, it)) }
        byLockId.remove(held.id)
    }
}

package com.androidinterview.movieticket.model

import java.time.Duration
import java.time.Instant
import kotlin.math.roundToLong

data class Money(val currency: String, val amount: Long) {
    operator fun plus(other: Money) = copy(amount = amount + other.amount)
    operator fun times(factor: Double) = copy(amount = (amount * factor).roundToLong())
    fun percentOf(basisPoints: Int) = copy(amount = (amount * basisPoints / 10000.0).roundToLong())
}

data class Movie(val id: String, val title: String, val language: String, val runtime: Duration)

// The price multiplier rides on the tier, so nothing else writes a when over
// seat classes. A recliner tier is one line.
enum class SeatTier(val multiplier: Double) {
    SILVER(1.0),
    GOLD(1.5),
    PLATINUM(2.0),
}

// A physical seat in a screen. It carries no availability of its own, and that
// is the point. The same seat is free at six and taken at nine, so availability
// belongs to the pair of a show and a seat.
data class Seat(val id: String, val row: String, val number: Int, val tier: SeatTier)

// A screen and the seats in it. The lookup by id is built once, because pricing
// a basket of seats should not walk the whole auditorium per seat, and because
// an id nobody recognises has to be rejected rather than quietly skipped.
class Screen(val id: String, val name: String, val seats: List<Seat>) {
    private val byId = seats.associateBy { it.id }
    fun seatById(seatId: String): Seat? = byId[seatId]
}

data class Cinema(val id: String, val name: String, val city: String, val screens: List<Screen>)

// A movie on a screen at a time. This is what tickets are sold against, and its
// id is half of every inventory key in the system.
data class Show(
    val id: String,
    val movie: Movie,
    val screen: Screen,
    val startsAt: Instant,
    val basePrice: Money,
)

// A confirmed set of seats. There is no pending state here on purpose. Pending
// is what the seat lock is, and it lives where it can expire.
class Booking(
    val id: String,
    val showId: String,
    val userId: String,
    val seatIds: List<String>,
    val total: Money,
) {
    var cancelled: Boolean = false
        private set

    fun cancel() {
        check(!cancelled) { "this booking is already cancelled" }
        cancelled = true
    }
}

package com.androidinterview.movieticket.model

import java.time.Duration
import java.time.Instant
import kotlin.math.roundToLong

data class Money(val currency: String, val amount: Long) {
    operator fun plus(other: Money) = copy(amount = amount + other.amount)
    operator fun times(factor: Double) = copy(amount = (amount * factor).roundToLong())
    fun percentOf(basisPoints: Int) = copy(amount = (amount * basisPoints / 10000.0).roundToLong())
}

data class Movie(val id: String, val title: String, val language: String, val runtime: Duration)

enum class SeatTier(val multiplier: Double) {
    SILVER(1.0),
    GOLD(1.5),
    PLATINUM(2.0),
}

data class Seat(val id: String, val row: String, val number: Int, val tier: SeatTier)

class Screen(val id: String, val name: String, val seats: List<Seat>) {
    private val byId = seats.associateBy { it.id }
    fun seatById(seatId: String): Seat? = byId[seatId]
}

data class Cinema(val id: String, val name: String, val city: String, val screens: List<Screen>)

data class Show(
    val id: String,
    val movie: Movie,
    val screen: Screen,
    val startsAt: Instant,
    val basePrice: Money,
)

class Booking(
    val id: String,
    val showId: String,
    val userId: String,
    val seatIds: List<String>,
    val total: Money,
) {
    var cancelled: Boolean = false
        private set

    fun cancel() {
        check(!cancelled) { "this booking is already cancelled" }
        cancelled = true
    }
}

package com.androidinterview.movieticket.pricing

import com.androidinterview.movieticket.model.Money
import com.androidinterview.movieticket.model.Seat
import com.androidinterview.movieticket.model.Show

// Priced per seat, not per booking, because a booking can mix tiers.
fun interface PricingStrategy {
    fun priceFor(show: Show, seat: Seat): Money
}

val tierPricing = PricingStrategy { show, seat -> show.basePrice * seat.tier.multiplier }

// A weekend or a premiere rule wraps the tier rule rather than replacing it, the
// same way surge wraps ride pricing. Wrapping composes. Siblings multiply.
fun PricingStrategy.withSurcharge(basisPoints: Int, applies: (Show) -> Boolean) =
    PricingStrategy { show, seat ->
        val base = priceFor(show, seat)
        if (applies(show)) base + base.percentOf(basisPoints) else base
    }

package com.androidinterview.movieticket.pricing

import com.androidinterview.movieticket.model.Money
import com.androidinterview.movieticket.model.Seat
import com.androidinterview.movieticket.model.Show

fun interface PricingStrategy {
    fun priceFor(show: Show, seat: Seat): Money
}

val tierPricing = PricingStrategy { show, seat -> show.basePrice * seat.tier.multiplier }

fun PricingStrategy.withSurcharge(basisPoints: Int, applies: (Show) -> Boolean) =
    PricingStrategy { show, seat ->
        val base = priceFor(show, seat)
        if (applies(show)) base + base.percentOf(basisPoints) else base
    }

package com.androidinterview.movieticket.service

import com.androidinterview.movieticket.lock.SeatLock
import com.androidinterview.movieticket.lock.SeatLockManager
import com.androidinterview.movieticket.model.Booking
import com.androidinterview.movieticket.model.Money
import com.androidinterview.movieticket.model.Seat
import com.androidinterview.movieticket.model.Show
import com.androidinterview.movieticket.pricing.PricingStrategy
import java.time.Clock
import java.util.UUID
import java.util.concurrent.CompletableFuture
import java.util.concurrent.ConcurrentHashMap

// Five outcomes, not a boolean and not a nullable booking. Refund needed is the
// one everybody forgets, and it is the whole reason this is a type.
sealed interface ConfirmResult {
    data class Confirmed(val booking: Booking) : ConfirmResult
    data class AlreadyConfirmed(val booking: Booking) : ConfirmResult
    data object PaymentDeclined : ConfirmResult

    // The house lights are already down. Nothing has been charged, because the
    // clock is checked before the card is.
    data object ShowStarted : ConfirmResult

    // The seats were gone by the time the money arrived. The charge has to be
    // reversed and the user has to be told, and neither is optional.
    data class RefundNeeded(val reason: String) : ConfirmResult
}

// The one class the app talks to. It sequences selection, payment and
// confirmation and owns none of the rules.
//
// Payment is a function type rather than a gateway interface, because card
// handling is a different interview. The key is what makes a retry safe.
class BookingService(
    private val locks: SeatLockManager,
    private val pricing: PricingStrategy,
    private val charge: (idempotencyKey: String, amount: Money) -> Boolean,
    private val clock: Clock,
) {
    // One entry per idempotency key, claimed before the card is touched. A
    // plain map read followed by a write would let two copies of the same
    // request both miss and both charge, which is the exact bug this map is
    // here to prevent.
    private val attempts = ConcurrentHashMap<String, CompletableFuture<ConfirmResult>>()

    fun availableSeats(show: Show, userId: String): List<Seat> = locks.availableSeats(show, userId)

    // Every requested seat has to exist in this screen. Skipping the ones that
    // do not would quote a lower total and then charge it.
    fun quote(show: Show, seatIds: List<String>): Money =
        seatIds.fold(Money(show.basePrice.currency, 0)) { running, seatId ->
            val seat = requireNotNull(show.screen.seatById(seatId)) { "no seat $seatId in this screen" }
            running + pricing.priceFor(show, seat)
        }

    // Selection takes the lock. Nothing is charged and nothing is sold yet, and
    // the clock is now running. A show that has already started sells nothing,
    // so the request is refused here rather than ten minutes later.
    fun selectSeats(show: Show, seatIds: List<String>, userId: String): SeatLock? =
        if (hasStarted(show)) null else locks.lockSeats(show.id, seatIds, userId)

    // The order here is the answer to the hardest follow up in this problem.
    // Charge first, then confirm, because a cinema seat cannot be sold twice and
    // a refund is a real remedy. If the lock died while the bank was thinking,
    // the seats may already belong to somebody else.
    //
    // The key is claimed before any of that. One key, one answer, so a retry
    // that arrives while the first request is still at the bank waits for it
    // and reads its outcome rather than charging the card a second time.
    fun confirm(show: Show, seatLock: SeatLock, userId: String, idempotencyKey: String): ConfirmResult {
        val mine = CompletableFuture<ConfirmResult>()
        attempts.putIfAbsent(idempotencyKey, mine)?.let { running ->
            val first = running.join()
            return if (first is ConfirmResult.Confirmed) ConfirmResult.AlreadyConfirmed(first.booking) else first
        }
        return runCatching { attemptConfirm(show, seatLock, userId, idempotencyKey) }
            .onSuccess { mine.complete(it) }
            .onFailure {
                // Nothing was decided, so the key must not be poisoned by it.
                attempts.remove(idempotencyKey, mine)
                mine.completeExceptionally(it)
            }
            .getOrThrow()
    }

    private fun attemptConfirm(show: Show, seatLock: SeatLock, userId: String, key: String): ConfirmResult {
        // Ten minutes is long enough for a show to begin, so the clock is
        // checked again here and before the card rather than only at selection.
        if (hasStarted(show)) {
            locks.release(seatLock.id, userId)
            return ConfirmResult.ShowStarted
        }
        val total = quote(show, seatLock.seatIds)
        if (!charge(key, total)) {
            locks.release(seatLock.id, userId)
            return ConfirmResult.PaymentDeclined
        }
        if (!locks.confirm(seatLock.id, userId)) {
            return ConfirmResult.RefundNeeded("the seat lock expired while payment was in flight")
        }
        return ConfirmResult.Confirmed(
            Booking(UUID.randomUUID().toString(), show.id, userId, seatLock.seatIds, total),
        )
    }

    // Abandoning checkout should not make three other people wait ten minutes.
    fun abandon(seatLock: SeatLock, userId: String) = locks.release(seatLock.id, userId)

    fun cancel(booking: Booking) {
        booking.cancel()
        locks.releaseSold(booking.showId, booking.seatIds)
    }

    private fun hasStarted(show: Show) = !clock.instant().isBefore(show.startsAt)
}

package com.androidinterview.movieticket.service

import com.androidinterview.movieticket.lock.SeatLock
import com.androidinterview.movieticket.lock.SeatLockManager
import com.androidinterview.movieticket.model.Booking
import com.androidinterview.movieticket.model.Money
import com.androidinterview.movieticket.model.Seat
import com.androidinterview.movieticket.model.Show
import com.androidinterview.movieticket.pricing.PricingStrategy
import java.time.Clock
import java.util.UUID
import java.util.concurrent.CompletableFuture
import java.util.concurrent.ConcurrentHashMap

sealed interface ConfirmResult {
    data class Confirmed(val booking: Booking) : ConfirmResult
    data class AlreadyConfirmed(val booking: Booking) : ConfirmResult
    data object PaymentDeclined : ConfirmResult

    data object ShowStarted : ConfirmResult

    data class RefundNeeded(val reason: String) : ConfirmResult
}

class BookingService(
    private val locks: SeatLockManager,
    private val pricing: PricingStrategy,
    private val charge: (idempotencyKey: String, amount: Money) -> Boolean,
    private val clock: Clock,
) {
    private val attempts = ConcurrentHashMap<String, CompletableFuture<ConfirmResult>>()

    fun availableSeats(show: Show, userId: String): List<Seat> = locks.availableSeats(show, userId)

    fun quote(show: Show, seatIds: List<String>): Money =
        seatIds.fold(Money(show.basePrice.currency, 0)) { running, seatId ->
            val seat = requireNotNull(show.screen.seatById(seatId)) { "no seat $seatId in this screen" }
            running + pricing.priceFor(show, seat)
        }

    fun selectSeats(show: Show, seatIds: List<String>, userId: String): SeatLock? =
        if (hasStarted(show)) null else locks.lockSeats(show.id, seatIds, userId)

    fun confirm(show: Show, seatLock: SeatLock, userId: String, idempotencyKey: String): ConfirmResult {
        val mine = CompletableFuture<ConfirmResult>()
        attempts.putIfAbsent(idempotencyKey, mine)?.let { running ->
            val first = running.join()
            return if (first is ConfirmResult.Confirmed) ConfirmResult.AlreadyConfirmed(first.booking) else first
        }
        return runCatching { attemptConfirm(show, seatLock, userId, idempotencyKey) }
            .onSuccess { mine.complete(it) }
            .onFailure {
                attempts.remove(idempotencyKey, mine)
                mine.completeExceptionally(it)
            }
            .getOrThrow()
    }

    private fun attemptConfirm(show: Show, seatLock: SeatLock, userId: String, key: String): ConfirmResult {
        if (hasStarted(show)) {
            locks.release(seatLock.id, userId)
            return ConfirmResult.ShowStarted
        }
        val total = quote(show, seatLock.seatIds)
        if (!charge(key, total)) {
            locks.release(seatLock.id, userId)
            return ConfirmResult.PaymentDeclined
        }
        if (!locks.confirm(seatLock.id, userId)) {
            return ConfirmResult.RefundNeeded("the seat lock expired while payment was in flight")
        }
        return ConfirmResult.Confirmed(
            Booking(UUID.randomUUID().toString(), show.id, userId, seatLock.seatIds, total),
        )
    }

    fun abandon(seatLock: SeatLock, userId: String) = locks.release(seatLock.id, userId)

    fun cancel(booking: Booking) {
        booking.cancel()
        locks.releaseSold(booking.showId, booking.seatIds)
    }

    private fun hasStarted(show: Show) = !clock.instant().isBefore(show.startsAt)
}