Spotify Software Engineer Onsite Coding Questions

LeetCode #346: Moving Average from Data Stream. Difficulty: Easy. Topics: Array, Design, Queue, Data Stream. Asked at Spotify in the last 6 months.

LeetCode #1152: Analyze User Website Visit Pattern. Difficulty: Medium. Topics: Array, Hash Table, String, Sorting. Asked at Spotify in the last 6 months.

LeetCode #295: Find Median from Data Stream. Difficulty: Hard. Topics: Two Pointers, Design, Sorting, Heap (Priority Queue), Data Stream. Asked at Spotify in the last 6 months.

LeetCode #20: Valid Parentheses. Difficulty: Easy. Topics: String, Stack. Asked at Spotify in the last 6 months.

## Problem You are given a list of play events `(user_id, song_id)`. For each user, return the top `k` most-played songs (by play count), breaking ties by `song_id` ascending. Return a dictionary mapping each user to their ranked list. ```python def top_songs( events: list[tuple[int, int]], # (user_id, song_id) k: int ) -> dict[int, list[int]]: pass ``` ``` Input: events = [(1,101),(1,102),(1,101),(2,200),(2,201),(2,200),(2,201),(2,201)] k = 2 Output: { 1: [101, 102], # 101 played 2x, 102 played 1x 2: [201, 200] # 201 played 3x, 200 played 2x } ``` ## Follow-ups 1. How would you use a heap to get top-k without fully sorting the song list per user? 2. If the event stream is very large (billions of entries), how would you compute this with a distributed map-reduce approach? 3. How would you handle a sliding window: top-k songs played in the last 7 days? 4. Extend: return songs where play count >= some threshold `t` instead of top-k.