Exercise: Find the Duplicate Songs
Users with big libraries say the "find duplicate songs" button never finishes: write a new one with the same answers that handles 200,000 songs in under 2 seconds, count what today's button costs, and name each one's growth rate.
Apprentice · Software Development · Updated
Here's the ticket from the music app's support team:
Users with big libraries say the "find duplicate songs" button never finishes. One user with 50,000 songs waited half a minute and gave up; a DJ with 200,000 songs can't use it at all. Small libraries are fine.
- The same answers as today: every title that appears more than once, listed once, in A to Z order. Capital letters count: "Slow Rain" and "slow rain" are different titles.
- A library of 200,000 songs takes under 2 seconds.
- The user's playlist keeps its own order. The button may not rearrange it.
It's the friend from Twice the Stuff, How Much More Work? again, and the button from Why the Duplicates Button Crawls: O(n²). Today's button is in the code you start from, and it's right; it's only too slow. You write a new one with the same answers, and the tests time it on 200,000 songs.
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-big-o-duplicate-songs, 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-big-o-duplicate-songs.git
Git makes a folder, exercise-big-o-duplicate-songs, 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 today's button and two functions to finish (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 both buttons on an eight-song playlist.
In VS Code, choose File > Open Folder and open your language's folder, not the whole repository.
What's already there
Today's button is findDuplicatesByPairs (FindDuplicatesByPairs in C#, find_duplicates_by_pairs in Python). Here it is in Python, as the starter has it (the other languages say the same in their own syntax):
def find_duplicates_by_pairs(songs):
duplicates = []
for first in range(len(songs)):
for second in range(first + 1, len(songs)):
if songs[first] == songs[second] and songs[first] not in duplicates:
duplicates.append(songs[first])
duplicates.sort()
return duplicates
Leave it as it is: the tests compare your new button's answers with it.
What to do
- Count what today's button costs. Finish
pairChecks(pair_checksin Python,PairChecksin C#): how many comparisons a playlist of a given size needs when every song is compared with every other song once. - Write the new button. Finish
findDuplicates(FindDuplicatesin C#,find_duplicatesin Python): the same answers as today's button, each duplicated title once, in A to Z order, for 200,000 songs in under 2 seconds, without rearranging the playlist it's given. - Name the growth rates. On each function's Growth rate: line, today's button included, 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 DuplicateSongs |
| 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 7 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: Slow Rain appears three times but is listed once, after Lemon Skies. If your new button gives the right answers but takes too long, the last test says how long, for example Not yet: 20000 songs took 5125 ms. The button has 2000 ms, even for 200000 songs.
<details> <summary>Stuck?</summary>
pairChecksis the comparison count from Why the Duplicates Button Crawls: O(n²): two loops, one inside the other, and a counter.- Why today's button is slow: it compares every pair, so twice the songs is about four times the work. Any new button that compares every pair, in any order, has the same problem.
- Where to look: sort a copy of the playlist. After sorting, equal titles sit side by side, so you only ever compare a title with the one right before it. Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ) says why a good sort is fast.
- A copy, not the playlist. A new list made from the old one is a copy:
new List<string>(songs)in C#,new ArrayList<>(songs)in Java,sorted(songs)orlist(songs)in Python,[...songs]in JavaScript and TypeScript. - A title that appears three times is still one duplicate. Before you add a title, check whether it's the last one you added. Checking the whole answer list is a search, and it makes the button slow again.
- Stuck on a growth rate? Count the loops, and use Are Two Loops Twice as Slow? Why O(2n) Is Still O(n) to decide which part counts.
</details>
When you're done
Every test is green, and the demo prints the same four lines in every language:
Playlist: Midnight Bus, Lemon Skies, Slow Rain, Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Slow Rain
Pair checks for 8 songs: 28
Duplicates, today's code: Lemon Skies, Slow Rain
Duplicates, the new button: Lemon Skies, Slow Rain
<details> <summary>Why Should I Choose This?</summary>
- Today's button, every song against every other: about 20 billion comparisons for 200,000 songs, O(n²). Measured on a laptop, it already takes about 5 seconds at 20,000 songs in Python, and 4 to 5 seconds at 60,000 in C#, Java and JavaScript.
- Sort a copy, then compare neighbors: the sort is O(n log n), about 3.6 million comparisons for 200,000 songs, and the walk along the sorted copy is O(n). Measured on the same laptop, 200,000 songs take 28 ms in Python and under 100 ms in every language.
- What it costs: a copy of the playlist, as much memory again as the playlist itself.
- What would beat it: a structure that remembers every title it has seen and answers "seen it before?" in one step, without sorting. That's a hash set, in Module 5, and it finds duplicates in a single pass, O(n).
</details>
Where else does this shape show up?
You've replaced "compare every pair" with "sort first, then look at neighbors". Before you open the answers, think of three other places, at work or in daily life, where a job that seems to need every pair compared can be done by sorting first.
<details> <summary>Some answers</summary>
- Two students with the same birthday in a school of 2,000: sort the birthdays, and any match sits side by side.
- Duplicate customer emails in a shop's mailing list: sort the emails, then walk the list once.
- Two runners with the same finishing time: sort the times, and ties are neighbors.
- Merging two class rosters to see who's on both: sort each, then walk them side by side.
- Spotting a repeated ticket number at an event: sort the numbers, and a repeat is right next to its twin.
</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-big-o-duplicate-songs), 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-big-o-duplicate-songs.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-big-o-duplicate-songs, 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 kept the answers and changed the growth rate: from O(n²), which gave up at 50,000 songs, to O(n log n), which handles 200,000 in a blink. That's the everyday work of Big-O: not memorizing symbols, but noticing the nested loop and knowing there's a faster way. Module 5 shows a third way, with a hash set, that finds duplicates in a single pass.