# 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 November 17, 2026

By Gregor Dzierzon

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:

> 1. **Sign-up:** "How many of these wanted usernames are already taken? We have 100,000 taken names, and check on every visit."
> 2. **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."
> 3. **Subway app:** "Show the fewest stops between two stations. Each track joins two neighboring stations, and the new map has 22,500 stations."
> 4. **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."
> 5. **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](https://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:

```bash
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.md` names 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):

```python
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?

1. **Taken usernames.** Finish `countTaken` (`count_taken` in Python, `CountTaken` in C#).
2. **The most played song.** Finish `mostPlayed`. With no plays, return an empty string.
3. **The fewest stops.** Finish `fewestStops`. A station is 0 stops from itself, and -1 means no tracks join them.
4. **Balanced brackets.** Finish `bracketsBalanced`.
5. **The spam guard.** Finish `blockedMessages`.
6. **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.

&lt;details>
&lt;summary>Stuck?&lt;/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.

&lt;/details>

## When you're done

Every test is green, and the demo prints the same six lines in every language:

```text
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?

&lt;details>
&lt;summary>Why Should I Choose This?&lt;/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.

&lt;/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.

&lt;details>
&lt;summary>Some answers&lt;/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.

&lt;/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.

1. 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.
2. 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:

   ```bash
   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 main
   ```

3. Paste 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.

## Key terms

- [Data Structure](https://www.ask-codey.com/glossary/data-structure)
- [Big-O Notation](https://www.ask-codey.com/glossary/big-o-notation)
- [Time Complexity](https://www.ask-codey.com/glossary/time-complexity)
- [Sliding Window](https://www.ask-codey.com/glossary/sliding-window)

## Related

- [The Feature Is Slow: Which Structure Fixes It?](https://www.ask-codey.com/lessons/ds-choosing-a-structure)
- [Your Turn at the Whiteboard: Solving a Problem Out Loud](https://www.ask-codey.com/lessons/ds-solving-out-loud)

Source: https://www.ask-codey.com/lessons/exercise-ds-pick-the-structure
