Quick Overview

This question evaluates algorithmic problem-solving and state management for streaming deduplication with order preservation, testing competencies in data structures, deterministic filtering, and handling constrained visibility windows.

Dedupe titles in per-shelf viewport

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are rendering a streaming app home page. - The home page consists of **shelves** displayed from top to bottom. - Each shelf contains a list of `titleId` values (integers). - Each shelf’s horizontal viewport can show at most **X** titles. - Assume the vertical viewport is unlimited (i.e., you process shelves in order, top to bottom). Implement a function that **filters titles while preserving order** under the following deduplication rules: 1. **Global dedupe within the visible region:** - While building the **first `X` output titles** for a shelf, you must **skip** any `titleId` that has already appeared in the **visible region** (first `X` output titles) of any earlier shelf. 2. **Local dedupe after the visible region:** - After a shelf has already produced `X` output titles, continue outputting additional titles from that shelf, but now **only dedupe within the same shelf** (i.e., skip repeats that have already been output in this shelf). - Global deduplication no longer applies past position `X` within a shelf. ### Function signature - Input: `shelves: List[List[int]]`, `X: int` - Output: `List[List[int]]` (the filtered shelves) ### Notes - Preserve the original relative order of titles within each shelf. - If a shelf has fewer than `X` eligible titles (after global dedupe), it may output fewer than `X` titles. ### Example If `X = 2` and shelves are: - Shelf 1: `[1, 2, 1, 3]` - Shelf 2: `[2, 4, 2, 5]` Then: - Shelf 1 visible region (first 2 outputs) becomes `[1, 2]` (global seen = `{1,2}`), then locally can output `3` (skipping the repeated `1`). - Shelf 2 visible region cannot use `2` (already globally visible), so it outputs `[4, 2]` as its first 2 outputs (4 is new globally visible; once the shelf has hit `X` outputs, `2` is allowed even though it was globally visible). After that it can output `5`. So the output is `[[1, 2, 3], [4, 2, 5]]`. Specify and implement the algorithm.

Quick Answer: This question evaluates algorithmic problem-solving and state management for streaming deduplication with order preservation, testing competencies in data structures, deterministic filtering, and handling constrained visibility windows.

You are rendering a streaming app home page. - The home page consists of **shelves** displayed from top to bottom. - Each shelf contains a list of integer `titleId` values. - Each shelf has a horizontal viewport that can show at most **X** titles. - The vertical viewport is unlimited (process shelves in order, top to bottom). You must **filter titles while preserving order** using these rules: ### Definitions - For each shelf, the **viewport window** is the first **X positions of the original shelf list** (indices `0..X-1`). - Important: even if filtering removes items, you **do not** extend the viewport window to pull in more items for global dedupe purposes. ### Deduplication rules 1. **Global dedupe inside the viewport window (raw first X positions):** - When processing an item whose original index `i < X`, you must **skip it** if its `titleId` has already been output from the viewport window of any **earlier shelf**. - If you do output it from within the viewport window, it becomes globally visible and affects later shelves. 2. **Local dedupe everywhere (entire shelf):** - Regardless of index, a shelf must never output the same `titleId` twice. 3. **No global dedupe beyond the viewport window:** - For items with original index `i >= X`, **global dedupe does not apply** (but local dedupe still does). This means a title skipped in the viewport window due to global dedupe may still appear later in the same shelf if it appears again beyond the first X positions. Return the filtered shelves.

Constraints

  • 0 <= X <= 10^5
  • 0 <= number of shelves <= 10^5 (practical limits depend on total titles)
  • 0 <= total number of title IDs across all shelves <= 2 * 10^5
  • titleId values fit in 32-bit signed integers
  • Must preserve relative order of remaining titles within each shelf

Examples

Input: ([[1, 2, 1, 3], [2, 4, 2, 5]], 2)

Expected Output: [[1, 2, 3], [4, 2, 5]]

Explanation: Shelf1 viewport window indices 0..1 outputs 1,2 => globally visible {1,2}. Later in shelf1, only local dedupe applies so 3 is kept. Shelf2 index0=2 is globally visible so skipped; index1=4 kept and becomes globally visible; index2=2 is beyond viewport window so global dedupe no longer applies and 2 can be output (locally unique).

Input: ([[1, 1, 2, 1], [1, 3, 1, 4]], 2)

Expected Output: [[1, 2], [3, 1, 4]]

Explanation: Shelf1 viewport window [1,1] outputs only one 1 (local dedupe), making {1} globally visible; later 2 is kept. Shelf2 viewport index0=1 skipped globally; index1=3 kept (global add 3); beyond viewport, 1 is allowed and then 4.

Loading coding console...