NeetCode #166LC-379MediumArrays & Hashing
← Back to All Problems#166 · #379 · Design Phone Directory(电话目录)
📌 Problem Statement & Constraints
Design a phone directory that assigns numbers in the range
[0, maxNumbers - 1]. Implement get() returning an available number (or -1 if none), check(number) returning whether the number is available, and release(number) returning a number to the pool. Constraints: 1 <= maxNumbers <= 10^4; at most 10^4 calls.💡 Core Algorithmic Approaches
- Keep a set of available numbers plus a set of used numbers.
getpops an arbitrary available number and moves it to the used set.checkis a set membership test;releasemoves a number back if it was in use.- The
releasemust be idempotent with respect to already-available numbers -- releasing a number that is already free is a no-op.
💻 Benchmark Python3 Implementation
class PhoneDirectory:
def __init__(self, maxNumbers: int):
self.available = set(range(maxNumbers))
self.used = set()
def get(self) -> int:
if not self.available:
return -1
num = self.available.pop()
self.used.add(num)
return num
def check(self, number: int) -> bool:
return number in self.available
def release(self, number: int) -> None:
if number in self.used: # only release numbers actually in use
self.used.discard(number)
self.available.add(number)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) average per operation.
💾 Space Complexity
O(maxNumbers).
⚠️ Interview Pitfalls & Follow-ups
- Releasing a number that is already available: without the
usedcheck, the set would still contain it once, so it is harmless here -- but in a design that tracks counts it would corrupt the state. The guard makes the intent explicit. - Using a list with linear search for
get: O(n) per call. - Returning the smallest available number: the problem allows any available number, so a set pop is fine.
- Forgetting to remove the number from
availableonget: the same number could be handed out twice.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.