Exercise: The Lost and Found
The lunch line at a school's lost-and-found doesn't move: change the desk so every request for one of 800 items is answered in 120 looks or fewer, and every tag number in one step. The tests check it with a full lunch line.
Novice · Data Structures · Software Development · Updated
Here's the ticket from the school's front office:
By spring the lost-and-found holds about 800 things, and at lunch 30 students line up at the desk. Each one asks for something by its name and its kind ("Blue Water Bottle, it's a bottle"), and the volunteer digs through one big box. Lunch is 30 minutes; the line doesn't make it.
- Every request is answered in 120 looks or fewer, whether the desk has the item or not, even with 800 items. Every item the desk looks at counts as a look.
- Every item handed in gets a tag number in the desk's log: 0 for the first, then 1, 2, 3, in the order they arrive. A student who brings a tag number gets that item in one step, without anyone looking through the others.
- Nothing goes missing. Every item handed in can still be found by its name and kind, and by its tag.
You've met both halves of this in the chapter. The code you start from is the desk as it works today, and it finds things correctly; it's only too slow. Your job is to change how the desk keeps its items, so the lunch line test passes: 800 items, every one of them asked for, every answer in 120 looks or fewer.
Before you start
You need one language set up, as in Setup: VS Code and Your Language, and to know how to run the tests, as in Running the Exercise Tests. 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-lost-and-found, 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-lost-and-found.git
Git makes a folder, exercise-ds-lost-and-found, with the exercise code inside. If you can't clone it, click Code on the repository's page, then Download ZIP, and unzip it into your course folder instead.
The repository has a folder for each language: csharp, java, python, javascript and typescript. Each folder holds:
- your code: one file with the desk, a class called
Desk(the repository'sREADME.mdnames the file for each language); - the tests that check the desk. You don't need to change them;
- a demo program that tries the desk on eight items.
In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.
What's already there
Today's desk keeps everything in one list, box, in the order things are handed in, and counts every item it looks at in looks (Looks in C#, looks() in Java). Here is its find in Python, as the starter has it (the other languages say the same in their own syntax):
def find(self, item, kind):
"""
A student asks for an item by its name and its kind. Return True if
the desk has it, False if not. Add 1 to self.looks for every item
the desk looks at.
find("Blue Water Bottle", "Bottles") -> True
find("Purple Scarf", "Clothing") -> False
Growth rate: (write it here)
"""
for thing in self.box:
self.looks += 1
if thing == item:
return True
return False
It's right every time, and with 8 items it's quick. With 800, a request can read the whole box.
What to do
- Run the tests first. Three pass already, because today's desk finds the right answer. Read the four that fail: their messages say how many looks a request took.
- Change how the desk keeps its items in
add, sofindcan answer in 120 looks or fewer. You may add a field to the class to keep them in. - Change
findto use it. Keep counting: every item it looks at adds 1 tolooks. - Finish
itemWithTag(ItemWithTagin C#,item_with_tagin Python): the item with that tag number in one step, or"empty"if no item has it. - Name the growth rates. On each method's Growth rate: line, write how its work grows as the items grow. Chapter 3 gives these their proper names; for now, "the same however many items" or "grows with the items on one shelf" is a fine answer.
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 LostAndFound |
| 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, 4 of the 7 tests fail. That's expected. A failing test's message starts with Not yet: and says what it expected, for example Not yet: finding Water Bottle 16 took 121 looks. The lunch line needs 120 or fewer, even with 800 items.
<details> <summary>Stuck?</summary>
- Today's
findnever uses the kind the student asked for. What if the desk kept things the way students ask for them? - Where to look: 800 Lost Items and a Line at the Desk: What a Data Structure Is keeps the items on shelves by kind, one labeled list for each kind. With 800 items over 8 kinds, a shelf holds about 100, so a search of one shelf stays under 120 looks.
- Shelves in code: a labeled list is a
Dictionary<string, List<string>>in C#, aMap<String, List<String>>in Java, adictin Python and aMapin JavaScript and TypeScript. Inadd, if there's no shelf for that kind yet, make an empty one first, then put the item on it. - Don't throw the box away. A tag number is a position in the order things arrived, and only the box keeps that order. Keep both: the box for tags, and the shelves for finding.
- A tag in one step is the box at that position, as in Why "Play Track 750,000" Is Instant and "Find Golden Hour" Isn't: Memory as Mailboxes. Tags start at 0, so a number below 0, or equal to the number of items or more, has no item.
</details>
When you're done
Every test is green, and the demo prints these three lines in every language (if you found a way that looks at even fewer items, your two counts are lower, and that's fine):
Blue Water Bottle (Bottles): yes, looks: 2
Purple Scarf (Clothing): no, looks: 1
Tag 6: Blue Water Bottle
<details> <summary>Why Should I Choose This?</summary>
The lunch line is 800 items and 30 students, every day.
- One big box, read from the top: adding is instant, but a request can take 800 looks, and 30 of them is up to 24,000 looks in one lunch.
- A list kept in A to Z order by name: finding an exact name is quick, but every item handed in has to be slotted into its place, and students who say "a water bottle" don't know the exact name.
- Shelves by kind, plus the box: each request looks at one shelf, about 100 items at most, and a tag is one step into the box. What it costs: each item is filed twice, and adding takes a moment longer, which is fine for a few items a day.
- What would beat it: if students always knew the exact name, a structure that goes straight from a name to its item would answer in one look. That's the hash table, in Module 5.
</details>
Where else does this shape show up?
You've kept the same things two ways at once: in the order they arrived, for "number 6, please", and grouped by the way people ask, for "a water bottle". Before you open the answers, think of three other places where things are kept grouped by how people look for them, or numbered so one can be fetched in one step.
<details> <summary>Some answers</summary>
- A grocery store's aisles group things by kind, so "where's the rice?" means one aisle, not the whole store.
- A phone's contacts are kept A to Z, the way you look people up.
- A library's call numbers shelve books by subject, and the number on the spine takes you to the one shelf.
- Seats in a stadium are numbered, so ticket "Row K, Seat 12" is one walk, not a search.
- A music app plays track 750,000 in one step, and keeps a separate index of titles for its search box.
</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-lost-and-found), 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. If you cloned the starter, point your copy at your own repo, then commit and push:
git remote set-url origin https://github.com/your-name/exercise-ds-lost-and-found.git git add . git commit -m "My solution" git push -u origin mainIf you downloaded the ZIP instead:
git init -b main git add . git commit -m "My solution" git remote add origin https://github.com/your-name/exercise-ds-lost-and-found.git git push -u origin mainPaste your repo's address, such as
https://github.com/your-name/exercise-ds-lost-and-found, 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 changed how a program keeps its data, and the same job went from up to 800 looks to about 100, with the code that answers barely changed. That's the course in miniature: choose the structure for the job done most. Counting the looks, and asking how they grow when there's more stuff, is exactly what Big-O is, two chapters from now.