Katkat
Back

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

NetflixSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Implement an in-memory movie playlist in which get returns the highest-scoring movie not yet served in the current loop, starting a new loop once every movie has been served, while scores can change at any time. A follow-up asks where to add locks when many threads call it concurrently.

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.

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?

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

Hints

Hint 1

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 2

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.

Hint 3

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.

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?