Problem Description

You need to design a phone directory system that manages a pool of phone numbers. The directory starts with a fixed number of available slots (from 0 to maxNumbers - 1), and you need to implement operations to allocate, check availability, and release phone numbers.

The PhoneDirectory class should support the following operations:

1. Constructor PhoneDirectory(int maxNumbers): Initialize the directory with maxNumbers available slots. Initially, all numbers from 0 to maxNumbers - 1 are available for allocation.

2. Get a number get(): Allocate and return any available phone number. Once a number is allocated, it becomes unavailable. If no numbers are available, return -1.

3. Check availability check(int number): Check if a specific phone number is currently available (not allocated). Return true if the number is available, false if it's already allocated.

4. Release a number release(int number): Return a previously allocated phone number back to the pool of available numbers, making it available for future allocation again.

The solution uses a hash set to track all available phone numbers. Initially, the set contains all numbers from 0 to maxNumbers - 1. When get() is called, it removes and returns any number from the set (or -1 if empty). The check() method simply verifies if a number exists in the set. The release() method adds a number back to the available set. All operations run in O(1) time complexity.

Intuition

The key insight is recognizing that we need to efficiently track which phone numbers are available versus allocated. This is fundamentally a problem of managing two distinct sets - available numbers and allocated numbers.

Since we start with all numbers available and only need to know which ones are free at any point, we can maintain just one set containing the available numbers. Why a set? Because we need fast operations for:

• Removing an arbitrary element when allocating (get)
• Checking membership when verifying availability (check)
• Adding elements back when releasing (release)

A hash set gives us O(1) time complexity for all these operations.

The beauty of using set(range(maxNumbers)) for initialization is that it immediately gives us all valid phone numbers. When we call get(), we can use pop() to both retrieve and remove any available number in one operation - we don't care which specific number we give out, just that it's available.

For check(), it's a simple membership test - if the number is in our available set, it hasn't been allocated yet. And release() just adds the number back to our available pool.

This approach avoids the complexity of tracking allocated numbers separately or maintaining any ordering. We let the set data structure handle the heavy lifting of efficient storage and lookup, while our logic remains simple: available numbers live in the set, allocated numbers don't.

Solution Approach

We implement the phone directory using a hash set called available to store all unallocated phone numbers.

Initialization (__init__):

self.available = set(range(maxNumbers))

We create a set containing all numbers from 0 to maxNumbers - 1. This represents our initial pool of available phone numbers. Using set(range(maxNumbers)) efficiently generates and stores all valid phone numbers.

Getting a number (get):

def get(self) -> int:
    if not self.available:
        return -1
    return self.available.pop()

First, we check if the set is empty. If it is, no numbers are available, so we return -1. Otherwise, we use pop() to remove and return an arbitrary element from the set. The pop() operation on a set removes and returns any element in O(1) time - we don't need to care which specific number is returned, just that it's available.

Checking availability (check):

def check(self, number: int) -> bool:
    return number in self.available

This is a straightforward membership test. We simply check if the given number exists in our available set. If it's present, the number hasn't been allocated yet and is available. The in operator on a hash set runs in O(1) time.

Releasing a number (release):

def release(self, number: int) -> None:
    self.available.add(number)

When a phone number is released, we add it back to the available set using the add() method. This makes the number available for future allocation. The add() operation on a hash set also runs in O(1) time.

All operations achieve O(1) time complexity, making this solution highly efficient. The space complexity is O(n) where n is maxNumbers, as we need to store up to maxNumbers elements in our set.

Example Walkthrough

Let's walk through a small example with maxNumbers = 3, which gives us phone numbers 0, 1, and 2.

Step 1: Initialize the directory

directory = PhoneDirectory(3)
# available = {0, 1, 2}

All three numbers are initially available in our set.

Step 2: Get a phone number

number1 = directory.get()  # Returns 2 (could be any of 0, 1, or 2)
# available = {0, 1}

The pop() method removes and returns an arbitrary element. Let's say it returns 2. Now only 0 and 1 remain available.

Step 3: Check if number 2 is available

directory.check(2)  # Returns False
# available = {0, 1} (unchanged)

Since we just allocated number 2, it's not in the available set anymore, so check(2) returns False.

Step 4: Get another number

number2 = directory.get()  # Returns 1
# available = {0}

We allocate another number. Let's say it returns 1. Only number 0 remains.

