Design Phone Directory — Available Number Pool Management

Problem Statement#

Design a phone directory that manages maxNumbers phone numbers. Implement three operations: get() provides an available number and returns -1 if none; check(number) returns whether a number is available; release(number) recycles a number back to the pool.

Constraints:

• 1 <= maxNumbers <= 10^4
• 0 <= number < maxNumbers
• At most 2 * 10^4 calls total to get, check, and release

Input:  maxNumbers=3, get(), get(), check(2), get(), check(2), release(2), check(2)
Output: 0, 1, true, 2, false, —, true

Input:  maxNumbers=1, get(), get()
Output: 0, -1

Why This Problem Matters#

Resource pool management is a fundamental pattern in systems programming. Database connection pools, thread pools, IP address allocation (DHCP), and memory allocators all implement the same core abstraction: a finite pool of identifiers that can be acquired and released. Understanding this design is essential for senior engineering interviews at Amazon AWS (where EC2 instance ID allocation uses similar logic) and Google Cloud.

In FAANG interviews, this problem tests whether you can design a bounded resource allocator with O(1) operations. Naive approaches using sorted sets or linear scans fail to achieve the required constant-time guarantees. The queue-plus-boolean-array design is the canonical solution.

This same pattern appears in operating system process ID allocation, port number assignment in network stacks, and UUID pool management in distributed systems.

The Core Insight#

Maintain two data structures: a queue of available numbers (initialised with all numbers 0 to maxNumbers-1) and a boolean array used[] to track allocation status. get() dequeues from the free queue and marks the number as used. check(n) simply reads used[n]. release(n) marks the number as free and enqueues it.

All three operations are O(1). The queue ensures fair FIFO allocation—numbers are reused in the order they were released, which is important for audit trails and debugging. The boolean array provides O(1) availability checks without scanning the queue.

A HashSet alternative uses O(N) average for all operations but avoids the fixed-size array limitation. Use the queue-plus-array approach when the number space is bounded and known in advance.

Visual Dry Run#

Solution (Optimal)#

from collections import deque
 
class PhoneDirectory:
    def __init__(self, maxNumbers: int):
        self.available = deque(range(maxNumbers))
        self.in_use = set()
 
    def get(self) -> int:
        if not self.available:
            return -1
        num = self.available.popleft()
        self.in_use.add(num)
        return num
 
    def check(self, number: int) -> bool:
        return number not in self.in_use
 
    def release(self, number: int) -> None:
        if number in self.in_use:
            self.in_use.remove(number)
            self.available.append(number)

class PhoneDirectory {
    constructor(maxNumbers) {
        this.queue = [];
        this.used = new Array(maxNumbers).fill(false);
        for (let i = 0; i < maxNumbers; i++) this.queue.push(i);
        this.head = 0;
    }
 
    get() {
        if (this.head >= this.queue.length) return -1;
        const num = this.queue[this.head++];
        this.used[num] = true;
        return num;
    }
 
    check(n) {
        return !this.used[n];
    }
 
    release(n) {
        if (this.used[n]) {
            this.used[n] = false;
            this.queue.push(n);
        }
    }
}

Time: O(1) for all three operations
Space: O(N) — queue and boolean array each of size maxNumbers

Common Mistakes#

• Not checking if number in self.in_use before releasing—releasing a free number should be a no-op, not add it twice to the queue
• Using a list with pop(0) instead of a deque—O(N) per get due to list shifting
• Forgetting to guard release against double-release—without the guard, the same number appears twice in the queue and can be returned by two consecutive get() calls
• Not initialising all numbers in the queue at startup—leaving some numbers permanently unavailable
• Using in self.available to check a deque which is O(N)—use the boolean array or set for O(1) availability checks

Interview Tips#

• Explain the two components clearly: queue for ordering/allocation, boolean array for O(1) availability lookup
• Mention the connection pool analogy: this is exactly how database drivers like JDBC manage connection availability
• Discuss the double-release protection: in production systems, releasing a resource you do not own is a serious bug and must be guarded
• For the follow-up about concurrency, mention synchronized blocks in Java or asyncio.Lock in Python to protect the queue and array together

Follow-up Questions#

• How would you handle concurrent get() calls from multiple threads? (Lock the queue-and-array pair atomically; use ReentrantLock in Java or asyncio.Lock in Python)
• What if numbers could have priority levels—allocate low numbers first? (Use a min-heap instead of a queue)
• How would you support returning the current allocation count in O(1)? (Maintain a counter variable incremented on get and decremented on release)
• How would you handle automatic reclamation of numbers not released after a timeout? (Store allocation timestamp; background thread reclaims expired numbers)
• How does this scale to a billion phone numbers in a distributed system? (Shard the number space across nodes; each node owns a range and manages its own pool)

Key Takeaways#

• A deque (queue) of free numbers plus a boolean availability array gives O(1) get, check, and release
• Always guard release against double-release: only re-enqueue if the number was actually in use
• Use deque.popleft() not list.pop(0)—the latter is O(N) due to list element shifting
• This pattern is used verbatim for connection pool management, DHCP IP allocation, and OS process ID allocation
• The queue ensures FIFO reuse ordering; a min-heap can replace it if lowest-numbered-first allocation is needed
• check(n) should use the boolean array or set for O(1) lookup, not scan the queue
• The space complexity is O(maxNumbers) regardless of how many numbers are currently allocated