LOW LEVEL DESIGN · MACHINE CODING · MEDIUM · 41 OF 42

Design an Airline Reservation System: LLD in Java

The airline reservation machine coding question, solved end to end: flight schedules versus dated flight instances, seat maps with business and economy cabins, search by route and date, seat holds that expire on a fake clock, PNR generation, demand-based fare strategies, overbooking as a policy, refund rules per fare type, check-in with boarding passes, one lock per departure, and a full Java 17 solution.

Patterns usedStrategyObserver

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 23

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 508 lines, with a small main() demo. Save it as AirlineBooking.java, then run javac AirlineBooking.java && java AirlineBooking.

import java.time.DayOfWeek;
import java.time.Duration;
import java.time.Instant;
import java.time.LocalDate;
import java.time.LocalTime;
import java.time.ZoneId;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.EnumMap;
import java.util.EnumSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Supplier;

/** An airline reservation system: schedules, dated flights, expiring seat holds, PNRs, fares and check-in. */
public class AirlineBooking {

    // ---------- the static model: aircraft and schedules ----------
    enum Cabin { BUSINESS, ECONOMY }

    enum FareType { SAVER, FLEX }

    record Seat(String code, Cabin cabin) {
        int row() { return Integer.parseInt(code.substring(0, code.length() - 1)); }
    }

    record SeatMap(String model, List<Seat> seats) {
        int count(Cabin c) { return (int) seats.stream().filter(s -> s.cabin() == c).count(); }

        Seat seat(String code) {
            for (Seat s : seats) if (s.code().equals(code)) return s;
            throw new IllegalArgumentException("no seat " + code + " on a " + model);
        }

        /** Business boards first, then the back half of economy, then the front half. */
        int boardingGroup(Seat s) {
            if (s.cabin() == Cabin.BUSINESS) return 1;
            int first = Integer.MAX_VALUE, last = 0;
            for (Seat x : seats) {
                if (x.cabin() != Cabin.ECONOMY) continue;
                first = Math.min(first, x.row());
                last = Math.max(last, x.row());
            }
            return s.row() > (first + last) / 2 ? 2 : 3;
        }
    }

    /** A schedule line, such as AR101 BLR to DEL at 09:00 every day. One Flight, many FlightInstances. */
    record Flight(String number, String from, String to, LocalTime departs, ZoneId zone, Set<DayOfWeek> days,
                  SeatMap aircraft, Map<Cabin, Long> baseFareCents) {
        boolean operatesOn(LocalDate d) { return days.contains(d.getDayOfWeek()); }
    }

    // ---------- the changing part: one flight on one date ----------
    record Hold(String id, String instanceId, Cabin cabin, FareType fare, List<String> travellers,
                List<String> seats, long totalCents, Instant expiresAt) {}

    static final class Traveller {
        final String name;
        private String seat;              // chosen at booking, or given at check-in
        private boolean checkedIn;

        Traveller(String name, String seat) {
            this.name = name;
            this.seat = seat;
        }
    }

    enum BookingStatus { CONFIRMED, CANCELLED }

    static final class Booking {
        final String pnr;
        final FlightInstance flight;
        final Cabin cabin;
        final FareType fare;
        final List<Traveller> travellers;
        final long totalCents;
        private BookingStatus status = BookingStatus.CONFIRMED;   // guarded by the flight instance

        Booking(String pnr, FlightInstance flight, Cabin cabin, FareType fare, List<Traveller> travellers,
                long totalCents) {
            this.pnr = pnr;
            this.flight = flight;
            this.cabin = cabin;
            this.fare = fare;
            this.travellers = travellers;
            this.totalCents = totalCents;
        }
    }

    record BoardingPass(String pnr, String name, String flight, LocalDate date, String seat, int group,
                        int seq) {
        @Override
        public String toString() {
            return flight + " " + date + " " + name + " seat " + seat + " group " + group + " seq " + seq
                    + " (" + pnr + ")";
        }
    }

    /** The unit of locking: everything that changes for one departure is guarded by this object. */
    static final class FlightInstance {
        final String id;
        final Flight flight;
        final LocalDate date;
        final Instant departure;
        private final Map<String, String> seatOwner = new HashMap<>();    // seat code to hold id or PNR
        private final Map<String, Hold> holds = new HashMap<>();
        private final Map<Cabin, Integer> sold = new EnumMap<>(Cabin.class);
        private final List<String> deniedBoarding = new ArrayList<>();
        private int boardingSeq;

        FlightInstance(Flight flight, LocalDate date) {
            this.id = flight.number() + "-" + date;
            this.flight = flight;
            this.date = date;
            this.departure = date.atTime(flight.departs()).atZone(flight.zone()).toInstant();
            for (Cabin c : Cabin.values()) sold.put(c, 0);
        }