Step 5: Release number 2 back to the pool

directory.release(2)
# available = {0, 2}

Number 2 is added back to the available set and can be allocated again.

Step 6: Check availability

directory.check(2)  # Returns True
directory.check(1)  # Returns False
directory.check(0)  # Returns True

Number 2 is available (we just released it), number 1 is still allocated, and number 0 was never allocated.

Step 7: Get remaining numbers

directory.get()  # Returns 2
directory.get()  # Returns 0
directory.get()  # Returns -1 (no numbers left)
# available = {} (empty set)

After allocating the last two available numbers, the set becomes empty. Any subsequent get() calls return -1 to indicate no numbers are available.

This example demonstrates how the hash set efficiently tracks available numbers, removing them when allocated and adding them back when released.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(maxNumbers): O(n) where n is the value of maxNumbers, as we need to create a set containing all numbers from 0 to maxNumbers - 1.
• get(): O(1) on average. The pop() operation on a set has average case O(1) time complexity.
• check(number): O(1) on average. Checking membership in a set is an O(1) average case operation.
• release(number): O(1) on average. Adding an element to a set is an O(1) average case operation.

Space Complexity: O(n) where n is the value of maxNumbers. The primary space usage comes from the self.available set, which in the worst case (when all numbers are available) stores n integers from 0 to maxNumbers - 1. This dominates the space complexity of the entire data structure.

Common Pitfalls

1. Not Handling Invalid Release Operations

The current implementation doesn't validate whether a number being released was actually allocated before. This can lead to incorrect behavior where:

• Releasing a number that was never allocated (e.g., releasing number 100 when maxNumbers is 50)
• Releasing the same number multiple times
• Having duplicate numbers in the available pool

Example of the problem:

directory = PhoneDirectory(3)  # Numbers 0, 1, 2 available
num = directory.get()  # Get number 2 (for example)
directory.release(2)   # Release it back
directory.release(2)   # Release again - no error but creates duplicate
directory.release(5)   # Release invalid number - adds number outside range

Solution: Add validation to ensure only valid, previously allocated numbers can be released:

def __init__(self, max_numbers: int) -> None:
    self.available = set(range(max_numbers))
    self.max_numbers = max_numbers  # Store the maximum limit

def release(self, number: int) -> None:
    # Validate the number is within valid range
    if 0 <= number < self.max_numbers:
        # Only add if not already available (prevents duplicates)
        self.available.add(number)

2. Thread Safety Issues in Concurrent Environments

The current implementation is not thread-safe. If multiple threads access the PhoneDirectory simultaneously, race conditions can occur:

• Two threads calling get() might receive the same number
• A thread checking availability while another is allocating might get inconsistent results

Solution: Use threading locks to ensure atomic operations:

import threading

def __init__(self, max_numbers: int) -> None:
    self.available = set(range(max_numbers))
    self.lock = threading.Lock()

def get(self) -> int:
    with self.lock:
        if not self.available:
            return -1
        return self.available.pop()

def check(self, number: int) -> bool:
    with self.lock:
        return number in self.available

def release(self, number: int) -> None:
    with self.lock:
        self.available.add(number)

3. Memory Inefficiency for Large Number Ranges

When maxNumbers is very large (e.g., 10 million), storing all available numbers in a set consumes significant memory even when most numbers are allocated.

Alternative Solution for Large Ranges: Use a set to track only allocated numbers instead of available ones:

def __init__(self, max_numbers: int) -> None:
    self.allocated = set()
    self.max_numbers = max_numbers
    self.next_available = 0  # Track next number to try

def get(self) -> int:
    if len(self.allocated) >= self.max_numbers:
        return -1
  
    # Find next available number
    while self.next_available in self.allocated:
        self.next_available += 1
        if self.next_available >= self.max_numbers:
            # Wrap around and search from beginning
            for i in range(self.max_numbers):
                if i not in self.allocated:
                    self.allocated.add(i)
                    return i
            return -1
  
    num = self.next_available
    self.allocated.add(num)
    return num

def check(self, number: int) -> bool:
    return 0 <= number < self.max_numbers and number not in self.allocated

def release(self, number: int) -> None:
    if number in self.allocated:
        self.allocated.remove(number)
        self.next_available = min(self.next_available, number)

This approach uses less memory when most numbers are allocated, as it only tracks the allocated set rather than the available set.