Design a Phone Directory (Set/Trie)

To design this phone directory efficiently, I first clarify that we need O(1) performance for checking existence and reserving numbers, as Stripe values low-latency APIs. A simple array would require linear scanning, which fails at scale. Instead, I propose using a Hash Set for storing available numbers. This allows us to check existence in constant time. For the reserve operation, we remove the number from the set; for release, we add it back. Both operations remain O(1). If the problem implies we need to validate prefixes or find available numbers within a range, a Trie becomes superior because it compresses shared prefixes, saving space compared to a flat hash set. However, for standard reservation, the Hash Set is more intuitive and faster. I would also consider handling integer overflow if numbers are stored as integers rather than strings. In terms of concurrency, since Stripe handles financial transactions, I'd suggest using atomic operations or locks to prevent race conditions where two users try to reserve the same number simultaneously. Finally, I'd implement a cleanup mechanism to handle stale entries if the system runs for extended periods, ensuring memory usage stays bounded while maintaining the core O(1) guarantees for the primary user actions.