Heaps & Top-K

Spotify's coding loop concentrates its hard tail in one place: Find a Premium question, with Sliding Window Median right behind it. A Premium question comes up often enough to make heaps a favorite rather than a tail risk. That fits the product. Every ranked surface Spotify ships, Discover Weekly, autoplay, search results, the Home shelves, spends its day answering one question: what are the top items right now? The catalog and event stream behind that question never stop moving, and the question itself is a heap.

There is no Spotify heap trick here. This is the same data-structures bar everyone drills, told in track-and-playlist language. A Premium question is Kth Largest. Spacing artists apart in a generated queue is a Premium question. Learn the underlying patterns cold and the product story decodes itself. This loop does weight one thing more than most. Interviewers reward a clean, well-named, narrated medium over a faster but messier optimal, and they watch whether you test your own code. Say the complexity trade-off out loud and drop a couple of assertions at the end. Both move the score.

The Spotify angle

When K is much smaller than N, keep a heap of size K, not the whole input. Spotify's recommendation system, BaRT (Bandits for Recommendations as Treatments), scores a large candidate pool to build Discover Weekly and the Home shelves, then surfaces only the top handful, roughly thirty tracks on a playlist. To pull the top K out of a million scored candidates, a full sort is O(N log N) and throws away almost everything it computed. A min-heap capped at K scans once, evicting the smallest whenever it overflows, and lands at O(N log K) time with O(K) memory. When K is thirty and N is a million, that gap is the difference between a passing answer and an optimal one. Name the trade-off before you are asked. It costs one sentence and it is the optimization a ranking-shaped problem is built around.