        /** Call with the lock held. Expired holds are dropped lazily, so no timer is needed. */
        void dropExpired(Instant now) {
            for (Iterator<Hold> it = holds.values().iterator(); it.hasNext(); ) {
                Hold h = it.next();
                if (now.isBefore(h.expiresAt())) continue;
                it.remove();
                for (String s : h.seats()) seatOwner.remove(s);
            }
        }

        /** Sold tickets plus travellers in live holds. */
        int taken(Cabin c) {
            int n = sold.get(c);
            for (Hold h : holds.values()) if (h.cabin() == c) n += h.travellers().size();
            return n;
        }
    }

    // ---------- policies (Strategy) ----------
    record PriceQuery(Flight flight, Cabin cabin, FareType fare, int loadPercent, long daysToGo) {}

    interface PricingStrategy { long fareCents(PriceQuery q); }

    /** Fares rise as the cabin fills and as departure gets close; FLEX costs more than SAVER. */
    static final class DemandPricing implements PricingStrategy {
        @Override
        public long fareCents(PriceQuery q) {
            long fare = q.flight().baseFareCents().get(q.cabin());
            int demand = q.loadPercent() < 50 ? 100 : q.loadPercent() < 80 ? 130 : 170;
            int lastMinute = q.daysToGo() < 7 ? 125 : 100;
            int flex = q.fare() == FareType.FLEX ? 130 : 100;
            return fare * demand / 100 * lastMinute / 100 * flex / 100;
        }
    }

    interface OverbookingPolicy { int sellLimit(Cabin cabin, int seats); }

    static final class NoOverbooking implements OverbookingPolicy {
        @Override public int sellLimit(Cabin cabin, int seats) { return seats; }
    }

    record PercentOverbooking(Cabin only, int percent) implements OverbookingPolicy {
        @Override public int sellLimit(Cabin cabin, int seats) {
            return cabin == only ? seats + seats * percent / 100 : seats;
        }
    }

    interface RefundPolicy { long refundCents(Booking b, Instant now); }

    /** Saver: the total minus a fee per traveller, if cancelled 72 hours or more before departure. */
    record SaverRefund(long feePerTravellerCents) implements RefundPolicy {
        @Override
        public long refundCents(Booking b, Instant now) {
            if (Duration.between(now, b.flight.departure).toHours() < 72) return 0;
            return Math.max(0, b.totalCents - feePerTravellerCents * b.travellers.size());
        }
    }

    /** Flex: everything back until the plane leaves; a no-show gets nothing. */
    static final class FlexRefund implements RefundPolicy {
        @Override
        public long refundCents(Booking b, Instant now) {
            return now.isBefore(b.flight.departure) ? b.totalCents : 0;
        }
    }

    // ---------- PNR generation ----------
    /** Six symbols from 32 (no I, O, 0, 1). An odd multiplier mod 2^30 is one to one: codes never repeat. */
    static final class PnrGenerator {
        private static final String ALPHABET = "ABCDEFGHJKLMNPQRSTUVWXYZ23456789";
        private final AtomicLong seq = new AtomicLong();

