Movie Playlist With Live Score Updates and No Repeats per Loop, Plus Thread Safety

Design and implement an in-memory movie playlist. Every movie has a numeric score, and scores can be updated at any time. The playlist hands out movies one at a time: - Each call to `get()` returns one movie. - Within one pass over the catalog (a loop), a movie is returned at most once. - Once every movie has been returned in the current loop, the next `get()` starts a new loop, in which every movie is available again. Assume that `get()` returns the highest-scoring movie not yet returned in the current loop, so scores decide the order inside each loop. Score updates must be supported efficiently, and they can arrive in the middle of a loop. After the core implementation, the interviewer adds a multi-threading follow-up. ### Constraints and Clarifications - The whole catalog fits in memory on one machine, and movie ids are unique. - Assume that `update_score(movie_id, score)` also adds a movie the first time it sees its id. - No sizes are given. State the complexity of each operation in terms of the catalog size. ### Clarifying Questions - When two movies still available in this loop have the same score, which one comes first? - If a movie not yet returned in this loop gets a new score, does the new score change its position in the current loop immediately? - If a movie already returned in this loop gets a new score, does the change only affect the next loop? - If a new movie is added in the middle of a loop, is it available in the current loop or only from the next one? - What should `get()` return when the playlist is empty? ### Part 1 — Playlist with score updates Implement `update_score(movie_id, score)` and `get()` with the rules above, and state the time and space complexity of both, including the cost of starting a new loop. ```hint Separate state for the loop Ask which movies `get()` may choose from at any moment, and what has to happen to all the other movies when the loop rolls over. ``` ```hint Updates and priority queues A binary heap cannot change the priority of an entry in place. Decide what to do with an entry whose score has become out of date. ``` #### What This Part Should Cover - Data structures that support highest-score retrieval, arbitrary score changes and loop rollover together - Explicit semantics for ties and for updates in the middle of a loop - Time and space complexity per operation, including rollover ### Part 2 — Multi-threading Several threads now call `get()` and `update_score()` concurrently. Where do you add locks, and what guarantees must hold? ```hint Compound operations List every step `get()` performs on shared state. Ask which of those steps must happen together so that no movie can be served twice in one loop. ``` #### What This Part Should Cover - Which operations are read-modify-write and must be atomic, including rollover - Lock granularity and its effect on correctness and throughput - How update threads and `get()` threads interact ### What a Strong Answer Covers - Working code for both operations, finished early enough to leave time for tests - Clear semantics for ties, mid-loop updates and rollover - Correct complexity, with no full re-sort on each call - Edge cases tested: an empty playlist, a single movie, updates to served and unserved movies - Concurrency reasoning grounded in the actual shared state, not just "add a lock" ### Follow-up Questions - How would you support removing a movie in the middle of a loop? - How would you prove in tests that no movie repeats within a loop, including under concurrent calls? - If each user needs their own loop over a shared scored catalog, how does the design change? - If score updates vastly outnumber `get()` calls, would you change the data structures?