379. Design Phone Directory
Model: qwen3.5:9b
Topics: Linked List,Design
FAANG asked: 1
Acceptance rate: 48.4%
Problem Breakdown
We need to manage a pool of phone numbers from 0 to maxNumbers - 1. The system must support three operations: allocating an unused number (get), checking if a specific number is free (check), and freeing up a previously allocated number (release).
Key constraints are the maximum capacity () and the total number of calls (up to ). We need an efficient way to track availability. The tricky part is ensuring get returns any available slot quickly without scanning a large array every time, while maintaining fast lookups for check.
Intuition
A naive approach would be to use a boolean list where we scan from index 0 upwards until we find an empty slot (True) or reach the end.
- Naive Time Complexity: per
getcall because of scanning. With many calls, this leads to total time, which is too slow if (calls) and are large. - Optimization Insight: Since the order in which we return numbers doesn’t matter (“any available phone number”), we don’t need a specific queue structure like FIFO. We just need to know which slots exist as free resources. A Hash Set allows us to store all currently free numbers and perform lookups, insertions (release), and deletions (
get). - Key Insight: Maintain the state of “available” vs “occupied”. If we track available numbers in a set:
checkis simply checking membership.releaseadds to the set.getremoves from the set (and returns value).
Approach
- Initialization: Create a Python
setinitialized with all integers from tomaxNumbers - 1. This represents our pool of free slots. - Constructor (
__init__): Populate the set and store it as an instance variable. Time complexity is linear relative to capacity, which happens once at startup. - Method
get():- Check if the set is empty. If so, return
-1. - Otherwise, use
.pop(). This removes and returns a random element from the set in amortized time. We don’t need to track which specific number was returned for future logic other than its absence.
- Check if the set is empty. If so, return
- Method
check(number):- Return whether
numberis present in our available slots set usingin. This is .
- Return whether
- Method
release(number):- Add the number back to the set if it’s not already there (though logically, we assume valid inputs where only occupied numbers are released). Python sets handle duplicate additions gracefully by ignoring them, so a simple
.add()works perfectly for both cases without explicit existence checks.
- Add the number back to the set if it’s not already there (though logically, we assume valid inputs where only occupied numbers are released). Python sets handle duplicate additions gracefully by ignoring them, so a simple
Complexity Analysis
- Time Complexity:
- Initialization: to build the initial set of available slots.
get,check,release: All are amortized operations on a hash set.- Total for calls after initialization is . Given constraints, this fits well within time limits.
- Space Complexity:
- We store every available slot in the set: . This is necessary to track state and cannot be avoided without scanning (which would increase space but hurt time).
Solution
class PhoneDirectory:
def __init__(self, maxNumbers):
# Initialize a set with all numbers from 0 to maxNumbers - 1.
# This represents the pool of currently available phone slots.
self.available = set(range(maxNumbers))
def get(self) -> int:
"""Returns an empty slot or -1 if no number is available."""
if not self.available:
return -1
# Pop removes and returns a random element from the set efficiently.
return self.available.pop()
def check(self, number: int) -> bool:
"""Checks if 'number' slot is currently empty (available)."""
return number in self.available
def release(self, number: int):
"""Recycles or releases a specific slot back to the pool."""
# Adding an existing element does nothing harmful; it ensures
# availability status matches reality.
self.available.add(number)
Edge Cases Handled
- Empty Directory: If
getis called when all slots are taken,self.availablebecomes empty. The checkif not self.availablecorrectly returns-1. - Full Capacity Initialization: Initializing with ensures the range covers exactly
[0, maxNumbers), matching constraints (). - Release on Already Free Slot: If a number is released that was never taken (or already free),
set.addhandles it idempotently without throwing errors or corrupting state. This makes the implementation robust against invalid release calls in some test environments, though valid inputs are expected per problem description.