Exercise: Build a Coat Check
The paper tickets ran out, and 3,000 coats are coming: build a coat check that hands any coat back in a moment however full it gets, keeps every coat when two names share a hook, and moves to a bigger room before it slows down. The tests check it, collisions and a busy night included.
Journeyman · Data Structures · Updated
Here's the ticket from Riverside Hall's manager:
Saturday's concert sold 3,000 tickets, and the coat check's paper tickets run out on every big night. So from now on there are no tickets: guests say their name when they hand over a coat, and say it again to get it back.
- Every handout takes a moment, whether 30 coats are hanging or 50,000. At 11 p.m. everyone wants their coat at once.
- No coat is ever lost or handed to the wrong person, even when two names end up on the same hook. A guest who checks a second coat under the same name swaps it for the first.
- The rack grows. We start with 4 hooks. When there are more coats than three-quarters of the hooks, we move to a room with twice as many hooks and hang every coat again.
- A guest who leaves early can take their coat back off the rack.
You've met every piece of this in the chapter, and now you build the whole coat check. The tests put in names that share a hook on purpose, then 1,000 coats, then a busy night of 50,000 that has to finish in under 2 seconds, so you'll know every coat stays findable, and fast, through every moving day.
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-coat-check, 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-coat-check.git
Git makes a folder, exercise-ds-coat-check, 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 a
CoatCheckclass and five methods to finish (the repository'sREADME.mdnames the file for each language); - the tests that check your coat check. You don't need to change them;
- a demo program that tries your coat check on five guests.
In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.
What's already there
The class starts with 4 hooks. Each hook holds a chain, a list of entries, and each entry is a name with its coat. Three methods are written for you:
hookFor(name)(HookForin C#,hook_forin Python): the times-31 recipe from Why Is Everyone on Hook 3? Hash Functions. It always gives a hook from 0 to one less than the number of hooks.bucketCount()(BucketCountin C#,bucket_count()in Python): how many hooks there are right now.size()(Countin C#): how many coats are hanging. It reads thecountfield, which your code keeps up to date.
Here is get in Python, as the starter has it (the other languages say the same in their own syntax):
def get(self, name):
"""
The coat hanging under this name, or None if nobody checked in under it.
Go to the name's hook and walk its chain.
put("Maya", "green raincoat") -> get("Maya") is "green raincoat", get("Leo") is None
Growth rate: (write it here)
"""
return None
What to do
- Get a coat. Finish
get: find the name's hook, walk along its chain, and return the coat of the entry whose name matches. Nobody there? Returnnull(Nonein Python). - Put a coat. Finish
put. If the name is already in its hook's chain, replace that entry's coat and stop: a name is never listed twice. Otherwise add a new entry to the chain and add 1 tocount. - Remove a coat. Finish
remove: take the name's entry out of its chain, take 1 offcount, and returntrue. If the name isn't there, returnfalse. - Measure how full it is. Finish
loadFactor: coats divided by hooks, as a decimal. - Move to a bigger room. Finish
resize: make twice as many hooks, then hang every coat again on its new hook. Then makeputcall it whenever, after adding a new name, the coat check is more than three-quarters full. - Name the growth rates. On each method's Growth rate: line, write its Big-O and a few words on why.
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 BuildACoatCheck |
| 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 9 tests fail. That's expected: each method you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: Maya and Zoe share hook 0, and Zoe's coat is the yellow umbrella.
<details> <summary>Stuck?</summary>
- Maya and Zoe share hook 0 while there are 4 hooks, so they're your first collision. If
get("Zoe")gives Maya's coat, your loop returns the first entry on the hook instead of the one whose name matches. - Replacing isn't adding. If the "same name again" test fails with a count of 2,
putadded a second entry instead of changing the coat on the first. - "More than three-quarters full" is
count > 0.75 * bucketCount. Without decimals:count * 4 > bucketCount * 3. With 4 hooks, the 3rd coat is exactly three-quarters, so the move happens on the 4th. - In
resize, put the new hooks in place first, then rehash.hookForuses the current number of hooks, so once the new, bigger list is in place, it gives every name its new hook. Keep the old list in a variable so you can walk it. - Stuck on a growth rate?
get,putandremovework on one hook and its short chain.resizetouches every coat. Collisions: Two Coats, One Hook explains why a put is still O(1) on average.
</details>
When you're done
Every test is green, and the demo prints the same five lines in every language:
Hooks at the start: 4
Maya goes to hook 0, and Zoe to hook 0
Zoe's coat: yellow umbrella
After 5 coats: 8 hooks, load factor 0.625
After Leo leaves: 4 coats, Leo's coat: none
Now look at the 1,000-coat test. Your coat check moved nine times on the way from 4 hooks to 2,048, and every coat was found afterward. Each move got bigger, but they got rarer just as fast. Why does that keep a put at O(1) on average?
<details> <summary>Why Should I Choose This?</summary>
On the busy night, 50,000 coats go in and come back out. Coats kept in arrival order would mean reading about 25,000 name tags per handout, over a billion for the night. A rack kept in A to Z order finds a coat in about 16 looks, but slides about 600 million coats along while the 50,000 arrive. Your coat check works out the hook from the name, checks a chain of a coat or two, and moves to a bigger room only 15 times on the way to 131,072 hooks. What it gives up is order: listing every guest from A to Z still means sorting.
</details>
Where else does this shape show up?
You've built "turn the name into the place to look". Before you open the answers, think of three other places, at work or in daily life, where something is stored under a name or a number and found again straight away, without searching.
<details> <summary>Some answers</summary>
- A login page turns your email into the place your account is kept.
- A shopping cart finds a product's price from its code.
- A spell checker knows at once whether a word is in its dictionary (a hash table with only keys, which the next chapter calls a set).
- A library's call number says which shelf a book is on, worked out from the book itself.
- A parcel locker opens the one door your pickup code points to.
</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-coat-check), 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-coat-check.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-coat-check, 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 built the structure behind every dictionary and set you'll ever use, collisions, moving day and all. From now on, when you write Dictionary, HashMap, dict or Map, you know what happens when you put something in, and why getting it back is fast.