Reasoning Checkpoint
A design challenge, worked through in writing — no auto-grading, just a real attempt.
The Challenge
Samantha has four new features planned for the festival. John asks Anna to choose, for each one, the right data structure — and to say how fast its main operation will be in Big-O. No code needed; this is the thinking that comes before code.
1. The waitlist: when a ticket is returned, offer it to the person who joined the waitlist first. 2. Ticket check at the gate: scan a QR code and instantly say whether that ticket ID is valid. 3. Undo in the organiser's seat editor: organisers move seats around and need an "Undo last change" button. 4. Seat browsing: show free seats grouped by stand, then section, then row.
What Your Answer Needs
- For each feature, name the data structure you'd use.
- For each feature, give the everyday analogy that matches it (plates, line, coat check, family tree...).
- For each feature, give the Big-O of its main operation and explain it in one sentence.
- For the gate check, explain what would go wrong at the festival gate if the valid ticket IDs were kept in a plain array instead.
- Bonus: one feature could accidentally become O(n²). Say which one, and how.
Stuck? A Few Hints
- Ask the question from chapter 3: "What will my code ask most often?"
- 50,000 tickets are scanned at the gate in about an hour.
- A loop inside a loop over the same data is the classic O(n²) trap.
Before You Move On
Notice that you never had to write code to make these decisions — and they matter more than any single line you'll write. Picking the structure that answers your most common question in O(1) or O(log n) is the core habit of performance-aware engineering. The dedicated DSA course takes all of this much further.