Spotify Software Engineer Interview Questions

## Problem Given a string `s` and an integer `limit`, remove the minimum number of characters so that no character appears more than `limit` times consecutively. Return the resulting string. ```python def limit_consecutive_duplicates(s: str, limit: int) -> str: pass ``` ``` Input: s = "aaabbbcc", limit = 2 Output: "aabbcc" # 'a' appears 3x consecutively -> remove 1 -> 'aa' # 'b' appears 3x -> remove 1 -> 'bb' Input: s = "aaa", limit = 1 Output: "a" Input: s = "aabbcc", limit = 3 Output: "aabbcc" # already valid Input: s = "", limit = 2 Output: "" ``` ## Follow-ups 1. Is your solution a single pass? Prove it produces the minimum number of removals. 2. What is the time and space complexity? 3. Extend to limit the total (not just consecutive) occurrences of any character to `limit`. 4. If you cannot remove characters but can rearrange them, how would you solve the problem?

## Problem You have a collection of letter tiles (with repetition). Given a target word, determine the minimum number of additional letters you need to purchase (insert) so you can spell the word. Each tile can be used at most once. ```python def min_insertions_to_make_word(tiles: list[str], target: str) -> int: pass ``` ``` Input: tiles = ['a', 'a', 'b', 'c'], target = "aabbc" Output: 2 # Have: a=2, b=1, c=1. Need: a=2, b=2, c=1. # Missing: b=1. But also missing one 'b'. Wait: need b=2, have b=1 -> need 1 more b. # Answer = 1? Check: need a=2 (have 2 ok), b=2 (have 1, need 1 more), c=1 (have 1 ok) -> 1. # Let's use a cleaner example: Input: tiles = ['a', 'b'], target = "aab" Output: 1 # Have a=1,b=1. Need a=2,b=1. Missing: 1 'a'. ``` ## Follow-ups 1. What if tiles have costs and you want to minimize total cost, not count of inserted letters? 2. How do you handle case-insensitivity? 3. Extend: given multiple target words, find the minimum total insertions to spell all of them (tiles are shared). 4. What if tiles can be wildcards that match any letter?

## Problem You are given a list of song pairs `(a, b)` meaning song `a` was played immediately before song `b` in a playlist. Reconstruct the full playlist order. Assume the input forms a single valid sequence with no ambiguity. ```python def reconstruct_playlist(pairs: list[tuple[str, str]]) -> list[str]: pass ``` ``` Input: pairs = [("Shape of You", "Blinding Lights"), ("Blinding Lights", "Levitating"), ("Levitating", "Stay")] Output: ["Shape of You", "Blinding Lights", "Levitating", "Stay"] Input: pairs = [("B","C"), ("A","B"), ("C","D")] Output: ["A", "B", "C", "D"] ``` ## Follow-ups 1. How do you identify the starting song (the one that never appears as a "next" song)? 2. What if the pairs form a cycle — how would you detect and report that? 3. If some pairs are missing (gaps in the sequence), how do you handle discontinuous playlists? 4. Extend to reconstruct a sequence where each pair says song `a` played within 2 slots before `b` (not necessarily immediately before). How does the problem change?

## 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.