⚡Flashcard Drill➔
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

  1. Keep a set of available numbers plus a set of used numbers.
  2. get pops an arbitrary available number and moves it to the used set.
  3. check is a set membership test; release moves a number back if it was in use.
  4. The release must 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 used check, 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 available on get: 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems