Capstone · Data Structures and Algorithms (DSA) for interviews
Capstone: a mini IRCTC journey and booking engine
The brief
Build the engine of a small train-booking site on a simplified Indian rail network: a station search box, the fewest-change and the fastest or cheapest journeys, region checks when routes close, a coach with confirmed berths and a waitlist, berths free between two stations, the most booked routes, seating groups together, and one function that plans a trip from what a passenger types.
Why it matters
Railway, bus and airline booking systems are built from exactly these parts: indexes for search, graph searches for journeys, queues for waitlists, segment counts for seat quotas, heaps for reports and dynamic programming for allocation. A working, tested engine like this is a strong portfolio project, and you can explain every Big-O in an interview.
Skills you practise
- hash maps
- binary search with bisect
- BFS and Dijkstra
- union-find
- queues with deque
- difference arrays
- heaps
- 0/1 knapsack DP
- putting modules together
What you will have at the end
A GitHub repository with irctc.py, its tests, and a README that explains each part, its data structure and its Big-O, and shows one trip planned from typed station names.
How it is marked (rubric, 100 points)
| Working engineAll ten steps pass, including unknown stations, waitlist changes, segment counts and the 100,000-name search. | 35 |
|---|---|
| Right data structure for each jobbisect, BFS, Dijkstra, union-find, deque, difference array, heap and knapsack DP are each used where they fit. | 25 |
| Complexity explainedEvery function has its time and space Big-O in a comment, and the README explains the main trade-offs. | 20 |
| Code qualitySmall functions, clear names, no repeated logic; plan_trip reuses the other parts. | 10 |
| Portfolio readyA README with a usage example and a short note on what you would add next (for example real timetables). | 10 |
0/10 steps done
Step 1 of 10
The rail network
build_network(routes) returns {code: [(neighbour, minutes, fare), ...]} with every route added both ways.
Store the network as an adjacency list: each station code maps to the routes leaving it. Keep both the minutes and the fare on each edge, so the same graph can answer "fastest" and "cheapest" later.
It takes O(V + E) space, and listing a station's routes is O(its number of routes).
Run shows what your code prints. Check runs the step's tests. Ctrl+Enter checks too.