Design a Phone Directory (Linked List/Array)

To design this directory, I first need to understand if the number range is fixed and dense, like local area codes, or highly sparse across global prefixes. If we assume a standard scenario where numbers are sparse, a simple array would waste massive amounts of memory storing nulls. Instead, I recommend using a Hash Set combined with a Doubly Linked List. The Hash Set allows us to track reserved numbers with O(1) average time complexity for both reservation and release checks. However, to efficiently find an available number when a user wants one, the Doubly Linked List can maintain all currently free numbers in a contiguous chain. When reserving, we remove the head of the list from the set and return it. When releasing, we add the number back to the head of the list and the set. This approach ensures that finding a new number is O(1), which aligns with Stripe's focus on high-throughput payment processing systems where latency must be minimized. If the range were small and dense, say 0-9999, an array with a pointer to the next free slot would be more efficient, reducing space to exactly N bits. For this implementation, I will proceed with the Hash Set and Linked List combination as it scales better for real-world scenarios where most numbers remain unassigned.