Dedupe Homepage Shelves
NetflixPhone screenMedium
A streaming home page shows shelves from top to bottom, and each shelf is an ordered list of title ids. Implement dedupe_shelves(shelves, viewport, exempt), which returns the cleaned shelves in the same order, keeping the surviving titles of each shelf in their original relative order.
Within every shelf a title appears at most once: a later copy of a title already in that same shelf is dropped.
The exempt argument lists shelf indices; how those shelves are treated is described in each part.
Part 1: Window by position
In each shelf, look at the original positions 0 to viewport - 1; call these titles the window. A window title is dropped if an earlier shelf's window kept the same title; otherwise it is kept and marked as shown. Titles at positions viewport and beyond are never compared with other shelves.
Dropping a title does not shift the later titles: the window is fixed by original positions, so it never slides.
In this part exempt is empty, so every shelf follows the rule above.
- Example 1
- exempt
[]- shelves
[[1,2,3],[2,4,3],[3,5,6]]- viewport
2- Output
[[1,2,3],[4,3],[3,5,6]]
Why: Shelf 0's window keeps and marks 1 and 2. In shelf 1 the window is positions 0 and 1: 2 is already marked, so it is dropped, and 4 is kept. Title 3 sits at position 2, outside the window, so shelf 1 keeps it. Shelf 2's window starts with 3, which no earlier window kept, so shelf 2 is unchanged.
Constraints
1 <= len(shelves) <= 10^30 <= len(shelves[i]) <= 10^30 <= viewport <= 10^31 <= shelves[i][j] <= 10^9sum(len(shelf) for shelf in shelves) <= 10^5