## Scenario Design an in-memory store with ordered storage levels. The class is initialized with each level's item capacity. `store(item)` places an item in a level, and `retrieve(now)` returns one eligible item. For this exercise, an item has `id`, positive `weight`, and `expiresAt`. A level is eligible for retrieval only when at least half of its item slots are currently occupied. Retrieval scans levels from top to bottom, ignores and removes expired items, and returns the heaviest unexpired item in the first eligible level. Break equal-weight ties by earlier expiration and then smaller item ID. If no item qualifies, return `null`. Explain the API, invariants, data structures, and error behavior. State a deterministic placement policy for `store`. ### Constraints & Assumptions - Use first-fit placement from the top level downward; reject a store when every level is full. - Expired items do not count toward occupancy after they are discovered. - Timestamps are supplied by the caller so tests do not depend on wall-clock time. - One item ID may exist at most once. ### Clarifying Questions to Ask - Is the fifty-percent threshold based on slots or weight? Slots. - Is expiration checked before level eligibility? Yes. - Does retrieval remove the item? Yes. - What should happen on duplicate IDs or full capacity? Return an explicit error without partial mutation. ```hint Make cleanup part of the operation Before testing a level's occupancy, remove items whose expiration is not later than `now`; otherwise an expired item can incorrectly make the level eligible. ``` ### What a Strong Answer Covers - Exact placement, expiration, occupancy, level-order, weight, and tie-break semantics. - Consistent indexes for ID lookup, expiration cleanup, and best-item selection. - Atomic mutation on store and retrieve, including duplicate and full errors. - Complexity and the trade-off between eager and lazy expiration. ### Follow-up Questions 1. How would you support concurrent stores and retrievals? 2. What changes if capacity is measured by total weight rather than item count? 3. How would you avoid long cleanup pauses after many items expire at once?