Design Booking.com

package com.androidinterview.bookingcom.inventory;

import java.time.LocalDate;
import java.util.HashMap;
import java.util.Map;

import com.androidinterview.bookingcom.model.DateRange;

// The class most candidates forget, and the one the answer rests on.
// Availability is a question about a room type on a single night, so the key
// is that pair and nothing smaller.
public final class AvailabilityCalendar {

    private record Key(String roomTypeId, LocalDate night) {}

    private final Map<Key, NightInventory> nights = new HashMap<>();

    public void openRooms(String roomTypeId, DateRange range, int total) {
        for (LocalDate night : range.nights()) {
            nights.put(new Key(roomTypeId, night), new NightInventory(total));
        }
    }

    NightInventory at(String roomTypeId, LocalDate night) {
        return nights.get(new Key(roomTypeId, night));
    }

    // A stay is available only if every night in it is. One sold out night in
    // the middle makes the whole stay unbookable, which is why this walks the
    // nights instead of reading one row. Package private, because the read has
    // to happen under the hold manager's lock like every other touch of a
    // night, so the service asks the hold manager rather than the calendar.
    boolean isAvailable(String roomTypeId, DateRange range, int rooms) {
        for (LocalDate night : range.nights()) {
            NightInventory inventory = at(roomTypeId, night);
            if (inventory == null || inventory.available() < rooms) {
                return false;
            }
        }
        return true;
    }
}

package com.androidinterview.bookingcom.inventory;

import java.time.Instant;

import com.androidinterview.bookingcom.model.DateRange;

