Exercise: Pick the Structure
Five tickets from apps you use, each easy to get right on a small input and only fast on a big one with the right choice, one of them a problem the course hasn't shown: choose the structure, write it, name its Big-O, and let the tests time it.
Journeyman · Data Structures · Updated
Every slow feature you'll ever fix started as code that worked fine on a small test. This exercise is five of those features, each as the ticket a team would send you:
- Sign-up: "How many of these wanted usernames are already taken? We have 100,000 taken names, and check on every visit."
- Music app: "Show a 'most played' badge: the title played the most times, ties going to the title first from A to Z. A busy day is 200,000 plays."
- Subway app: "Show the fewest stops between two stations. Each track joins two neighboring stations, and the new map has 22,500 stations."
- Code editor: "Warn when the brackets in a line don't match: every
(,[and{closed by the same kind, in the right order. Some generated files nest 100,000 deep."- Chat room: "Block spam. A message is blocked when its sender already sent 3 or more messages in the 10 seconds before it, and every message counts, blocked or not. Count the blocked ones. A spam wave is 800,000 messages."
Each one is easy to get right for five items. The tests then try the big size, and only the right choice finishes in under 2 seconds. The first four look like jobs from the course; the fifth, the chat room, is one the course hasn't shown. Nobody tells you the structure: choosing it is the exercise.
Before you start
You need one language set up, as in Setup: VS Code and Your Language. The exercise is written in all five of the course's languages; pick the one you use.
Get the exercise code
Open this lesson's GitHub repository, github.com/ask-codey/exercise-ds-pick-the-structure, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:
git clone https://github.com/ask-codey/exercise-ds-pick-the-structure.git
Git makes a folder, exercise-ds-pick-the-structure, with the exercise code inside.
The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:
- your code: one file with five functions to finish (the repository's
README.mdnames the file for each language); - the tests that check your functions. You don't need to change them;
- a demo program that tries your functions on small examples.
In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.
What to do
Every function is already there, with its parameters, and returns 0, an empty string or false for now. The comment above each one says what it should return, with examples, and ends with a Structure: line. Here is the fifth one in Python, as the starter has it (the other languages say the same in their own syntax):
def blocked_messages(messages):
"""
A chat room's spam guard. Each message is a sender's name and the
second it was sent, and the messages come in time order. A message
is blocked when its sender already sent 3 or more messages in the 10
seconds before it: at a second greater than this one's minus 10.
Every message counts toward the limit, blocked or not. Return how
many messages are blocked. A busy room sends 800,000 messages an
hour, so this has to stay fast.
blocked_messages([("Kai", 1), ("Kai", 2), ("Kai", 3), ("Kai", 4)]) -> 1
blocked_messages([("Kai", 1), ("Kai", 2), ("Kai", 3), ("Kai", 11)]) -> 0
Structure: (write the structure you used, and this function's Big-O)
"""
return 0
For each ticket, work through the questions from The Feature Is Slow: Which Structure Fixes It?: what does the job do most, what has to be fast, and which structure makes that cheap?
- Taken usernames. Finish
countTaken(count_takenin Python,CountTakenin C#). - The most played song. Finish
mostPlayed. With no plays, return an empty string. - The fewest stops. Finish
fewestStops. A station is 0 stops from itself, and -1 means no tracks join them. - Balanced brackets. Finish
bracketsBalanced. - The spam guard. Finish
blockedMessages. - Name your choices. On each function's Structure: line, write the structure you used and the function's Big-O.
Check your work
Each language has its own command, run in the terminal in your language's folder (Terminal > New Terminal in VS Code). The repository's README.md has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (npm install).
| Language | Run the tests | Run the demo |
|---|---|---|
| C# | dotnet test |
dotnet run --project PickTheStructure |
| Java | ./mvnw test (.\mvnw test in PowerShell) |
java src/main/java/Demo.java |
| Python | python -m pytest |
python demo.py |
| JavaScript | npm test |
node demo.js |
| TypeScript | npm test |
node demo.ts |
At first all 10 tests fail. That's expected: each function you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected.
Each ticket has two tests: one with small examples, and one with the big input that has to finish in under 2 seconds, such as Not yet: checking 100,000 names took 8.2 seconds. With the right structure it takes well under one. If a test seems stuck, stop it with Ctrl+C: it's telling you to choose another structure, not that your answer is wrong.
<details> <summary>Stuck?</summary>
Try each ticket on your own first; these name the structures.
- Taken names: the job done most is "is this name in there?". A set answers that in O(1) on average.
- Most played: the job is "add one to this title's count", over and over. A dictionary from title to count finds the count by its name.
- Fewest stops: "fewest" is a level question. Build the map as an adjacency list, then breadth-first search with a queue.
- Brackets: the bracket that has to close next is always the newest one still open: a stack. A recursive answer may run out of call stack on the deep test; a stack of your own won't.
- Spam guard: for each sender, only their messages from the last 10 seconds matter. Keep each sender's recent seconds in a queue, inside a dictionary by sender: new seconds join at the back, and seconds 10 or more back leave from the front.
</details>
When you're done
Every test is green, and the demo prints the same six lines in every language:
Taken: 2 of 4 wanted names
Most played: Slow Rain
Fewest stops from Elm to Harbor: 3
total = (price * [1 + tax]) - {discount}: balanced
(1 + 2]: not balanced
Blocked: 2 of 7 messages
Now read your five Structure: lines out loud, the way you would in an interview: "a set, because checking a name is O(1) on average, so the whole function is O(n)". Could you defend each one to a teammate?
<details> <summary>Why Should I Choose This?</summary>
Open this once your tests are green.
- Taken names: a list makes each check read up to 100,000 names: 100,000 checks is up to 10 billion comparisons. A set makes each check one lookup, so the whole job is O(t + w).
- Most played: sorting the 200,000 plays first works in O(n log n); a dictionary of counts does it in one pass, O(n). Scanning a list of titles for each play is O(n × titles), 10 billion steps with 50,000 titles.
- Fewest stops: trying every route is exponential, and a depth-first walk finds a route, not the fewest. Breadth-first search visits each of the 22,500 stations once, O(V + E).
- Brackets: counting brackets can't tell
(]from(). A stack checks each bracket once, O(n), and never runs out of call stack. - Spam guard: checking every earlier message for each new one is O(n²): with 800,000 messages it ran more than 10 minutes in every language before we stopped it. Keeping each sender's whole history and counting it every time is better, but still slow when each sender has tens of thousands of messages: 9 seconds in JavaScript and TypeScript, 35 in C#, 75 in Java and 9 minutes in Python. A queue per sender holds only the last 10 seconds, and each second joins and leaves it once, O(n): under a fifth of a second in every language.
</details>
Where else does this shape show up?
The spam guard's shape, "only the last few seconds matter, per person", is called a sliding window. Before you open the answers, think of three other places where an app counts something over the last few seconds, minutes or items.
<details> <summary>Some answers</summary>
- A login page that locks an account after 5 failed passwords in 15 minutes.
- An API that allows each app 100 requests a minute, and answers "slow down" after that.
- A fitness tracker showing your average heart rate over the last 30 seconds.
- A stock app drawing the average price over the last 50 trades.
- A music app that won't play the same song twice within the last 20 songs.
</details>
Submit your exercise
The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.
On GitHub, click +, then New repository. Name it (for example
exercise-ds-pick-the-structure), choose Public, and click Create repository. Leave out the README: your folder already has one.In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:
git remote set-url origin https://github.com/your-name/exercise-ds-pick-the-structure.git git add . git commit -m "My solution" git push -u origin mainPaste your repo's address, such as
https://github.com/your-name/exercise-ds-pick-the-structure, into Submit your exercise on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.
Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.
So what
You've chosen five structures from five tickets, one of them new to you, and the tests proved each choice with a stopwatch. That's the whole course in one exercise, and it's what you'll do on your own from here: read the ticket, find the job done most, and choose.
What's next: this was the course's last exercise. Where to Go Next looks back at everything you can now do, and asks you to spot the structures inside three apps you use.