Capstone — Discovery Feed
The discovery tab is where Tunebox's pieces meet. A listener who loves Rock types "ne", and the feed should show the best few Rock tracks — Punk and Metal included — whose titles start with "ne", most-played first. That's three questions, and this section has already built a structure for each: the genre tree says which genres count, a trie says which titles match, and a heap picks the top k.
The spec, pinned down
discovery_feed(genres, tracks, favorite, prefix, k) takes:
genres— the genre tree as a level-order list,Nonefor a missing childtracks—[title, genre, plays]triples; titles are unique and lowercasefavorite— a genre; the feed draws from it and every genre beneath itprefix— what's been typed so far;""matches everythingk— how many titles to return
It returns up to k titles, most plays first, ties broken alphabetically. A
favorite that isn't in the tree gives [], and a track whose genre isn't in the tree is
never picked.
Pinning ties down isn't pedantry. Two listeners with the same taste must see the same feed, and a test can only check an answer that has exactly one right value.
Stage 1 — the genre tree: which genres count?
Find the favorite's node, then gather its whole subtree. Both are small recursions from the binary trees lesson:
find(...) or find(...) works because a node is truthy and None isn't, so the right
subtree is only searched when the left one came back empty.
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def names(node):
if node is None:
return set()
return {node.val} | names(node.left) | names(node.right)
electronic = Node("Electronic", Node("Techno", None, Node("Acid")), Node("House"))
print(len(names(electronic.left)))Stage 2 — the trie: which titles match?
Insert the titles of the tracks that survived stage 1, walk down the prefix, and collect everything below. Order doesn't matter yet — stage 3 does the ranking — so a plain stack will do:
❓ Cross-question — "For one query, isn't
title.startswith(prefix)simpler?" Honestly, yes: one filter over a few thousand tracks is a single line, and fast enough. The trie pays off when it's built once and queried on every keystroke, because each query touches only the typed letters and the matching subtree. The ⚡ section below keeps the index alive between keystrokes.
Stage 3 — the heap: which k are best?
Rank the matches by (-plays, title). Negating puts the most plays first in Python's
min-heap, and the title settles ties. Getting that key backwards is the classic bug:
Ties should be broken alphabetically, but this puts 'never again' before 'needle drop'.
heapq.nsmallest(k, tracks, key=lambda t: (-t[1], t[0])), or heapify followed by k
pops, gets the order right. You can negate a number but not a string, which is why the
number flips and the title stays as it is.
Filter first, then rank
The stages run so each one hands the next fewer candidates. Step through a miniature pipeline and watch them shrink before the heap ever sees them:
(startswith stands in for the trie to keep the trace short.) Had ranking come first,
the heap would have ordered every track in Tunebox only to throw most of them away.
import heapq
plays = {"nebula": 240, "needle drop": 95, "never again": 95}
heap = [(-count, title) for title, count in plays.items()]
heapq.heapify(heap)
print([heapq.heappop(heap)[1] for _ in range(min(5, len(heap)))])| Stage | Structure | Cost |
|---|---|---|
| Build the genre tree | queue | O(G) |
| Find the favorite and its subtree | recursion | O(G) |
| Build a trie of the allowed titles | trie | O(C), C = their characters |
| Walk the prefix and collect matches | trie + stack | O(p + size of that subtree) |
| Pick the top k of m matches | heap | O(m + k log m) |
The whole feed is roughly linear in its input. Once the indexes exist, a keystroke only pays for the last two rows.
Coming from Java/JS: this is a stream pipeline —
filter,filter,sorted(comparator).limit(k)— with one difference that matters: a heap never sorts the survivors it doesn't return.
Idioms & real-world patterns
Build once, query per keystroke
In a real app the indexes outlive a single call. A class builds them once and answers every keystroke; the graded function is the one-shot version:
⚡ Advanced — the best few on every trie node
If each trie node stores its best few titles, updated as titles are inserted, a keystroke needs no heap at all: walk one step and read the list. Large autocomplete systems do exactly this, trading memory and slower inserts for instant reads.
⚡ Advanced — charts that change while you read them
Plays keep arriving. Rather than rebuild the heap, push the updated (-plays, title)
entry and discard stale ones as they surface — the lazy-deletion trick from the heaps
lesson.
🎯 Your turn
Write discovery_feed(genres, tracks, favorite, prefix, k). Use the genre tree to find
favorite and every genre beneath it, a trie to find their titles starting with
prefix, and a heap to return the k most-played, ties alphabetical. With
genres = ["Music", "Rock", "Electronic", "Punk", "Metal", None, "House"] and
tracks = [["nebula", "Metal", 240], ["needle drop", "Punk", 95], ["glasshouse", "Rock", 500], ["neon rain", "House", 120]]:
discovery_feed(genres, tracks, "Rock", "ne", 2)→["nebula", "needle drop"]discovery_feed(genres, tracks, "Jazz", "", 3)→[]
Hint — three stages, in order: names(find(build(genres), favorite)), then a trie
of the allowed titles walked down prefix, then (-plays, title) pairs on a heap.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = the discovery feed is live, and this part of Tunebox is complete. ✅