Spotify Software Engineer Phone Screen Questions

have phone screen for backend engineer role coming up. Anyone who has interviewed at Spotify have any tips/advice on how to prep?

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