        String next() {
            long x = (seq.incrementAndGet() * 0x2545F491L + 0x9E3779B1L) & ((1L << 30) - 1);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; i++, x >>>= 5) sb.append(ALPHABET.charAt((int) (x & 31)));
            return sb.toString();
        }
    }

    // ---------- the service ----------
    record Offer(String instanceId, String flight, LocalTime departs, Cabin cabin, int canSell,
                 long saverCents, long flexCents) {
        @Override
        public String toString() {
            return flight + " " + departs + " " + cabin + ": can sell " + canSell
                    + ", saver " + money(saverCents) + ", flex " + money(flexCents);
        }
    }

    private final Map<String, Flight> schedule = new ConcurrentHashMap<>();
    private final Map<String, FlightInstance> instances = new ConcurrentHashMap<>();
    private final Map<String, Hold> holds = new ConcurrentHashMap<>();
    private final Map<String, Booking> bookings = new ConcurrentHashMap<>();
    private final PnrGenerator pnrs = new PnrGenerator();
    private final AtomicLong holdIds = new AtomicLong();
    private final PricingStrategy pricing;
    private final OverbookingPolicy overbooking;
    private final Map<FareType, RefundPolicy> refundRules;
    private final Supplier<Instant> clock;
    private final Duration holdFor;

    AirlineBooking(PricingStrategy pricing, OverbookingPolicy overbooking,
                   Map<FareType, RefundPolicy> refundRules, Supplier<Instant> clock, Duration holdFor) {
        this.pricing = pricing;
        this.overbooking = overbooking;
        this.refundRules = refundRules;
        this.clock = clock;
        this.holdFor = holdFor;
    }

    void addFlight(Flight f) { schedule.put(f.number(), f); }

    /** Search is a hint: the numbers may change a moment later, so hold() checks again under the lock. */
    List<Offer> search(String from, String to, LocalDate date, Cabin cabin, int travellers) {
        Instant now = clock.get();
        List<Offer> out = new ArrayList<>();
        for (Flight f : schedule.values()) {
            if (!f.from().equals(from) || !f.to().equals(to) || !f.operatesOn(date)) continue;
            String key = f.number() + "-" + date;
            FlightInstance fi = instances.computeIfAbsent(key, k -> new FlightInstance(f, date));
            synchronized (fi) {
                fi.dropExpired(now);
                int left = limit(fi, cabin) - fi.taken(cabin);
                if (left < travellers) continue;
                out.add(new Offer(fi.id, f.number(), f.departs(), cabin, left,
                        price(fi, cabin, FareType.SAVER, now), price(fi, cabin, FareType.FLEX, now)));
            }
        }
        out.sort(Comparator.comparing(Offer::departs));
        return out;
    }

    /** Hold seats while the traveller pays. Capacity, seats and the claim all happen under one lock. */
    Hold hold(String instanceId, Cabin cabin, FareType fare, List<String> travellers, List<String> seats) {
        FlightInstance fi = find(instances, instanceId, "flight");
        if (seats.size() > travellers.size() || new HashSet<>(seats).size() != seats.size()) {
            throw new IllegalArgumentException("one distinct seat per traveller at most");
        }
        Instant now = clock.get();
        synchronized (fi) {
            fi.dropExpired(now);
            if (!now.isBefore(fi.departure)) throw new IllegalStateException(fi.id + " has left");
            if (fi.taken(cabin) + travellers.size() > limit(fi, cabin)) {
                throw new IllegalStateException(cabin + " sold out on " + fi.id);
            }
            for (String code : seats) {
                if (fi.flight.aircraft().seat(code).cabin() != cabin) {
                    throw new IllegalArgumentException(code + " is not in " + cabin);
                }
                if (fi.seatOwner.containsKey(code)) {
                    throw new IllegalStateException("seat " + code + " is taken");
                }
            }
            long total = price(fi, cabin, fare, now) * travellers.size();
            Hold h = new Hold("H" + holdIds.incrementAndGet(), fi.id, cabin, fare, List.copyOf(travellers),
                    List.copyOf(seats), total, now.plus(holdFor));
            for (String code : seats) fi.seatOwner.put(code, h.id());
            fi.holds.put(h.id(), h);
            holds.put(h.id(), h);
            return h;
        }
    }

    /** Payment went through: the hold becomes a booking with a PNR, unless it ran out first. */
    Booking confirm(String holdId) {
        Hold h = holds.remove(holdId);                 // remove first: a hold is confirmed at most once
        if (h == null) throw new IllegalArgumentException("unknown or used hold " + holdId);
        FlightInstance fi = instances.get(h.instanceId());
        synchronized (fi) {
            fi.dropExpired(clock.get());
            if (fi.holds.remove(h.id()) == null) {
                throw new IllegalStateException(holdId + " expired, please search again");
            }
            String pnr = pnrs.next();
            List<Traveller> ts = new ArrayList<>();
            for (int i = 0; i < h.travellers().size(); i++) {
                String seat = i < h.seats().size() ? h.seats().get(i) : null;
                if (seat != null) fi.seatOwner.put(seat, pnr);
                ts.add(new Traveller(h.travellers().get(i), seat));
            }
            fi.sold.merge(h.cabin(), h.travellers().size(), Integer::sum);
            Booking b = new Booking(pnr, fi, h.cabin(), h.fare(), List.copyOf(ts), h.totalCents());
            bookings.put(pnr, b);
            return b;
        }
    }

    /** Returns the refund in paise. Frees the seats and the sold count exactly once. */
    long cancel(String pnr) {
        Booking b = find(bookings, pnr, "PNR");
        FlightInstance fi = b.flight;
        synchronized (fi) {
            if (b.status != BookingStatus.CONFIRMED) throw new IllegalStateException(pnr + " was cancelled");
            long refund = refundRules.get(b.fare).refundCents(b, clock.get());
            fi.seatOwner.values().removeIf(pnr::equals);
            fi.sold.merge(b.cabin, -b.travellers.size(), Integer::sum);
            b.status = BookingStatus.CANCELLED;
            return refund;
        }
    }

    /** Opens 24 hours before departure, closes 45 minutes before. Seats without a choice are given here. */
    BoardingPass checkIn(String pnr, String name) {
        Booking b = find(bookings, pnr, "PNR");
        FlightInstance fi = b.flight;
        Instant now = clock.get();
        if (now.isBefore(fi.departure.minus(Duration.ofHours(24)))) {
            throw new IllegalStateException("check-in opens 24 hours before departure");
        }
        if (now.isAfter(fi.departure.minus(Duration.ofMinutes(45)))) {
            throw new IllegalStateException("check-in closed");
        }
        synchronized (fi) {
            if (b.status != BookingStatus.CONFIRMED) throw new IllegalStateException(pnr + " is cancelled");
            Traveller t = b.travellers.stream().filter(x -> x.name.equals(name)).findFirst()
                    .orElseThrow(() -> new IllegalArgumentException(name + " is not on " + pnr));
            if (t.checkedIn) throw new IllegalStateException(name + " is already checked in");
            if (t.seat == null) {
                for (Seat s : fi.flight.aircraft().seats()) {
                    if (s.cabin() == b.cabin && !fi.seatOwner.containsKey(s.code())) {
                        t.seat = s.code();
                        fi.seatOwner.put(s.code(), pnr);
                        break;
                    }
                }
                if (t.seat == null) {                  // overbooked and everyone showed up
                    fi.deniedBoarding.add(name);
                    throw new IllegalStateException(name + ": " + b.cabin + " full, rebook + compensation");
                }
            }
            t.checkedIn = true;
            int group = fi.flight.aircraft().boardingGroup(fi.flight.aircraft().seat(t.seat));
            return new BoardingPass(pnr, name, fi.flight.number(), fi.date, t.seat, group, ++fi.boardingSeq);
        }
    }

    List<String> deniedBoarding(String instanceId) {
        FlightInstance fi = find(instances, instanceId, "flight");
        synchronized (fi) { return List.copyOf(fi.deniedBoarding); }
    }

    /** Call with the instance lock held: the fare depends on how full the cabin is right now. */
    private long price(FlightInstance fi, Cabin cabin, FareType fare, Instant now) {
        int load = fi.taken(cabin) * 100 / fi.flight.aircraft().count(cabin);
        long days = Duration.between(now, fi.departure).toDays();
        return pricing.fareCents(new PriceQuery(fi.flight, cabin, fare, load, days));
    }

    private int limit(FlightInstance fi, Cabin cabin) {
        return overbooking.sellLimit(cabin, fi.flight.aircraft().count(cabin));
    }

    private static <T> T find(Map<String, T> map, String id, String what) {
        T t = map.get(id);
        if (t == null) throw new IllegalArgumentException("no " + what + " " + id);
        return t;
    }

    static String money(long cents) { return String.format("%,d.%02d", cents / 100, cents % 100); }

    // ---------- demo ----------
    static Booking book(AirlineBooking app, String id, Cabin c, FareType f, List<String> who,
                        List<String> seats) {
        Booking b = app.confirm(app.hold(id, c, f, who, seats).id());
        System.out.println("  " + b.pnr + " " + f + " " + who + " paid " + money(b.totalCents));
        return b;
    }

    public static void main(String[] args) throws InterruptedException {
        // 10:00 in India on 1 Dec; the flight leaves at 09:00 on 20 Dec
        AtomicReference<Instant> now = new AtomicReference<>(Instant.parse("2026-12-01T04:30:00Z"));
        List<Seat> seats = new ArrayList<>();
        seats.add(new Seat("1A", Cabin.BUSINESS));
        seats.add(new Seat("1C", Cabin.BUSINESS));
        for (int row = 2; row <= 3; row++) {
            for (String col : List.of("A", "B", "C")) seats.add(new Seat(row + col, Cabin.ECONOMY));
        }
        SeatMap jet = new SeatMap("mini jet", List.copyOf(seats));
        ZoneId ist = ZoneId.of("Asia/Kolkata");
        Map<Cabin, Long> fares = Map.of(Cabin.ECONOMY, 5_000_00L, Cabin.BUSINESS, 15_000_00L);
        Map<FareType, RefundPolicy> rules = new EnumMap<>(FareType.class);
        rules.put(FareType.SAVER, new SaverRefund(2_500_00));
        rules.put(FareType.FLEX, new FlexRefund());
        OverbookingPolicy overbook = new PercentOverbooking(Cabin.ECONOMY, 20);   // or new NoOverbooking()
        AirlineBooking app = new AirlineBooking(new DemandPricing(), overbook, rules, now::get,
                Duration.ofMinutes(15));
        Set<DayOfWeek> daily = EnumSet.allOf(DayOfWeek.class);
        app.addFlight(new Flight("AR101", "BLR", "DEL", LocalTime.of(9, 0), ist, daily, jet, fares));
        app.addFlight(new Flight("AR205", "BLR", "DEL", LocalTime.of(18, 30), ist,
                EnumSet.of(DayOfWeek.MONDAY, DayOfWeek.WEDNESDAY, DayOfWeek.FRIDAY), jet, fares));
        app.addFlight(new Flight("AR330", "BLR", "BOM", LocalTime.of(7, 15), ist, daily, jet, fares));

        LocalDate day = LocalDate.of(2026, 12, 20);                         // a Sunday: AR205 does not fly
        System.out.println("search BLR-DEL " + day + ": " + app.search("BLR", "DEL", day, Cabin.ECONOMY, 2));
        String id = "AR101-2026-12-20";

        Hold slow = app.hold(id, Cabin.ECONOMY, FareType.SAVER, List.of("traveller-a", "traveller-b"),
                List.of("2A", "2B"));
        System.out.println("held " + slow.id() + " 2A 2B for " + money(slow.totalCents()) + " until "
                + slow.expiresAt());
        now.set(now.get().plus(Duration.ofMinutes(16)));                    // the traveller wandered off
        try {
            app.confirm(slow.id());
        } catch (IllegalStateException e) {
            System.out.println("confirm: " + e.getMessage());
        }

        // Eight travellers want seat 1A at the same moment: exactly one hold wins.
        AtomicInteger won = new AtomicInteger(), lost = new AtomicInteger();
        AtomicReference<Hold> winner = new AtomicReference<>();
        ExecutorService pool = Executors.newFixedThreadPool(8);
        CountDownLatch go = new CountDownLatch(1);
        for (int i = 0; i < 8; i++) {
            List<String> who = List.of("racer-" + i);
            pool.submit(() -> {
                try {
                    go.await();
                    winner.set(app.hold(id, Cabin.BUSINESS, FareType.FLEX, who, List.of("1A")));
                    won.incrementAndGet();
                } catch (IllegalStateException e) {
                    lost.incrementAndGet();
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
        go.countDown();
        pool.shutdown();
        pool.awaitTermination(5, TimeUnit.SECONDS);
        System.out.println("race for seat 1A: " + won.get() + " held, " + lost.get() + " refused");
        if (won.get() != 1) throw new AssertionError("seat sold twice");
        Booking flexBiz = app.confirm(winner.get().id());
        System.out.println("  " + flexBiz.pnr + " FLEX business 1A paid " + money(flexBiz.totalCents));

        System.out.println("economy fills up (6 seats, sell limit 7):");
        Booking family = book(app, id, Cabin.ECONOMY, FareType.FLEX, List.of("traveller-a", "traveller-b"),
                List.of("2A", "2B"));
        Booking group = book(app, id, Cabin.ECONOMY, FareType.SAVER,
                List.of("traveller-c", "traveller-d", "traveller-e"), List.of());
        Booking f = book(app, id, Cabin.ECONOMY, FareType.SAVER, List.of("traveller-f"), List.of());
        Booking g = book(app, id, Cabin.ECONOMY, FareType.SAVER, List.of("traveller-g"), List.of());
        try {
            book(app, id, Cabin.ECONOMY, FareType.SAVER, List.of("traveller-h"), List.of());
        } catch (IllegalStateException e) {
            System.out.println("  traveller-h: " + e.getMessage());
        }
        Booking saverBiz = book(app, id, Cabin.BUSINESS, FareType.SAVER, List.of("traveller-z"),
                List.of("1C"));

        now.set(Instant.parse("2026-12-15T04:30:00Z"));                      // 119 hours before departure
        long saverBack = app.cancel(saverBiz.pnr);
        System.out.println("cancel " + saverBiz.pnr + " SAVER 119h before: refund " + money(saverBack)
                + " of " + money(saverBiz.totalCents));
        now.set(Instant.parse("2026-12-18T04:30:00Z"));                      // 47 hours before departure
        long flexBack = app.cancel(flexBiz.pnr);
        System.out.println("cancel " + flexBiz.pnr + " FLEX 47h before: refund " + money(flexBack)
                + " of " + money(flexBiz.totalCents));
        try {
            app.checkIn(family.pnr, "traveller-a");
        } catch (IllegalStateException e) {
            System.out.println("check-in: " + e.getMessage());
        }

        now.set(Instant.parse("2026-12-19T10:00:00Z"));                      // 17.5 hours before departure
        for (Booking b : List.of(family, group, f, g)) {
            for (Traveller t : b.travellers) {
                try {
                    System.out.println("  " + app.checkIn(b.pnr, t.name));
                } catch (IllegalStateException e) {
                    System.out.println("  denied: " + e.getMessage());
                }
            }
        }
        System.out.println("denied boarding on " + id + ": " + app.deniedBoarding(id));
    }
}

Notes

Requirements

Fix the scope. Flights run on a weekly schedule, each with an aircraft whose seat map has business and economy cabins. Travellers search by origin, destination, date and cabin, hold seats for fifteen minutes while paying, and get a six character booking reference, the PNR. Fares depend on the fare type and on demand. Bookings can be cancelled under refund rules, travellers check in for a boarding pass, and the airline may overbook within a limit.

Ask the questions that change the code. Must every traveller pick a seat? No: those who skip get one at check-in, which is what makes overbooking possible. When is the price fixed? At hold time. When does check-in open and close? Twenty-four hours before departure until forty-five minutes before. How much overbooking? Whatever the policy says, for example twenty percent extra in economy. And for now, one flight leg per booking.

Requirements
  • flights run on a weekly schedule
  • aircraft seat map: business,
  • economy
  • search by from, to, date, cabin
  • hold seats while paying: 15 min
  • confirm: a 6 char PNR
  • fare by fare type and demand
  • cancel with refund rules
  • check in, get a boarding pass
  • overbooking: a configurable limit
  • out of scope: crew, baggage
Clarify first
  • must every traveller pick a seat?
  • no: free seat at check-in
  • price fixed when?
  • quoted at hold time
  • check-in window?
  • 24h to 45 min before departure
  • overbooking how much?
  • a policy, e.g. 20% of economy
  • one leg or many?
  • one leg; multi-leg is an
  • extension

Entities

The most important split in this design: a flight is not a departure. Flight A R one zero one, Bangalore to Delhi at nine every day, is a schedule. The plane leaving on the twentieth of December is a flight instance. Seats, holds, bookings and sold counts belong to the instance, because seat two A can be free on Sunday and sold on Monday. The schedule and the seat map never change, so they are shared by every instance.

Class diagram

Turn them into types. Cabin and fare type are enums. A seat, a seat map and a flight schedule are records, because they never change. The flight instance is the one class with changing state: which seat is owned by which hold or booking, the active holds, and how many tickets are sold per cabin. Departure time is computed in the origin airport's time zone. Money is a long number of paise.

Types
enum Cabin { BUSINESS, ECONOMY }
enum FareType { SAVER, FLEX }
record Seat(String code, Cabin cabin)
record Flight(number, from, to, departs,
    zone, Set<DayOfWeek> days, SeatMap,
    Map<Cabin, Long> baseFareCents)
class FlightInstance {
  Map<String,String> seatOwner;
  Map<String,Hold> holds;
  Map<Cabin,Integer> sold;
}

Flow: search

Search walks the schedule. A flight matches if the route is right and it operates on that day of the week, so the Monday, Wednesday, Friday flight is skipped on a Sunday. The dated instance is created on first use with compute if absent, so two searches never create two copies. For each match we count what is left to sell and quote both a saver and a flex fare. Like any search, it is only a hint; hold checks again.

search(from, to, date, cabin, n)
for (Flight f : schedule)
  if route matches and
     f.days contains date.dayOfWeek
    fi = instances.computeIfAbsent(..)
    synchronized (fi) {
      left = sellLimit - sold - held
      if (left >= n) offer(saver, flex)
    }
sorted by departure time

Holds

Paying takes a few minutes, so seats are held first. A hold remembers its seats, its quoted total and an expiry fifteen minutes away. There is no timer per hold. Instead, every operation on a flight instance first drops the holds whose time has passed and frees their seats, under the same lock. A traveller who wanders off simply stops counting the moment anyone looks. The clock is injected, so the demo moves time without sleeping.

dropExpired(now)
// called under the instance lock
for (Hold h : holds.values())
  if (!now.isBefore(h.expiresAt)) {
    remove h
    free every seat h owned
  }

taken(cabin) = sold + travellers
  in the holds that are left

Flow: hold

Walk the hold. Lock the flight instance and drop expired holds. Check capacity against the overbooking policy's sell limit, not the physical seats. Then check every requested seat: it must exist, be in the right cabin, and have no owner. Only if every check passes do we price the hold and mark the seats as owned by it. All or nothing, so a family of two never ends up with one seat held and one lost.

hold(flight, cabin, pax, seats)
synchronized (fi) {
  fi.dropExpired(now);
  if (taken + pax > sellLimit)
    throw: sold out
  for each seat: in cabin? owned?
    throw: seat 1A is taken
  total = price(..) * pax
  for each seat: owner = holdId
  fi.holds.put(hold)
}

Concurrency

Now the race. Eight travellers tap seat one A on the same departure at the same moment. If checking and claiming were separate steps, two threads could both see the seat free and both claim it. So both happen inside one lock on the flight instance. The first thread claims the seat; the others wait a moment, see the owner and fail with seat taken. The lock is per departure, so tomorrow's flight and every other route never wait.

No double-booked seat
  • bad: is 1A free? then claim
  • two threads both see free
  • good: check and claim inside
  • synchronized (flightInstance)
  • the second thread waits, then
  • sees the owner and fails
  • one lock per departure:
  • other flights never wait

Flow: confirm

Once payment succeeds, confirm. Removing the hold from the map first means a hold can be confirmed only once, even if the payment callback arrives twice. Under the instance lock, drop expired holds; if ours is gone, the traveller took too long and must search again. Otherwise generate a PNR, hand the seats from the hold to the booking, and add the travellers to the sold count for their cabin.

confirm(holdId)
Hold h = holds.remove(holdId);
if (h == null) throw: unknown or used
synchronized (fi) {
  fi.dropExpired(now);
  if (fi.holds.remove(id) == null)
    throw: expired, search again
  pnr = pnrs.next();
  seat owners: holdId to pnr
  sold[cabin] += pax
}

PNR generation

A PNR is six characters a traveller reads over the phone, so the alphabet drops I, O, zero and one, which leaves thirty-two symbols, exactly five bits each. Six of them give thirty bits. We take an atomic counter and scramble it: multiply by an odd number and add a constant, modulo two to the thirtieth. With an odd multiplier that mapping is one to one, so codes never repeat, yet consecutive bookings look unrelated. No retry loop on collisions is needed.

PnrGenerator.next()
ALPHABET: 32 symbols, no I O 0 1
6 symbols x 5 bits = 30 bits

long x = seq.incrementAndGet()
  * 0x2545F491L + 0x9E3779B1L;
x &= (1L << 30) - 1;
// odd multiplier mod 2^30:
// a one to one mapping
take 5 bits at a time
  into ALPHABET.charAt(..)

Strategy: pricing

Pricing is a strategy, because revenue teams change it constantly. Ours reads a small query: the flight, cabin, fare type, how full the cabin is, and days to departure. Under half full the economy fare is the base five thousand rupees, up to eighty percent full it is thirty percent higher, and beyond that seventy percent higher. Inside a week it rises again, and flex costs thirty percent more than saver. The fare is computed under the instance lock, so the load it reads is exact.

DemandPricing
interface PricingStrategy {
  long fareCents(PriceQuery q);
}
demand: load under 50% x1.0,
        under 80% x1.3, else x1.7
last minute (under 7 days) x1.25
FLEX x1.3

economy base 5,000: load 33%: 5,000
  load 83%: 8,500, FLEX empty: 6,500

Overbooking

Some travellers never show up, so airlines sell a few more seats than the plane has. That is a business decision, so it is a policy: an interface that returns the sell limit for a cabin. No overbooking returns the seat count. Percent overbooking adds, say, twenty percent to economy, so six seats can sell seven tickets. Selling more is easy; the bill comes at check-in, when the last traveller without a seat may find none left.

OverbookingPolicy
interface OverbookingPolicy {
  int sellLimit(Cabin c, int seats);
}
NoOverbooking: seats
PercentOverbooking(ECONOMY, 20):
  6 + 6 * 20 / 100 = 7

seat chosen at booking: owned now
no seat chosen: assigned at
  check-in, if one is left

Strategy: refunds

Cancellation depends on the fare type, so each type maps to a refund policy. Saver refunds the total minus a fee of two thousand five hundred per traveller if you cancel seventy-two hours or more before departure, and nothing after that. Flex refunds everything until the plane leaves. Cancel runs under the instance lock: it computes the refund, frees the booking's seats, lowers the sold count and marks the booking cancelled, so it can only happen once.

RefundPolicy
interface RefundPolicy {
  long refundCents(Booking b,
                   Instant now);
}
Saver: 72h or more before departure:
  total - 2,500 per traveller
  later: nothing
Flex: everything until departure

cancel releases seats and
  sold count under the lock

Flow: check-in

Check-in opens twenty-four hours before departure and closes forty-five minutes before. Under the instance lock, a traveller who chose a seat keeps it; anyone else gets the first free seat in their cabin. The boarding pass carries the seat, a boarding group, business first and then the back rows of economy, and a sequence number from a counter on the instance. Checking in twice is rejected.

checkIn(pnr, name)
window: 24h to 45 min before
synchronized (fi) {
  if (t.seat == null)
    t.seat = first seat in cabin
             with no owner
  if still null: denied boarding
  t.checkedIn = true
  return new BoardingPass(..,
      group, ++boardingSeq)
}

Denied boarding

Here is overbooking coming due. Seven economy tickets were sold for six seats, and everyone shows up. The first six travellers get seats. The seventh finds none free, so check-in records them on the denied boarding list and the agent offers the next flight plus compensation. Notice that travellers who chose a seat at booking were never at risk, because their seat was owned from the start.

Concurrency

Check every shared field. Everything that changes for one departure, the seat owners, holds, sold counts, booking status and check-in state, is guarded by that instance's lock. Instances are created once with compute if absent. A hold is removed from the map before confirming, so it is used once. The PNR counter is atomic, and schedules and seat maps are immutable records. Each call takes at most one lock, so deadlock cannot happen.

Thread safety checklist
  • per departure, one lock:
  • seat owners, holds, sold,
  • booking status, check-in
  • instances: computeIfAbsent
  • holds by id: remove() once
  • PNR counter: AtomicLong
  • schedules, seat maps: records
  • one lock at a time: no deadlock
  • pricing reads load under lock

At scale

With many servers, the lock moves into the database. Each seat of each departure is a row with an owner and a hold expiry, and claiming it is a conditional update that only succeeds if the owner is empty or the hold has expired. The sold count is a conditional update too: add the travellers only if the result stays within the sell limit. Search, which is most of the traffic, reads from caches and replicas, because hold re-checks anyway.

At scale
  • seat_inventory(instance, seat,
  • owner, hold_expires_at)
  • unique (instance, seat)
  • sold count: UPDATE .. SET sold =
  • sold + n WHERE sold + n <= limit
  • one row update = the lock
  • holds: expires_at column
  • PNR: unique index, scrambled seq
  • search: cached, read replicas

Extensibility

Now the stretches. A multi-leg trip, Bangalore to Delhi to London, is an itinerary of legs that must all succeed: hold each leg, take instance locks in a fixed id order to avoid deadlock, and release every hold if one fails. Loyalty miles are an observer that hears when a booking is flown and credits miles by distance. Exit row fees are another pricing rule, and a sold-out waitlist reuses the cancel path.

Extension points
  • multi-leg itinerary: hold every
  • leg, lock instances in id order,
  • release all if one fails
  • loyalty miles: Observer on
  • booking flown, miles by distance
  • seat fees: PricingStrategy per
  • seat type (exit row, window)
  • waitlist when sold out
  • schedule change: rebook flow

Testing

The full code is below the player. The demo searches on a Sunday and gets only the daily flight. A hold expires after sixteen fake minutes and its late confirm is rejected. Eight threads race for seat one A and exactly one wins. Economy fares climb as the cabin fills, the eighth ticket is refused, the two refund rules pay out differently, and at check-in six travellers get boarding passes while the seventh is denied boarding.

Run it
search: AR101 only on a Sunday
H1 held, 16 minutes pass:
  confirm H1: expired
race for seat 1A: 1 held, 7 refused
economy 33% load: saver 5,000.00
  83% load: saver 8,500.00
8th economy ticket: sold out
saver cancel 119h before: 17,000
flex cancel 47h before: all back
check-in: 6 passes, 1 denied

Follow-ups

Expect follow-ups. Why one lock per departure and not per seat? A booking claims several seats and a sold count together, and they all live in one departure. What if payment succeeds after the hold expired? Try to hold again, and refund automatically if the seats are gone. How is the overbooking percent chosen? From no-show history per route. And which patterns did you use? Strategy for pricing, overbooking and refunds.

Follow-ups to expect
  • why lock per departure?
  • seats only clash within one
  • payment after hold expiry?
  • try to re-hold, else refund
  • fare changed while paying?
  • quoted price is kept
  • how to pick overbooking %?
  • no-show history per route
  • which patterns? Strategy x3,
  • Observer for miles

Say it like this

Here is the short version to say out loud. A flight is a schedule; a flight instance is that flight on one date, and it owns the seats, holds and sold counts under one lock. Holds expire lazily against an injected clock. Confirm turns a hold into a booking with a scrambled, unique PNR. Pricing, overbooking and refunds are strategies, and travellers without a chosen seat get one at check-in.

In the interview
  • "A Flight is a schedule; a
  • FlightInstance is one date and
  • owns seats, holds and sold
  • counts under one lock. Holds
  • expire lazily. Confirm makes a
  • PNR. Pricing, overbooking and
  • refunds are strategies; seats
  • without a choice are given at
  • check-in."

Interview questions

What is the difference between a Flight and a FlightInstance?

A Flight is the schedule: number, route, departure time, days of the week and aircraft. A FlightInstance is that flight on one date and owns the changing state: seat owners, holds, sold counts and check-ins. Mixing them up makes a seat look taken on every date at once.

How do you prevent the same seat being booked twice?

Check and claim inside one atomic step. Here every seat owner lives in a map on the flight instance, guarded by that instance's lock, so the second traveller sees the owner and fails. In a database, a unique row per seat per departure with a conditional update does the same job.

How do seat holds expire?

Each hold stores an expiry time. Every operation on a flight instance first drops holds whose time has passed and frees their seats, under the same lock, so no timer per hold is needed. Inject the clock so tests can move time forward without sleeping.

How would you generate PNRs?

Use six characters from a 32 symbol alphabet without confusing letters, which gives 30 bits. Scramble an atomic counter with an odd multiplier modulo 2 to the 30th: the mapping is one to one, so codes never repeat and do not look sequential. A unique index in the database is the final safety net.

How does overbooking work in your design?

An OverbookingPolicy returns a sell limit per cabin, which can exceed the physical seats. Holds check against the sell limit, while seats without a choice are assigned at check-in. If none are left, the traveller is denied boarding and offered another flight with compensation.

How do you price fares by demand?

A PricingStrategy takes the flight, cabin, fare type, current load factor and days to departure, and returns a fare. The load is read under the instance lock, and the quoted price is stored on the hold, so the traveller pays what they were shown.

How do you handle cancellation and refunds?

Map each fare type to a RefundPolicy, such as a saver refund minus a fee before a deadline and a flex refund until departure. Cancel runs under the instance lock, computes the refund, frees the seats and sold count, and marks the booking cancelled exactly once.

What does check-in do?

It checks the time window, then under the instance lock keeps the chosen seat or assigns the first free one in the cabin, marks the traveller checked in, and issues a boarding pass with a group and a sequence number. Checking in twice is rejected.

How would you extend this to multi-leg itineraries?

Model an itinerary as a list of legs that must all be held. Lock the flight instances in a fixed order, such as by id, to avoid deadlock, hold every leg, and release all holds if any leg fails. Confirm all legs under one PNR after payment.