## Design Prefix-Aware Deduplication for Homepage Content Rows A homepage contains ordered rows of content IDs. Each row has its own ordered candidate list. For a participating row, content placed in its protected prefix must not appear in the protected prefix of any other participating row. Once that prefix is full, the remaining positions only need to be unique within that row. Design an algorithm that constructs the displayed rows while preserving candidate rank as much as the deduplication rules allow. Then extend it to support a different protected-prefix length for every row and rows that are exempt from global deduplication. ### Constraints & Assumptions - Content identity is determined by a stable content ID, not by title text. - Candidate lists may contain repeated IDs, including repeats within one row. - The row processing order is deterministic and supplied by the caller. - A row may have too few eligible candidates to fill its requested prefix or total display size. If the protected prefix cannot be filled, stop that row at the shorter prefix and expose the shortfall; tail construction must not begin while any protected-prefix position remains unfilled. - Clarify whether an exempt row neither checks nor reserves global IDs, or whether the exemption is one-sided. ### Clarifying Questions to Ask - Does global uniqueness apply only among protected prefixes, or may a prefix item repeat later in another row's tail? - Is preserving each row's candidate order more important than maximizing how many prefixes can be filled? - Is row order an intentional priority rule, or should the algorithm optimize across all rows at once? - When a candidate is rejected from a prefix only because it was used globally, may it be reconsidered for that row's tail? ### Part 1 — Enforce One Shared Prefix Length Describe the state you maintain while constructing rows and how you select the first `n` positions and the remaining positions without duplicating an ID within a row. #### What This Part Should Cover - Separate row-local and global-prefix membership checks. - Deterministic handling of candidates rejected from the protected prefix. - Behavior when a prefix cannot be filled. - Time and space complexity in terms of the candidates examined. ```hint Separate the two scopes An ID can be forbidden for a protected position because another row reserved it while still being eligible for an unprotected position in the current row. ``` ### Part 2 — Support a Different Prefix Length per Row Change the design so row `r` has its own prefix length `n[r]`. Explain whether this changes the core data structures or only the acceptance rule for each output position. #### What This Part Should Cover - Per-row configuration validation, including zero and values larger than the display size. - A single global-prefix set shared by all participating rows. - Deterministic results when an early row has a much larger prefix than later rows. ```hint Make the quota data-driven The global state can stay shared even though the position at which each row switches to local-only deduplication is different. ``` ### Part 3 — Exempt Selected Rows from Global Deduplication Add a row policy that disables global deduplication for selected rows. Define the semantics precisely and show how the policy affects both membership checks and updates to global state. #### What This Part Should Cover - Whether an exempt row can reuse globally reserved content. - Whether content in an exempt row reserves IDs against later participating rows. - Row-local uniqueness remaining mandatory for every row. - Tests that distinguish full exemption from a one-sided exemption. ```hint Treat exemption as a policy Use explicit check and reserve flags instead of scattering special-row conditionals through the selection loop. ``` ### What a Strong Answer Covers - A precise rule for which output positions participate in global deduplication. - Stable ordering, explicit shortfall behavior, and no silent insertion of duplicate IDs. - Clean extensions for per-row prefix lengths and exempt-row policy. - Complexity analysis and tests for overlapping rankings, repeated candidates, empty rows, and impossible quotas. ### Follow-up Questions 1. How would the result change if row order must not determine which row wins a globally duplicated item? 2. How would you update one row incrementally without rebuilding the whole page? 3. What metrics would reveal that global deduplication is leaving important rows underfilled? 4. How would you make the selection reproducible when candidate rankings update concurrently?