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

By Gregor Dzierzon

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.
>
> 1. **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.
> 2. **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.
> 3. **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](https://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:

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

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

1. **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.
2. **Change how the desk keeps its items** in `add`, so `find` can answer in 120 looks or fewer. You may add a field to the class to keep them in.
3. **Change `find`** to use it. Keep counting: every item it looks at adds 1 to `looks`.
4. **Finish `itemWithTag`** (`ItemWithTag` in C#, `item_with_tag` in Python): the item with that tag number in one step, or `"empty"` if no item has it.
5. **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.*

&lt;details>
&lt;summary>Stuck?&lt;/summary>

- **Today's `find` never 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#, a `Map<String, List<String>>` in Java, a `dict` in Python and a `Map` in JavaScript and TypeScript. In `add`, 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.

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

```text
Blue Water Bottle (Bottles): yes, looks: 2
Purple Scarf (Clothing): no, looks: 1
Tag 6: Blue Water Bottle
```

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

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

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

&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-lost-and-found`), 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. If you cloned the starter, point your copy at your own repo, then commit and push:

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

   If you downloaded the ZIP instead:

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

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

## Key terms

- [Data Structure](https://www.ask-codey.com/glossary/data-structure)
- [Algorithm](https://www.ask-codey.com/glossary/algorithm)
- [Array](https://www.ask-codey.com/glossary/array-data-structures)

## Related

- [800 Lost Items and a Line at the Desk: What a Data Structure Is](https://www.ask-codey.com/lessons/ds-what-is-a-data-structure)
- [Why "Play Track 750,000" Is Instant and "Find Golden Hour" Isn't: Memory as Mailboxes](https://www.ask-codey.com/lessons/ds-memory-as-mailboxes)
- [Running the Exercise Tests](https://www.ask-codey.com/lessons/ds-running-the-tests)

Source: https://www.ask-codey.com/lessons/exercise-ds-lost-and-found
