## Reason About a Movie Billboard Rotation Component An interview exercise concerns a movie billboard rotation component. The retained description says not to use a heap and points toward two ordered maps, followed by questions about multithreading and production-scale storage. It does not preserve the method signatures, record fields, rotation policy, or examples. Do not invent those as observed facts. Begin by recovering the missing contract, then show how your design would follow from the contract the interviewer supplies. ### Part 1 — Recover the Executable Contract Identify the questions that must be answered before implementation: what state a movie carries, which mutations exist, what one selection call returns, how rotation changes state, and how ties and invalid requests behave. #### What This Part Should Cover - Stable movie identity and every operation that can add, update, remove, or select a movie. - The exact selection and rotation rule, including deterministic ties. - Whether repeated selections, temporarily ineligible movies, or empty state are meaningful under the supplied contract. - Return values and failure behavior precise enough to turn examples into tests. ```hint Find the state transition The useful contract is not merely which movie is returned; it must also say what changes before the next call. ``` ### Part 2 — Use Two Ordered Maps without a Heap Once the contract is known, define the two orderings the implementation needs. Specify each ordered map's key and value, how duplicate keys are represented, and how every mutation keeps the two views consistent. #### What This Part Should Cover - Keys derived from the actual selection and transition rules rather than guessed field names. - Ordered buckets or composite keys for deterministic ties. - One atomic update path that removes stale keys before inserting replacement keys. - Complexity for selection and each supported mutation in terms of live movies. ```hint Name both orderings Two ordered maps are useful only when each answers a distinct ordered lookup required by the clarified rotation policy. ``` ### Part 3 — Make the Component Thread-Safe Explain how concurrent selection and mutation calls become linearizable without exposing a movie in one ordered view but not the other. #### What This Part Should Cover - A linearization point for a selection that also changes rotation state. - A simple lock boundary or another synchronization strategy protecting both maps. - Safe reads, cancellation or interruption, and failure before a two-map update completes. - Tests for two callers selecting or updating the same logical movie concurrently. ```hint Protect the invariant, not one container Locking each map independently can still expose a state that never existed as one valid rotation snapshot. ``` ### Part 4 — Scale and Persist It Describe how the in-memory design would change for production: choose an authoritative storage model, partitioning boundary, cache strategy, and recovery path while preserving the clarified rotation invariant. #### What This Part Should Cover - Durable movie and rotation state with versioned or transactional updates. - A partition key that keeps one ordering invariant under a single owner when possible. - Idempotent commands, cache rebuild, and reconciliation after partial failure. - Explicit trade-offs if global ordering prevents independent horizontal partitions. ```hint Preserve one owner for the next choice Partitioning is safe only when two workers cannot independently select from the same logical rotation state. ``` ### What a Strong Answer Covers - Refuses to fabricate the missing API or rotation rule. - Derives both ordered-map keys and invariants from the clarified contract. - Makes two-map changes atomic under concurrency. - Explains how persistence and partitioning preserve the same selection semantics. ### Follow-up Questions 1. Which contract choices determine whether a shorter or more complex data structure is sufficient? 2. How would you represent many movies with the same ordering key? 3. Where is the linearization point when selecting a movie changes its future position? 4. What production requirement would make a single global ordered index unacceptable?