Lab · Data Structures and Algorithms (DSA) for interviews
Lab: stacks, queues and linked lists for a train-booking site
The brief
Build four small tools for a train-booking website: a bracket checker for GST invoice templates (a stack), back and forward buttons (two stacks), a waitlist that confirms in order (a queue), and a train's coaches as a linked list that you reverse and split at the middle.
Why it matters
Template engines check brackets with a stack, browsers keep history in two stacks, booking systems confirm waitlists in queue order, and linked-list reversal and fast and slow pointers are among the most asked interview questions at Indian product companies.
Skills you practise
- stacks
- two-stack history
- queues with collections.deque
- linked list reversal
- fast and slow pointers
What you will have at the end
travel.py: a bracket checker, browser history, a waitlist queue and linked-list tools, each tested with edge cases.
How it is marked (rubric, 100 points)
| Correct resultsEvery check passes, including empty input, going back past the first page and an empty waitlist. | 45 |
|---|---|
| Right structure for each jobA stack for brackets and history, a deque for the waitlist, pointer changes (not new lists) for the coaches. | 30 |
| Clear codeReadable names (back_stack, waiting, prev, slow, fast); each method does one thing. | 10 |
| Can explain itYou can say why list.pop(0) is O(n) and deque.popleft() is O(1). | 15 |
0/5 steps done
Step 1 of 5
Check the invoice template's brackets
is_balanced(template) returns True when every (, [ and { is closed by the matching bracket in the right order, and False otherwise.
The invoice template uses {{gstin}} placeholders, (brackets) and [lists]. A stack fits because the last bracket opened must be the first one closed. Push each opening bracket; for a closing bracket, the top of the stack must be its partner.
At the end the stack must be empty, or something was left open. Other characters are ignored. O(n) time, O(n) space for the stack.
Run shows what your code prints. Check runs the step's tests. Ctrl+Enter checks too.