Support String Membership and Random Sampling

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.