Building an Indian Railway Reservation System

Confirmed berths, RAC, Waiting List — with FIFO promotion chains and berth preferences, all in-memory

By SysAdmin · Published 2026-05-27

Building an Indian Railway Reservation System

If you've ever booked an IRCTC ticket, you've seen the magic: Confirmed → RAC → Waiting List. Behind this seemingly simple queue is a cascading promotion engine that must handle thousands of concurrent bookings without overselling a single berth.

1. The Problem

Implement the Indian Railway reservation model:

• Confirmed berths — each passenger gets a dedicated berth (LOWER, MIDDLE, UPPER, SIDE_LOWER, SIDE_UPPER)
• RAC (Reservation Against Cancellation) — passengers share side-lower berths, promoted when confirmed passengers cancel
• Waiting List — no berth assigned; promoted to RAC as RAC slots free up
• Cancellation cascade: Cancel confirmed → promote RAC → confirmed, then WL → RAC
• Berth preferences honoured when possible, fallback to any free berth
• All state in-memory, thread-safe

2. The Naïve Approach (and Why It Fails)

int availableSeats = 63;

public String book(String name) {
    if (availableSeats > 0) {
        availableSeats--;
        return "CONFIRMED";
    }
    return "REJECTED";
}

This misses the entire reservation model:

1. No RAC or Waiting List — passengers are either confirmed or rejected, wasting potential capacity
2. No promotion chain — when confirmed passengers cancel, nobody gets upgraded
3. No berth tracking — can't honour preferences or prevent double-allocation

3. The Right Model

Three data structures:

┌─────────────────────────┐
│   Confirmed List        │  (capacity: e.g. 63)
│   Each pax → berth type │
│   + seat number         │
├─────────────────────────┤
│   RAC Queue (FIFO)      │  (capacity: e.g. 18)
│   No berth assigned     │
├─────────────────────────┤
│   Waiting List (FIFO)   │  (capacity: e.g. 10)
│   No berth assigned     │
└─────────────────────────┘

Berth inventory tracked separately:

4. The Implementation, Walked Through

The Interface

public interface TrainTicketBookingContract {
    void initialize(int confirmedBerths, int racCapacity, int waitingListCapacity);
    String bookPassenger(String name, int age, String gender, String berthPreference);
    boolean cancelBooking(String passengerId);
    Map<String, Object> getBookingDetails(String passengerId);
    Map<String, Integer> getAvailableCounts();
    List<Map<String, Object>> getConfirmedPassengers();
    List<Map<String, Object>> getRACQueue();
    List<Map<String, Object>> getWaitingList();
    Map<String, Integer> getBookedCount();
}

Booking Logic — The Three-Tier Waterfall

public synchronized String bookPassenger(String name, int age,
        String gender, String berthPreference) {
    if (confirmedList.size() < confirmedTotal) {
        String berth = allocateBerth(berthPreference);
        // assign berth + seat number, status = CONFIRMED
        confirmedList.add(id);
    } else if (racQueue.size() < racTotal) {
        // no berth, no seat, status = RAC
        racQueue.add(id);
    } else if (waitingList.size() < wlTotal) {
        // no berth, no seat, status = WAITING
        waitingList.add(id);
    } else {
        return null;  // completely full
    }
    return id;
}

The synchronized keyword ensures two threads can't book the last confirmed berth simultaneously.

Berth Allocation with Preference

private String allocateBerth(String preference) {
    // Try preferred berth first
    if (!"NONE".equals(preference) && berthAvail.get(preference) > 0) {
        berthAvail.put(preference, berthAvail.get(preference) - 1);
        return preference;
    }
    // Fallback: any available berth
    for (String type : BERTH_TYPES) {
        if (berthAvail.get(type) > 0) {
            berthAvail.put(type, berthAvail.get(type) - 1);
            return type;
        }
    }
    return "LOWER"; // should never reach here if capacity is correct
}

The Cancellation Cascade — The Heart of the System

This is the most complex part. When a confirmed passenger cancels:

public synchronized boolean cancelBooking(String passengerId) {
    String status = pax.get("status");
    
    if ("CONFIRMED".equals(status)) {
        confirmedList.remove(passengerId);
        freeBerth(pax.get("allocatedBerth"));  // return berth to pool
        pax.put("status", "CANCELLED");

        // Step 1: Promote first RAC → Confirmed
        if (!racQueue.isEmpty()) {
            String racId = racQueue.remove(0);  // FIFO
            racPax.put("allocatedBerth", allocateBerth(racPax.get("berthPreference")));
            racPax.put("status", "CONFIRMED");
            confirmedList.add(racId);

            // Step 2: Promote first WL → RAC
            if (!waitingList.isEmpty()) {
                String wlId = waitingList.remove(0);  // FIFO
                wlPax.put("status", "RAC");
                racQueue.add(wlId);
            }
        }
    } else if ("RAC".equals(status)) {
        racQueue.remove(passengerId);
        // Promote first WL → RAC
        if (!waitingList.isEmpty()) { ... }
    } else if ("WAITING".equals(status)) {
        waitingList.remove(passengerId);  // just remove, no cascade
    }
}

💡 Key insight: The cascade is always two levels deep at most. A confirmed cancellation can trigger RAC→Confirmed AND WL→RAC. But a RAC cancellation only triggers WL→RAC. A WL cancellation triggers nothing.

5. Performance + Concurrency

• synchronized on all public methods ensures mutual exclusion
• All operations are O(n) in the worst case (list removals), but with typical train capacities (63 + 18 + 10 = 91 passengers), this is effectively O(1)
• For production scale (10K trains, 100K concurrent users), you'd shard by train and use fine-grained locks

6. What the Grader Checks

7. Takeaways

1. Cascading promotions are the real challenge, not booking. Booking is a simple waterfall, but cancellation must correctly cascade through up to two tiers while maintaining FIFO order.

1. Berth inventory is separate from passenger tracking. Tracking berth availability independently from the passenger list makes allocation and deallocation clean — allocateBerth() and freeBerth() are symmetric operations.

1. FIFO order is critical for fairness. The first person in RAC should be the first promoted to Confirmed. Using ArrayList with remove(0) gives natural FIFO behavior (or use a LinkedList for O(1) removal).

👉 Try it yourself: Train Ticket Booking on Cruscible