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

By

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.

  1. Every handout takes a moment, whether 30 coats are hanging or 50,000. At 11 p.m. everyone wants their coat at once.
  2. 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.
  3. 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.
  4. 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 CoatCheck class and five methods to finish (the repository's README.md names 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) (HookFor in C#, hook_for in 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() (BucketCount in C#, bucket_count() in Python): how many hooks there are right now.
  • size() (Count in C#): how many coats are hanging. It reads the count field, 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

  1. 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? Return null (None in Python).
  2. 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 to count.
  3. Remove a coat. Finish remove: take the name's entry out of its chain, take 1 off count, and return true. If the name isn't there, return false.
  4. Measure how full it is. Finish loadFactor: coats divided by hooks, as a decimal.
  5. Move to a bigger room. Finish resize: make twice as many hooks, then hang every coat again on its new hook. Then make put call it whenever, after adding a new name, the coat check is more than three-quarters full.
  6. 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, put added 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. hookFor uses 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, put and remove work on one hook and its short chain. resize touches 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.

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

  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:

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

Key terms

Related