Exercise: Find the Song
A music app's search box freezes on a million songs: write the catalog's search so it reads at most 20 titles, keep the playlist search that reads from the top, count what each one reads, and let the tests check them, edge cases and 10,000 searches included.
Apprentice · Data Structures · Updated
Here's the ticket from the music app's search team:
Our catalog has grown to a million songs, and the search box looks a title up on every keystroke. Today's search reads the titles from the top, so a song that isn't there costs a million reads per keystroke, and the box freezes while people type.
- The catalog arrives sorted A to Z every night. You can count on that order.
- A catalog search reads at most 20 titles in a million songs, found or not, and 10,000 searches finish in under a second.
- Playlists aren't sorted. They keep the search that reads from the top, so it has to work on any order.
- We want to see the difference: for each search, count how many titles it reads.
You've met both searches in this chapter, and now you write them for real. The tests try the edge cases where searches go wrong, then a library of 1,000 songs, then the ticket's catalog: 10,000 searches in a million songs, in under a second.
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-find-the-song, 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-find-the-song.git
Git makes a folder, exercise-ds-find-the-song, 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 four functions to finish, two for playlists and two for the catalog (the repository's
README.mdnames 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 the lesson's 16-song library and on a library of 1,000 songs.
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 -1 or 0 for now. The comment above each one says what it should return, with examples. Here is the first one in Python, as the starter has it (the other languages say the same in their own syntax):
def linear_search(songs, title):
"""
Look at each song in turn, from the first, and give back the
position of the first one whose title matches. Give back -1 when
the title isn't in the list. The list can be in any order.
Capital letters count: "Slow Rain" and "slow rain" are different.
linear_search(["Midnight Bus", "Lemon Skies", "Slow Rain"], "Slow Rain") -> 2
linear_search(["Midnight Bus", "Lemon Skies", "Slow Rain"], "Blue Hour") -> -1
Growth rate: (write it here)
"""
return -1
- The playlist search. Finish
linearSearch(linear_searchin Python,LinearSearchin C#): the position of the first song with the title, read from the top, or -1. - Count its reads. Finish
linearLooks: how many titles that search reads, up to and including the match, or all of them when the song is missing. - The catalog search. Finish
binarySearchfor a list sorted A to Z: at most 20 reads in a million songs. - Count its reads. Finish
binaryLooks: how many titles your catalog search reads. - Name the growth rates. On each search'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 FindTheSong |
| 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 function you finish turns its tests green. A failing test's message starts with Not yet: and says what it expected, for example Not yet: Orange Sky would come between Neon Garden and Paper Boats, and it isn't there.
<details> <summary>Stuck?</summary>
- Where to look: the catalog search is the one from One Song in a Million, in 20 Looks: Binary Search; the playlist search is Is That Song in My Library? Linear Search.
- A linear search is a loop, a match and a
return -1after the loop. Return as soon as you find the song. Counting its reads is the same loop with a counter that stops at the match. - The catalog search keeps going while
low <= high. When the middle title comes before the one you want, movelowtomiddle + 1; when it comes after, movehightomiddle - 1. - The tests are the edge cases: the first and last songs, songs missing before, after and in between, a one-song library and an empty one. If one fails, check it against the off-by-one table in the binary search lesson.
- Compare titles the lesson's way:
string.CompareOrdinalin C#,compareToin Java,<in Python, JavaScript and TypeScript.
</details>
When you're done
Every test is green, and the demo prints the same four lines in every language:
Library: 16 songs, A to Z
Quiet Harbor: linear finds position 12 in 13 looks; binary finds position 12 in 4 looks
Orange Sky: linear finds position -1 in 16 looks; binary finds position -1 in 4 looks
1,000 songs, the last one: linear takes 1000 looks; binary takes 10 looks
Now look at the last line. For a million songs, how many reads would each search take for the last song? And what had to be true of the catalog before the faster search could be used at all?
<details> <summary>Why Should I Choose This?</summary>
The ticket's test is 10,000 searches in a million songs. Reading from the top costs about 500,000 titles a search, 5 billion for the test: measured, it got through fewer than 3,000 of the 10,000 searches in the second in every language, and the whole run would take from about 17 seconds in JavaScript to about 2 minutes in Python. Jumping to the first letter still reads tens of thousands of titles a search, and skipping ahead 1,000 at a time about 2,000. Halving reads at most 20, so the test takes a fraction of a second. What it gives up: it needs the catalog sorted. Here the sort is done once a night, before anyone searches; a playlist that's searched once isn't worth sorting, so it keeps the search that reads from the top.
</details>
Where else does this shape show up?
You've used "look in the middle, and throw away the half it can't be in". Before you open the answers, think of three other places, at work or in daily life, where you find something by halving what's left.
<details> <summary>Some answers</summary>
- Finding the change that broke an app: a team with 1,000 changes since the last good version tests the one in the middle, and keeps the half where the bug appeared. About 10 tests find it (Git does this for you with
git bisect). - Finding the line that breaks a program: comment out half the code; if the error goes, it was in that half.
- Finding a word in a paper dictionary, or a name in a phone book.
- The guessing game, "higher or lower?", which never needs more than 7 guesses for a number from 1 to 100.
- Finding the dead bulb in a string of lights: test the middle of the string, then the half that's dark.
</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-find-the-song), 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-find-the-song.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-find-the-song, 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 written the two searches every app is built on and watched one take 1,000 reads where the other takes 10, and a million where the other takes 20. The fast one only worked because the catalog was already sorted, so the next chapter asks the obvious question: how do you sort it?