# Design an Expected O(1) Randomized Container Design a generic container that stores distinct elements and supports: - `insert(element) -> bool`: add an element if absent and report whether insertion occurred. - `pop_random() -> element`: remove and return one currently stored element, with every stored element having equal probability. Raise a documented empty-container error when no element exists. Both operations should take expected `O(1)` time. Explain the representation, update invariants, randomness requirement, and tests. You may assume stored elements are hashable. ### Constraints & Assumptions - Duplicate elements are not stored. - The random generator can choose a uniformly distributed integer index. - Preserving insertion order is not required. - Thread safety is not required initially, but should be discussed as a follow-up. ### Clarifying Questions to Ask - Are duplicates rejected or counted as separate occurrences? - What exception or return value represents an empty pop? - Is reproducible seeded randomness needed for tests? - Must concurrent callers be supported? ### What a Strong Answer Covers - A dense array plus an element-to-index map - Swap-with-last removal and every required index update - Expected-time and memory analysis - Uniformity, deterministic testing seams, and empty-state behavior - Clear invariants and edge cases such as removing the last element ### Follow-up Questions - How would the design change if duplicates were allowed? - How would you support weighted random removal? - What synchronization would make operations linearizable? - How would you test distribution quality without flaky assertions?