// A claim on some room nights that expires by itself. The owner is on the
// record because release has to check it, and the expiry is an absolute
// instant rather than a duration so any process can judge it.
public record Hold(
        String id,
        String roomTypeId,
        String ownerId,
        DateRange stay,
        int rooms,
        Instant expiresAt) {

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

package com.androidinterview.bookingcom.inventory;

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

import com.androidinterview.bookingcom.model.DateRange;

// The centre of this problem. A hold moves room nights from available to
// held, a confirm moves them from held to booked, and a sweeper puts back
// anything nobody paid for. Search reads through here too, so a reader and a
// writer never see a night half updated.
//
// Be honest about the lock. This is one process. A real platform runs many
// servers against one database, so the same guarantee has to come from the
// database, as an update that increments held only where enough is left and
// then checks the row count.
public final class HoldManager {

    private final AvailabilityCalendar calendar;
    private final Clock clock;
    private final Duration ttl;
    private final Map<String, Hold> holds = new HashMap<>();
    private final Object lock = new Object();

    public HoldManager(AvailabilityCalendar calendar, Clock clock, Duration ttl) {
        this.calendar = calendar;
        this.clock = clock;
        this.ttl = ttl;
    }

    // The read search uses. It takes the same lock as the writes, which is
    // correct and slow. In production this read comes from a replica or a
    // cached count, and the hold re-checks under the real lock.
    public boolean isAvailable(String roomTypeId, DateRange stay, int rooms) {
        synchronized (lock) {
            expireStaleHolds();
            return calendar.isAvailable(roomTypeId, stay, rooms);
        }
    }

    // All nights or none. DateRange hands the nights back ascending, and that
    // canonical order is what stops two overlapping stays from each taking
    // half of what the other one needs.
    public Optional<Hold> hold(String roomTypeId, DateRange stay, String ownerId, int rooms) {
        synchronized (lock) {
            expireStaleHolds();
            List<NightInventory> taken = new ArrayList<>();
            for (LocalDate night : stay.nights()) {
                NightInventory inventory = calendar.at(roomTypeId, night);
                if (inventory == null || inventory.available() < rooms) {
                    taken.forEach(already -> already.releaseHold(rooms));
                    return Optional.empty();
                }
                inventory.hold(rooms);
                taken.add(inventory);
            }
            Hold hold = new Hold(UUID.randomUUID().toString(), roomTypeId, ownerId,
                    stay, rooms, clock.instant().plus(ttl));
            holds.put(hold.id(), hold);
            return Optional.of(hold);
        }
    }

    // Owner checked, and that one comparison is the point. Without it the
    // sweeper can free a hold a different guest acquired a moment earlier, and
    // that guest pays for a room somebody else is already taking.
    public boolean release(String holdId, String ownerId) {
        synchronized (lock) {
            Hold hold = holds.get(holdId);
            if (hold == null || !hold.ownerId().equals(ownerId)) {
                return false;
            }
            holds.remove(holdId);
            giveBack(hold);
            return true;
        }
    }

    // A compare and set. It judges the expiry itself rather than trusting the
    // sweeper to have run, so the payment worker and the sweeper can never
    // both believe they won.
    public boolean confirm(String holdId, String ownerId) {
        synchronized (lock) {
            Hold hold = holds.get(holdId);
            if (hold == null || !hold.ownerId().equals(ownerId)) {
                return false;
            }
            holds.remove(holdId);
            if (hold.isExpiredAt(clock.instant())) {
                giveBack(hold);
                return false;
            }
            for (LocalDate night : hold.stay().nights()) {
                calendar.at(hold.roomTypeId(), night).commit(hold.rooms());
            }
            return true;
        }
    }

    // A scheduled job in production. Called inline here too, so a test can
    // drive it with a fixed Clock instead of sleeping.
    public int expireStaleHolds() {
        synchronized (lock) {
            Instant now = clock.instant();
            int expired = 0;
            for (Hold hold : List.copyOf(holds.values())) {
                if (hold.isExpiredAt(now)) {
                    holds.remove(hold.id());
                    giveBack(hold);
                    expired++;
                }
            }
            return expired;
        }
    }

    // Cancelling a confirmed booking gives the nights back to the pool.
    public void releaseBooking(String roomTypeId, DateRange stay, int rooms) {
        synchronized (lock) {
            for (LocalDate night : stay.nights()) {
                calendar.at(roomTypeId, night).releaseBooking(rooms);
            }
        }
    }

    private void giveBack(Hold hold) {
        for (LocalDate night : hold.stay().nights()) {
            calendar.at(hold.roomTypeId(), night).releaseHold(hold.rooms());
        }
    }
}

package com.androidinterview.bookingcom.inventory;

// One room type on one night. Three counters, not two, because a model that
// knows only available and booked cannot say that somebody is part way
// through checkout and has not paid yet.
//
// Package private, and it does no locking. Everything that touches it runs
// inside the hold manager's critical section, and a lock split across two
// classes is how you get two half correct ones.
final class NightInventory {

    private final int total;
    private int held;
    private int booked;

    NightInventory(int total) {
        this.total = total;
    }

    int available() {
        return total - held - booked;
    }

    void hold(int rooms) {
        held += rooms;
    }

    void releaseHold(int rooms) {
        held -= rooms;
    }

    // Held becomes booked in one step. Releasing first and booking second
    // would open a window in which another guest takes the room this guest
    // has just paid for.
    void commit(int rooms) {
        held -= rooms;
        booked += rooms;
    }

    void releaseBooking(int rooms) {
        booked -= rooms;
    }
}

package com.androidinterview.bookingcom.model;

// One reservation. It is pending from the moment the service claims the
// idempotency key for it until the card is charged, and the service keys
// bookings by that idempotency key, so a retried request finds the booking it
// already made instead of making a second one and charging the guest twice.
public final class Booking {

    private final String id;
    private final Guest guest;
    private final RoomType roomType;
    private final DateRange stay;
    private final int rooms;
    private final Money total;
    private BookingStatus status = BookingStatus.PENDING;

    public Booking(String id, Guest guest, RoomType roomType, DateRange stay, int rooms, Money total) {
        this.id = id;
        this.guest = guest;
        this.roomType = roomType;
        this.stay = stay;
        this.rooms = rooms;
        this.total = total;
    }

    public String id() { return id; }
    public Guest guest() { return guest; }
    public RoomType roomType() { return roomType; }
    public DateRange stay() { return stay; }
    public int rooms() { return rooms; }
    public Money total() { return total; }
    public BookingStatus status() { return status; }

    // The only way status ever changes, so no caller anywhere can move a
    // cancelled booking to checked in.
    public void moveTo(BookingStatus next) {
        if (!status.canMoveTo(next)) {
            throw new IllegalStateException("cannot move from " + status + " to " + next);
        }
        status = next;
    }
}

package com.androidinterview.bookingcom.model;

// The lifecycle, with the legal moves written down once. A switch here beats
// a guard at every call site, because the illegal moves are all visible in
// one place and a new status is one line.
public enum BookingStatus {
    PENDING,
    CONFIRMED,
    CHECKED_IN,
    COMPLETED,
    CANCELLED;

    public boolean canMoveTo(BookingStatus next) {
        return switch (this) {
            case PENDING -> next == CONFIRMED || next == CANCELLED;
            case CONFIRMED -> next == CHECKED_IN || next == CANCELLED;
            case CHECKED_IN -> next == COMPLETED;
            case COMPLETED, CANCELLED -> false;
        };
    }
}

package com.androidinterview.bookingcom.model;

import java.time.LocalDate;
import java.util.ArrayList;
import java.util.List;

// A stay is a half open range. The check out date is not a night, so a guest
// leaving on the third and a guest arriving on the third never collide.
public record DateRange(LocalDate checkIn, LocalDate checkOut) {

    public DateRange {
        if (!checkOut.isAfter(checkIn)) {
            throw new IllegalArgumentException("check out must be after check in");
        }
    }

    public int nightCount() {
        return (int) (checkOut.toEpochDay() - checkIn.toEpochDay());
    }

    // Ascending, always. Multi night holds take nights in this order, and that
    // canonical order is what stops two overlapping stays from deadlocking.
    public List<LocalDate> nights() {
        List<LocalDate> nights = new ArrayList<>();
        for (LocalDate night = checkIn; night.isBefore(checkOut); night = night.plusDays(1)) {
            nights.add(night);
        }
        return nights;
    }
}

package com.androidinterview.bookingcom.model;

public record Guest(String id, String name, String email) {
}

package com.androidinterview.bookingcom.model;

// Minor units and a currency, never a double. Rounding a floating point price
// is how a booking total ends up a cent away from what the card was charged.
public record Money(String currency, long amount) {

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

    public Money times(long factor) {
        return new Money(currency, amount * factor);
    }

    // Percentages arrive as basis points so no caller can hand us a double.
    // 1050 basis points is ten and a half percent.
    public Money percentOf(int basisPoints) {
        return new Money(currency, Math.round(amount * basisPoints / 10000.0));
    }
}

package com.androidinterview.bookingcom.model;

import java.util.List;
import java.util.Set;

// One listing in the marketplace. A property owns its room types, and that is
// the only ownership arrow in this model worth drawing.
public record Property(
        String id,
        String name,
        String city,
        double rating,
        Set<String> amenities,
        List<RoomType> roomTypes) {
}

package com.androidinterview.bookingcom.model;

// Inventory hangs off a room type, not off a room. A guest books a double
// room and is allocated a physical room number at check in, which is what
// real properties do, and it turns availability into a counter rather than a
// flag on a row.
public record RoomType(
        String id,
        String propertyId,
        String name,
        int maxOccupancy,
        Money baseRatePerNight) {
}

package com.androidinterview.bookingcom.pricing;

import com.androidinterview.bookingcom.model.DateRange;
import com.androidinterview.bookingcom.model.Money;
import com.androidinterview.bookingcom.model.RoomType;

// The rule everything else wraps. Rate times nights, nothing clever.
public final class BaseRatePricing implements PricingStrategy {

    @Override
    public Money quote(RoomType roomType, DateRange stay) {
        return roomType.baseRatePerNight().times(stay.nightCount());
    }
}

package com.androidinterview.bookingcom.pricing;

import com.androidinterview.bookingcom.model.DateRange;
import com.androidinterview.bookingcom.model.Money;
import com.androidinterview.bookingcom.model.RoomType;

// Add ons are the textbook case for a decorator. They stack in any order,
// each adds to the price, and nothing downstream needs to know how many are
// on the booking.
public final class BreakfastAddOn implements PricingStrategy {

    private final PricingStrategy inner;
    private final Money perGuestPerNight;
    private final int guests;

    public BreakfastAddOn(PricingStrategy inner, Money perGuestPerNight, int guests) {
        this.inner = inner;
        this.perGuestPerNight = perGuestPerNight;
        this.guests = guests;
    }

    @Override
    public Money quote(RoomType roomType, DateRange stay) {
        Money extra = perGuestPerNight.times((long) guests * stay.nightCount());
        return inner.quote(roomType, stay).plus(extra);
    }
}

package com.androidinterview.bookingcom.pricing;

import com.androidinterview.bookingcom.model.DateRange;
import com.androidinterview.bookingcom.model.Money;
import com.androidinterview.bookingcom.model.RoomType;

// One seam for every price rule. Anything that changes a total, a seasonal
// rate, a length of stay discount, breakfast for two, is either a strategy or
// a wrapper around one, so the booking service never grows a pricing branch.
public interface PricingStrategy {
    Money quote(RoomType roomType, DateRange stay);
}

package com.androidinterview.bookingcom.pricing;

import java.time.Month;
import java.util.Set;

import com.androidinterview.bookingcom.model.DateRange;
import com.androidinterview.bookingcom.model.Money;
import com.androidinterview.bookingcom.model.RoomType;

// A decorator, not a sibling. Seasonal pricing is a modifier on whatever the
// rule underneath produced, so wrapping composes with every other rule. Make
// it a sibling implementation instead and you need one class per combination
// of season, stay length and add on.
public final class SeasonalSurcharge implements PricingStrategy {

    private final PricingStrategy inner;
    private final Set<Month> peakMonths;
    private final int surchargeBasisPoints;

    public SeasonalSurcharge(PricingStrategy inner, Set<Month> peakMonths, int surchargeBasisPoints) {
        this.inner = inner;
        this.peakMonths = Set.copyOf(peakMonths);
        this.surchargeBasisPoints = surchargeBasisPoints;
    }

    @Override
    public Money quote(RoomType roomType, DateRange stay) {
        Money base = inner.quote(roomType, stay);
        long peakNights = stay.nights().stream()
                .filter(night -> peakMonths.contains(night.getMonth()))
                .count();
        if (peakNights == 0) {
            return base;
        }
        // The surcharge applies to the peak share of the stay, rounded down to
        // whole basis points, so a booking that straddles the end of a season
        // is not charged peak throughout.
        int share = (int) (surchargeBasisPoints * peakNights / stay.nightCount());
        return base.plus(base.percentOf(share));
    }
}

package com.androidinterview.bookingcom.search;

import java.util.function.Predicate;

import com.androidinterview.bookingcom.model.Property;

// Search filters compose, so each one is a named predicate and the filter
// panel becomes a chain of ands. Java already has the combinator, so a
// Specification interface would be a second name for Predicate. Write the
// interface only when the filters also have to become a database query, which
// is the point where a predicate cannot follow you.
public final class PropertySpecs {

    private PropertySpecs() {
    }

    public static Predicate<Property> inCity(String city) {
        return property -> property.city().equalsIgnoreCase(city);
    }

    public static Predicate<Property> ratedAtLeast(double rating) {
        return property -> property.rating() >= rating;
    }

    public static Predicate<Property> hasAmenity(String amenity) {
        return property -> property.amenities().contains(amenity);
    }

    public static Predicate<Property> sleeps(int guests) {
        return property -> property.roomTypes().stream()
                .anyMatch(roomType -> roomType.maxOccupancy() >= guests);
    }
}

package com.androidinterview.bookingcom.service;

import com.androidinterview.bookingcom.model.Booking;

// Four outcomes, not a nullable booking. An Optional would collapse a lost hold
// and a declined card into one empty, and the guest needs a different message
// for each. AlreadyBooked carries the booking the first request made, or is
// still making, which is how a retry finds its way back to the same reservation.
public sealed interface BookingResult {

    record Confirmed(Booking booking) implements BookingResult {}

    record AlreadyBooked(Booking booking) implements BookingResult {}

    record PaymentDeclined(Booking booking) implements BookingResult {}

    record HoldExpired() implements BookingResult {}
}

package com.androidinterview.bookingcom.service;

import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.UUID;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Predicate;

import com.androidinterview.bookingcom.inventory.Hold;
import com.androidinterview.bookingcom.inventory.HoldManager;
import com.androidinterview.bookingcom.model.Booking;
import com.androidinterview.bookingcom.model.BookingStatus;
import com.androidinterview.bookingcom.model.DateRange;
import com.androidinterview.bookingcom.model.Guest;
import com.androidinterview.bookingcom.model.Money;
import com.androidinterview.bookingcom.model.Property;
import com.androidinterview.bookingcom.model.RoomType;
import com.androidinterview.bookingcom.pricing.PricingStrategy;

// The one class the outside world talks to. It sequences the steps and owns
// the bookkeeping. It owns no rules, because pricing is a strategy it was
// handed and inventory belongs to the hold manager. It never touches the
// calendar directly, every read and write of a night goes through the hold
// manager and its lock.
public final class BookingService {

    private final HoldManager holds;
    private final PricingStrategy pricing;
    private final PaymentGateway payments;
    // A concurrent map, because the reservation of a key has to be one atomic
    // step. A plain map with a get and then a put is the exact check then act
    // race the rest of this design exists to avoid.
    private final Map<String, Booking> byIdempotencyKey = new ConcurrentHashMap<>();

    public BookingService(HoldManager holds, PricingStrategy pricing, PaymentGateway payments) {
        this.holds = holds;
        this.pricing = pricing;
        this.payments = payments;
    }

    // Filter on the property, then on real availability for the dates. The
    // filters compose, so a new one never touches this method.
    public List<Property> search(List<Property> catalogue, Predicate<Property> filter,
                                 DateRange stay, int rooms) {
        return catalogue.stream()
                .filter(filter)
                .filter(property -> property.roomTypes().stream()
                        .anyMatch(type -> holds.isAvailable(type.id(), stay, rooms)))
                .toList();
    }

    public Optional<Hold> startCheckout(RoomType roomType, DateRange stay, Guest guest, int rooms) {
        return holds.hold(roomType.id(), stay, guest.id(), rooms);
    }

    // The risky path, all in one place. Claim the key, turn the hold into
    // booked nights, charge, then confirm. The key stays claimed only while an
    // attempt is in flight or once it has succeeded. Every failure releases
    // it, because the guest's next attempt with a different card is a real
    // attempt and not a duplicate.
    public BookingResult confirm(Hold hold, Guest guest, RoomType roomType, String idempotencyKey) {
        Money total = pricing.quote(roomType, hold.stay()).times(hold.rooms());
        Booking booking = new Booking(UUID.randomUUID().toString(), guest, roomType,
                hold.stay(), hold.rooms(), total);

        // Reserve the key before anything else, in one step. Two retries of
        // the same request cannot both get past this line, and the loser gets
        // the booking the winner is making.
        Booking first = byIdempotencyKey.putIfAbsent(idempotencyKey, booking);
        if (first != null) {
            return new BookingResult.AlreadyBooked(first);
        }

        if (!holds.confirm(hold.id(), guest.id())) {
            byIdempotencyKey.remove(idempotencyKey, booking);
            booking.moveTo(BookingStatus.CANCELLED);
            return new BookingResult.HoldExpired();
        }

        // Charging after the rooms are committed means a failed charge costs
        // a cancellation. Charging first would risk taking money for rooms
        // that went to somebody else. The gateway gets the booking id as its
        // own key, one per attempt, so a retried gateway call for this
        // booking is deduplicated and a fresh attempt after a decline is a
        // fresh key.
        if (!payments.charge(booking.id(), total)) {
            byIdempotencyKey.remove(idempotencyKey, booking);
            cancel(booking);
            return new BookingResult.PaymentDeclined(booking);
        }
        booking.moveTo(BookingStatus.CONFIRMED);
        return new BookingResult.Confirmed(booking);
    }

    // Legal from pending and from confirmed, and in both the nights are booked
    // and have to go back.
    public void cancel(Booking booking) {
        booking.moveTo(BookingStatus.CANCELLED);
        holds.releaseBooking(booking.roomType().id(), booking.stay(), booking.rooms());
    }

    public void checkIn(Booking booking) {
        booking.moveTo(BookingStatus.CHECKED_IN);
    }

    public void checkOut(Booking booking) {
        booking.moveTo(BookingStatus.COMPLETED);
    }
}

package com.androidinterview.bookingcom.service;

import com.androidinterview.bookingcom.model.Money;

// The whole of payments, for our purposes. Card handling is a different
// interview, so the seam is one call and the key is what makes a retry safe.
// A gateway that has already seen this key returns the original result rather
// than taking the money a second time. The service passes the booking id, one
// per attempt, so a declined attempt does not poison the next one.
@FunctionalInterface
public interface PaymentGateway {
    boolean charge(String idempotencyKey, Money amount);
}

package com.androidinterview.bookingcom.inventory

import com.androidinterview.bookingcom.model.DateRange
import java.time.Clock
import java.time.Duration
import java.util.UUID
import java.util.concurrent.locks.ReentrantLock
import kotlin.concurrent.withLock

// The centre of this problem. A hold moves room nights from available to held,
// a confirm moves them from held to booked, and a sweeper puts back anything
// nobody paid for. Search reads through here too, so a reader and a writer
// never see a night half updated.
//
// Be honest about the lock. This is one process. A real platform runs many
// servers against one database, so the same guarantee has to come from the
// database, as an update that increments held only where enough is left and
// then checks the row count.
class HoldManager(
    private val calendar: AvailabilityCalendar,
    private val clock: Clock,
    private val ttl: Duration,
) {
    private val holds = mutableMapOf<String, Hold>()
    private val lock = ReentrantLock()

    // The read search uses. It takes the same lock as the writes, which is
    // correct and slow. In production this read comes from a replica or a
    // cached count, and the hold re-checks under the real lock.
    fun isAvailable(roomTypeId: String, stay: DateRange, rooms: Int): Boolean = lock.withLock {
        expireStaleHolds()
        calendar.isAvailable(roomTypeId, stay, rooms)
    }

    // All nights or none. DateRange hands them back ascending, and that
    // canonical order is what stops two overlapping stays from each taking
    // half of what the other one needs.
    fun hold(roomTypeId: String, stay: DateRange, ownerId: String, rooms: Int): Hold? = lock.withLock {
        expireStaleHolds()
        val taken = mutableListOf<NightInventory>()
        for (night in stay.nights()) {
            val inventory = calendar.at(roomTypeId, night)
            if (inventory == null || inventory.available < rooms) {
                taken.forEach { it.releaseHold(rooms) }
                return@withLock null
            }
            inventory.hold(rooms)
            taken += inventory
        }
        val expiry = clock.instant().plus(ttl)
        Hold(UUID.randomUUID().toString(), roomTypeId, ownerId, stay, rooms, expiry)
            .also { holds[it.id] = it }
    }

    // Owner checked, and that one comparison is the point. Without it the
    // sweeper frees a hold a different guest acquired a moment earlier, and
    // that guest pays for a room somebody else is already taking.
    fun release(holdId: String, ownerId: String): Boolean = lock.withLock {
        val hold = holds[holdId]
        if (hold == null || hold.ownerId != ownerId) return@withLock false
        holds.remove(holdId)
        giveBack(hold)
        true
    }

    // A compare and set. It judges the expiry itself rather than trusting the
    // sweeper to have run, so the payment worker and the sweeper can never both
    // believe they won.
    fun confirm(holdId: String, ownerId: String): Boolean = lock.withLock {
        val hold = holds[holdId]
        if (hold == null || hold.ownerId != ownerId) return@withLock false
        holds.remove(holdId)
        if (hold.isExpiredAt(clock.instant())) {
            giveBack(hold)
            return@withLock false
        }
        hold.stay.nights().forEach { calendar.existing(hold.roomTypeId, it).commit(hold.rooms) }
        true
    }

    // A scheduled job in production. Driven inline here so a test can advance a
    // fixed Clock instead of sleeping.
    fun expireStaleHolds(): Int = lock.withLock {
        val now = clock.instant()
        val stale = holds.values.filter { it.isExpiredAt(now) }
        stale.forEach {
            holds.remove(it.id)
            giveBack(it)
        }
        stale.size
    }

    fun releaseBooking(roomTypeId: String, stay: DateRange, rooms: Int) = lock.withLock {
        stay.nights().forEach { calendar.existing(roomTypeId, it).releaseBooking(rooms) }
    }

    private fun giveBack(hold: Hold) =
        hold.stay.nights().forEach { calendar.existing(hold.roomTypeId, it).releaseHold(hold.rooms) }
}

package com.androidinterview.bookingcom.inventory

import com.androidinterview.bookingcom.model.DateRange
import java.time.Instant
import java.time.LocalDate

// One room type on one night. Three counters, not two, because a model that
// knows only available and booked cannot say somebody is part way through
// checkout and has not paid yet.
//
// Internal, and it does no locking. Everything that touches it runs inside the
// hold manager's critical section.
internal class NightInventory(private val total: Int) {
    private var held = 0
    private var booked = 0

    val available: Int get() = total - held - booked

    fun hold(rooms: Int) {
        held += rooms
    }

    fun releaseHold(rooms: Int) {
        held -= rooms
    }

    // Held becomes booked in one step, so no window opens in which another
    // guest takes the room this guest has just paid for.
    fun commit(rooms: Int) {
        held -= rooms
        booked += rooms
    }

    fun releaseBooking(rooms: Int) {
        booked -= rooms
    }
}

// A claim on some room nights that expires by itself. The owner is on the
// record because release has to check it.
data class Hold(
    val id: String,
    val roomTypeId: String,
    val ownerId: String,
    val stay: DateRange,
    val rooms: Int,
    val expiresAt: Instant,
) {
    fun isExpiredAt(now: Instant) = now >= expiresAt
}

// The class most candidates forget. Availability is a question about a room
// type on a single night, so the key is that pair and nothing smaller.
class AvailabilityCalendar {

    private val nights = mutableMapOf<Pair<String, LocalDate>, NightInventory>()

    fun openRooms(roomTypeId: String, range: DateRange, total: Int) {
        range.nights().forEach { nights[roomTypeId to it] = NightInventory(total) }
    }

    internal fun at(roomTypeId: String, night: LocalDate) = nights[roomTypeId to night]

    // For nights a hold has already proved exist. Failing loudly beats a silent
    // skip that leaves a counter wrong.
    internal fun existing(roomTypeId: String, night: LocalDate): NightInventory =
        checkNotNull(at(roomTypeId, night)) { "night $night was never opened for $roomTypeId" }

    // Every night or none. One sold out night in the middle makes the whole
    // stay unbookable. Internal, because the read has to happen under the hold
    // manager's lock like every other touch of a night.
    internal fun isAvailable(roomTypeId: String, range: DateRange, rooms: Int) =
        range.nights().all { (at(roomTypeId, it)?.available ?: 0) >= rooms }
}

package com.androidinterview.bookingcom.model

import java.time.LocalDate
import kotlin.math.roundToLong

// Minor units and a currency, never a double. Rounding a floating point price
// is how a total ends up a cent away from what the card was charged.
data class Money(val currency: String, val amount: Long) {
    operator fun plus(other: Money) = copy(amount = amount + other.amount)
    operator fun times(factor: Int) = copy(amount = amount * factor)

    // Basis points, so no caller can hand us a double. 1050 is ten and a half
    // percent.
    fun percentOf(basisPoints: Int) = copy(amount = (amount * basisPoints / 10000.0).roundToLong())
}

// A stay is a half open range. The check out date is not a night, so a guest
// leaving on the third and a guest arriving on the third never collide.
data class DateRange(val checkIn: LocalDate, val checkOut: LocalDate) {

    init {
        require(checkOut > checkIn) { "check out must be after check in" }
    }

    val nightCount: Int get() = (checkOut.toEpochDay() - checkIn.toEpochDay()).toInt()

    // Ascending, always. Multi night holds take nights in this order, and that
    // canonical order is what stops two overlapping stays from deadlocking.
    fun nights(): List<LocalDate> =
        generateSequence(checkIn) { it.plusDays(1) }.takeWhile { it < checkOut }.toList()
}

// Inventory hangs off a room type, not off a room. A guest books a double room
// and is given a room number at check in, which turns availability into a
// counter rather than a flag on a row.
data class RoomType(
    val id: String,
    val propertyId: String,
    val name: String,
    val maxOccupancy: Int,
    val baseRatePerNight: Money,
)

data class Property(
    val id: String,
    val name: String,
    val city: String,
    val rating: Double,
    val amenities: Set<String>,
    val roomTypes: List<RoomType>,
)

data class Guest(val id: String, val name: String, val email: String)

// The lifecycle, with the legal moves written down once. Every illegal move is
// visible in one place, and adding a status is one line.
enum class BookingStatus {
    PENDING,
    CONFIRMED,
    CHECKED_IN,
    COMPLETED,
    CANCELLED;

    fun canMoveTo(next: BookingStatus) = next in when (this) {
        PENDING -> setOf(CONFIRMED, CANCELLED)
        CONFIRMED -> setOf(CHECKED_IN, CANCELLED)
        CHECKED_IN -> setOf(COMPLETED)
        COMPLETED, CANCELLED -> emptySet()
    }
}

// One reservation. Pending from the moment the service claims the idempotency
// key for it until the card is charged, then confirmed.
class Booking(
    val id: String,
    val guest: Guest,
    val roomType: RoomType,
    val stay: DateRange,
    val rooms: Int,
    val total: Money,
) {
    // A private setter is the whole of encapsulation here. No getter and no
    // setter to write, and nothing outside can assign a status.
    var status: BookingStatus = BookingStatus.PENDING
        private set

    fun moveTo(next: BookingStatus) {
        check(status.canMoveTo(next)) { "cannot move from $status to $next" }
        status = next
    }
}

package com.androidinterview.bookingcom.pricing

import com.androidinterview.bookingcom.model.DateRange
import com.androidinterview.bookingcom.model.Money
import com.androidinterview.bookingcom.model.RoomType
import java.time.Month

// A single method strategy is a fun interface, so every call site can hand
// over a lambda instead of writing a class.
fun interface PricingStrategy {
    fun quote(roomType: RoomType, stay: DateRange): Money
}

// The rule everything else wraps. Rate times nights, nothing clever.
val baseRate = PricingStrategy { roomType, stay -> roomType.baseRatePerNight * stay.nightCount }

// The decorators are extension functions, which is what a decorator looks like
// in Kotlin. Wrapping composes, so seasonal and breakfast stack in either
// order. Sibling implementations would need one class per combination.
fun PricingStrategy.withSeasonalSurcharge(peakMonths: Set<Month>, basisPoints: Int) =
    PricingStrategy { roomType, stay ->
        val base = quote(roomType, stay)
        val peakNights = stay.nights().count { it.month in peakMonths }
        // The surcharge applies to the peak share of the stay, rounded down to
        // whole basis points, so a booking that straddles the end of a season
        // is not charged peak throughout.
        if (peakNights == 0) base else base + base.percentOf(basisPoints * peakNights / stay.nightCount)
    }

// Add ons are the textbook decorator case. They stack in any order and nothing
// downstream needs to know how many are on the booking.
fun PricingStrategy.withBreakfast(perGuestPerNight: Money, guests: Int) =
    PricingStrategy { roomType, stay ->
        quote(roomType, stay) + perGuestPerNight * (guests * stay.nightCount)
    }

package com.androidinterview.bookingcom.search

import com.androidinterview.bookingcom.model.Property

// A filter is a function. Kotlin needs no Specification interface here, and
// composing two of them is one infix function. Write the interface only when
// the filters also have to become a database query, which is the point where a
// plain function cannot follow you.
typealias PropertyFilter = (Property) -> Boolean

infix fun PropertyFilter.and(other: PropertyFilter): PropertyFilter {
    val first = this
    return { first(it) && other(it) }
}

fun inCity(city: String): PropertyFilter = { it.city.equals(city, ignoreCase = true) }

fun ratedAtLeast(rating: Double): PropertyFilter = { it.rating >= rating }

fun hasAmenity(amenity: String): PropertyFilter = { amenity in it.amenities }

fun sleeps(guests: Int): PropertyFilter = { property ->
    property.roomTypes.any { it.maxOccupancy >= guests }
}

package com.androidinterview.bookingcom.service

import com.androidinterview.bookingcom.inventory.Hold
import com.androidinterview.bookingcom.inventory.HoldManager
import com.androidinterview.bookingcom.model.Booking
import com.androidinterview.bookingcom.model.BookingStatus
import com.androidinterview.bookingcom.model.DateRange
import com.androidinterview.bookingcom.model.Guest
import com.androidinterview.bookingcom.model.Money
import com.androidinterview.bookingcom.model.Property
import com.androidinterview.bookingcom.model.RoomType
import com.androidinterview.bookingcom.pricing.PricingStrategy
import com.androidinterview.bookingcom.search.PropertyFilter
import java.util.UUID
import java.util.concurrent.ConcurrentHashMap

// The outcome as a sealed interface, so a caller has to handle every case and
// the compiler tells them when a new one appears. A nullable return would
// collapse three different failures into one. AlreadyBooked carries the
// booking the first request made, or is still making.
sealed interface BookingResult {
    data class Confirmed(val booking: Booking) : BookingResult
    data class AlreadyBooked(val booking: Booking) : BookingResult
    data class PaymentDeclined(val booking: Booking) : BookingResult
    data object HoldExpired : BookingResult
}

// The one class the outside world talks to. It sequences the steps and owns the
// bookkeeping. It owns no rules, because pricing is a strategy it was handed
// and inventory belongs to the hold manager. It never touches the calendar
// directly, every read and write of a night goes through the hold manager and
// its lock.
//
// Payments are a function type rather than an interface. Card handling is a
// different interview. The key the gateway gets is the booking id, one per
// attempt, so a retried gateway call is deduplicated and a declined attempt
// does not poison the next one.
class BookingService(
    private val holds: HoldManager,
    private val pricing: PricingStrategy,
    private val charge: (idempotencyKey: String, amount: Money) -> Boolean,
) {
    // A concurrent map, because the reservation of a key has to be one atomic
    // step. A plain map with a get and then a put is the exact check then act
    // race the rest of this design exists to avoid.
    private val byIdempotencyKey = ConcurrentHashMap<String, Booking>()

    fun search(catalogue: List<Property>, filter: PropertyFilter, stay: DateRange, rooms: Int) =
        catalogue.filter(filter).filter { property ->
            property.roomTypes.any { holds.isAvailable(it.id, stay, rooms) }
        }

    fun startCheckout(roomType: RoomType, stay: DateRange, guest: Guest, rooms: Int): Hold? =
        holds.hold(roomType.id, stay, guest.id, rooms)

    // The risky path, all in one place. Claim the key, turn the hold into booked
    // nights, charge, then confirm. The key stays claimed only while an attempt
    // is in flight or once it has succeeded. Every failure releases it, because
    // the guest's next attempt with a different card is a real attempt and not
    // a duplicate.
    fun confirm(hold: Hold, guest: Guest, roomType: RoomType, idempotencyKey: String): BookingResult {
        val total = pricing.quote(roomType, hold.stay) * hold.rooms
        val booking = Booking(UUID.randomUUID().toString(), guest, roomType, hold.stay, hold.rooms, total)

        // Reserve the key before anything else, in one step. Two retries of the
        // same request cannot both get past this line, and the loser gets the
        // booking the winner is making.
        byIdempotencyKey.putIfAbsent(idempotencyKey, booking)?.let { return BookingResult.AlreadyBooked(it) }

        if (!holds.confirm(hold.id, guest.id)) {
            byIdempotencyKey.remove(idempotencyKey, booking)
            booking.moveTo(BookingStatus.CANCELLED)
            return BookingResult.HoldExpired
        }

        // Charging after the rooms are committed means a failed charge costs a
        // cancellation. Charging first would risk taking money for rooms that
        // went to somebody else.
        if (!charge(booking.id, total)) {
            byIdempotencyKey.remove(idempotencyKey, booking)
            cancel(booking)
            return BookingResult.PaymentDeclined(booking)
        }
        booking.moveTo(BookingStatus.CONFIRMED)
        return BookingResult.Confirmed(booking)
    }

    // Legal from pending and from confirmed, and in both the nights are booked
    // and have to go back.
    fun cancel(booking: Booking) {
        booking.moveTo(BookingStatus.CANCELLED)
        holds.releaseBooking(booking.roomType.id, booking.stay, booking.rooms)
    }

    fun checkIn(booking: Booking) = booking.moveTo(BookingStatus.CHECKED_IN)

    fun checkOut(booking: Booking) = booking.moveTo(BookingStatus.COMPLETED)
}