Project · Data Structures and Algorithms (DSA) for interviews
Project: a Delhi Metro journey planner
The brief
Build the engine behind a metro app on a simplified Delhi Metro map: the graph, the route with the fewest stops (BFS), the fastest route (Dijkstra), how many separate networks remain when links close (union-find), a station search box (a trie), change from a ticket machine (DP) and "did you mean" for typos (edit distance).
Why it matters
Maps, metro and ride-hailing apps run shortest-path searches millions of times a day, search boxes use tries, and spell-correction uses edit distance. Graph and DP questions decide most final coding rounds at product companies, and this project gives you one worked system to talk about.
Skills you practise
- adjacency lists
- BFS
- Dijkstra with heapq
- union-find
- tries
- 1-D and 2-D dynamic programming
What you will have at the end
planner.py: a tested journey-planner engine (routes, networks, search, change and spelling help), with a README paragraph comparing fewest stops and fastest route on one real example.
How it is marked (rubric, 100 points)
| Correct resultsAll seven steps pass, including unknown stations, separate networks, ties and the 100,000-station chain. | 40 |
|---|---|
| Right algorithm and costBFS for stops, Dijkstra for minutes, union-find with path halving, a trie and bottom-up DP, each with its Big-O in a comment. | 30 |
| Clean designOne function or class per job, no globals changed, the graph built once and reused. | 15 |
| ExplainedThe README explains why BFS and Dijkstra give different answers for Dwarka Sector 21 to Botanical Garden. | 15 |
0/7 steps done
Step 1 of 7
Build the graph
build_graph(links) returns {station: [(neighbour, minutes), ...]} with every link added in both directions.
An adjacency list stores, for each station, the stations next to it. It uses O(V + E) space and lets you visit a station's neighbours in O(degree), which is what BFS and Dijkstra need.
Trains run both ways, so each link is added twice: a to b and b to a. dict.setdefault(key, []) gives the list for a station, making it the first time.
Run shows what your code prints. Check runs the step's tests. Ctrl+Enter checks too.