## Prompt Design an in-memory class with `store(item)` and `retrieve(now)` operations. Items have a unique ID, weight, size, and expiration timestamp. Storage is divided into ordered levels. Retrieval examines levels from highest to lowest, ignores expired items, considers only a level whose remaining capacity is at least 50% of that level's total capacity, and removes the highest-weight eligible item from the first eligible level. Specify initialization, placement, tie-breaking, and the data structures you would implement. ### Constraints & Assumptions - Level order and capacity are fixed at initialization. - Expiration is inclusive: an item with `expires_at <= now` is unavailable. - If two eligible items have equal weight, return the one stored earlier, then break any remaining tie by item ID. - A failed store or retrieve must leave the data structure consistent. ### Clarifying Questions to Ask - Does the 50% rule refer to free capacity before or after retrieval? State and use one interpretation consistently. - May an item be updated under an existing ID, or must duplicate IDs be rejected? - Should expired items be reclaimed eagerly, lazily, or by a background process? ```hint Separate selection from cleanup A weight heap answers one ordering question, while expiration answers another. Consider how stale heap entries can be recognized without corrupting capacity accounting. ``` ```hint Make the threshold observable Track used bytes per level explicitly so the 50% eligibility rule does not require scanning every item. ``` ### What a Strong Answer Covers - A precise class API and invariants for capacity, uniqueness, expiration, and level priority. - A placement policy for `store` and deterministic selection for `retrieve`. - Data structures that support weight priority without losing expiration correctness. - Complexity for both operations and an explanation of lazy-deletion cleanup. - Tests for threshold boundaries, expired heavy items, ties, full levels, and repeated retrieval. ### Follow-up Questions 1. How would you make `store` and `retrieve` safe under concurrent callers? 2. How would the design change if levels contain millions of items and expiration cleanup must be bounded per request? 3. What metrics would reveal that one level is chronically skipped by the 50% rule?