## Support String Membership and Random Sampling Design an in-memory collection initialized from a set of strings. It must support: - `contains(value) -> bool`: report whether an exact string is present. - `get_random() -> str`: return one stored string, with every stored string equally likely. For this practice version, strings are unique after initialization and the collection is immutable. Explain the implementation, complexity, and how your choice compares with a trie-based design. ### Constraints & Assumptions - The collection contains at least one string. - Exact membership is required; prefix membership is not. - Total input size may be large enough that both string storage and indexing overhead matter. - Random sampling must be uniform across stored strings. ### Clarifying Questions to Ask - Are duplicates possible, and if so, should sampling be uniform by distinct value or occurrence? - Will insertions or deletions be added later? - Are prefix queries expected in a future version? - Is a standard pseudorandom generator acceptable? ### Hints - Membership and uniform positional sampling favor different access patterns. - Avoid an implementation that must traverse the entire collection for every random sample. - When comparing a trie, distinguish exact lookup benefits from prefix-specific benefits. ### What a Strong Answer Covers - Correct exact-membership and uniform-sampling semantics. - Build time, per-operation time, and memory complexity. - A clear explanation of why the data structures complement each other. - Tradeoffs of a trie for shared prefixes, alphabet representation, and random sampling. - How mutability or duplicate-weighted sampling would change the design. ### Follow-up Questions - How would you support `insert` and `remove` while preserving uniform sampling? - How would sampling change if each string had a weight? - When could a compressed trie use less memory than storing full strings in a hash table? - How would you make random behavior reproducible in a unit test?