Build a Railway Reservation System

Difficulty: Hard · Category: Booking System · Languages: Java 17, Python 3.11, Go 1.22, Node.js 20, TypeScript 5.x

Railway Reservation System

1. Objective

Build a railway reservation system that supports:

• Seat booking with berth preference
• RAC (Reservation Against Cancellation)
• Waiting List management
• Ticket cancellation
• Automatic promotion (Waiting → RAC → Confirmed)

The system simulates basic Indian railway booking logic. The kv-store provides an in-memory key-value API for managing bookings and seat state — no external database server required.

Recommended infrastructure: kv-store — an in-memory key-value store for managing bookings and seat state, but you may use pure Java collections if you prefer.

How It Works

The platform injects your chosen infrastructure SDK(s) via constructor. For example, if you use the kv-store:

public class MyReservationSystem implements TrainTicketBookingContract {
    private final KVStoreClient kvStore;

    public MyReservationSystem(KVStoreClient kvStore) {
        this.kvStore = kvStore;
    }

    // ... implement methods using kvStore.put(), kvStore.get(), etc.
}

See the SDK Docs tab for the full API reference of your chosen system.

2. Scope

In Scope:

• Train reservation lifecycle: book, cancel, view ticket
• Seat allocation with berth preferences
• RAC queue management
• Waiting list queue management
• Automatic promotion chain on cancellation

Out of Scope:

• Payment processing
• Authentication
• Multiple trains

3. System Constraints

Train capacity is fixed. Example configuration:

4. Berth Types

Supported berth types: LOWER, MIDDLE, UPPER, SIDE_LOWER, SIDE_UPPER

Example distribution:

The initialize() method sets total confirmed berths. Distribute berth types as you see fit, ensuring all five types exist.

5. Core Entity

Passenger
---------
passengerId
name
age
gender
berthPreference
allocatedBerth
seatNumber
status

Status values: CONFIRMED, RAC, WAITING, CANCELLED

6. Recommended Data Structures

Map<String, Passenger> allPassengers     // keyed by passengerId
Map<Integer, Passenger> confirmedSeats    // keyed by seatNumber
Queue<Passenger>        racQueue          // FIFO
Queue<Passenger>        waitingList       // FIFO

Seat tracking:

Map<Integer, String>  berthMap    // seatNumber → berthType
Map<Integer, Boolean> seatStatus  // seatNumber → occupied?

7. Seat Allocation Rules

Rule 1 — Confirmed Seats

If confirmed seats are available: assign the passenger a berth based on preference if possible. If the preferred berth is unavailable, assign any available berth. Status = CONFIRMED.

Rule 2 — RAC

If confirmed seats are full: passenger goes to the RAC queue. RAC passengers share side-lower berths (2 RAC passengers per berth). Status = RAC.

Rule 3 — Waiting List

If RAC is also full: passenger goes to the waiting list. No berth or seat is assigned. Status = WAITING.

Rule 4 — Booking Rejection

If all lists are full: reject the booking (return null).

8. Booking Flow

IF confirmed seat available
    allocate seat with berth preference
    status = CONFIRMED
ELSE IF RAC available
    push to RAC queue
    status = RAC
ELSE IF waiting list available
    push to waiting queue
    status = WAITING
ELSE
    reject booking (return null)

9. Cancellation & Promotion Logic

When a booking is cancelled:

Cancel the passenger

IF cancelled passenger was CONFIRMED
    free the berth
    IF RAC not empty
        move first RAC → CONFIRMED (assign freed berth)
    IF waiting list not empty
        move first WAITING → RAC

ELSE IF cancelled passenger was RAC
    remove from RAC queue
    IF waiting list not empty
        move first WAITING → RAC

ELSE IF cancelled passenger was WAITING
    simply remove from waiting list

This simulates real railway promotion logic.

10. Promotion Flow Example

Initial state: Confirmed = 63, RAC = 10, Waiting = 5

One confirmed passenger cancels:

1. Free the confirmed berth
2. RAC[0] → CONFIRMED (assign the berth)
3. WL[0] → RAC

Final state: Confirmed = 63, RAC = 10, Waiting = 4

11. Seat Tracking Example

Example seat map:

Seat 1 → LOWER
Seat 2 → MIDDLE
Seat 3 → UPPER
Seat 4 → LOWER
Seat 5 → MIDDLE
Seat 6 → UPPER

Allocation example:

Passenger preference: LOWER

Check available LOWER seats
IF available → assign that seat
IF not available → allocate next free seat of any type

12. 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();
}

13. Method Details

14. Error Handling

15. Example Booking Scenario

initialize(63, 18, 10)

// Confirmed booking with preference
id1 = bookPassenger("Arun", 32, "M", "LOWER")
getBookingDetails(id1)
→ {status=CONFIRMED, allocatedBerth=LOWER, seatNumber=1, ...}

// Fill all 63 confirmed berths...
// Next passenger goes to RAC
id64 = bookPassenger("Ravi", 28, "M", "UPPER")
getBookingDetails(id64)
→ {status=RAC, allocatedBerth=null, seatNumber=-1, ...}

// Fill all 18 RAC slots...
// Next passenger goes to Waiting List
id82 = bookPassenger("Priya", 25, "F", "LOWER")
getBookingDetails(id82)
→ {status=WAITING, allocatedBerth=null, seatNumber=-1, ...}

// All 91 slots full — booking rejected
id92 = bookPassenger("TooLate", 30, "M", "NONE")  → null

// Cancellation triggers promotion chain
cancelBooking(id1)  → true
// RAC[0] promoted to CONFIRMED (gets a berth)
// WL[0] promoted to RAC

16. Core Algorithms Required

17. Constraints

• name is non-null, non-empty
• age > 0
• gender is "M" or "F"
• berthPreference is one of: "LOWER", "MIDDLE", "UPPER", "SIDE_LOWER", "SIDE_UPPER", or "NONE"
• Passenger IDs must be unique
• allocatedBerth is null and seatNumber is -1 for RAC/WL passengers
• Promotion must maintain FIFO order within RAC and Waiting queues
• Thread-safe: concurrent bookings must not exceed capacity
• Performance target: ≥ 10,000 ops/sec with p99 ≤ 5 ms

18. Hints

• Use a ConcurrentHashMap for passenger storage keyed by ID, or leverage the kv-store for structured key-value state management.
• Use a LinkedList or ConcurrentLinkedQueue for RAC and WL queues to maintain FIFO order.
• Track available berths per type in a Map<String, Integer> or use a Queue per berth type for allocation.
• For thread safety, use synchronized blocks or ReentrantLock around the booking/cancellation/promotion logic.
• Generate unique IDs with UUID.randomUUID() or an AtomicLong counter.
• The promotion chain must be atomic: cancel + promote RAC + promote WL should happen in one synchronized block to avoid inconsistent state.
• Edge case: when cancelling with no RAC passengers, just free the berth. When cancelling RAC with no WL, just remove from RAC.

Infrastructure your code runs against

• Key-Value Store

How your solution is graded

Your score combines functional correctness (50%), performance (30%) and code quality (20%).

• Target throughput: 10,000 operations/second
• Target p99 latency: 5 ms
• Load test concurrency: 8 concurrent clients
• Load test duration: 10 seconds
• Maximum error rate: 0.1%

Practice this problem

• Solve Build a Railway Reservation System in the browser
• Read the walkthrough

Related LLD problems

• Build a Cab Booking System
• Build a Load Balancer
• Build a URL Shortener