Is Design Phone Directory easy or hard?

Design Phone Directory is generally rated Medium difficulty. The API itself is simple, but the challenge is designing a data structure that supports all operations in constant time while efficiently managing available numbers.

Design Phone Directory Python/Java solution

Most implementations use the same structure across languages: a queue (collections.deque in Python or ArrayDeque in Java) and a hash set or boolean array for tracking usage. The logic remains identical—pop from the queue for get(), check membership for check(), and push back during release().

How to solve Design Phone Directory in O(1)?

Initialize a queue containing all numbers from 0 to maxNumbers-1 and maintain a hash set or boolean array for assigned numbers. get() pops from the queue, check() verifies if the number exists in the assigned set, and release() removes it from the set and pushes it back to the queue. Each step performs constant-time operations.

What is the best approach for Design Phone Directory?

The most efficient approach uses a queue to store available numbers and a hash table (or boolean array) to track assigned numbers. The queue provides O(1) allocation of the next free number, while the hash lookup enables O(1) checks and releases. This keeps all operations—get, check, and release—constant time on average.

Is Design Phone Directory asked at Google/Amazon/Meta?

Design-style data structure problems like Design Phone Directory commonly appear in interviews at companies such as Google, Amazon, and Meta. They test the ability to design APIs, choose efficient data structures, and reason about time complexity for repeated operations.

What data structure is used in Design Phone Directory?

The optimal solution combines a queue and a hash table (or boolean array). The queue tracks available numbers for fast allocation, while the hash structure tracks which numbers are currently assigned so check() and release() can run in constant time.

What is the time complexity of Design Phone Directory?

With the optimal queue + hash table design, each operation runs in O(1) average time. The get() operation pops a number from the queue, check() performs a constant-time lookup, and release() pushes the number back to the queue. Space complexity is O(n) for storing the pool of numbers.

Description Solution Video 3:47

379. Design Phone Directory

Medium53.3% acceptance1 companyPremium elsewhere, free here

Design a phone directory that initially has maxNumbers empty slots that can store numbers. The directory should store numbers, check if a certain slot is empty or not, and empty a given slot.

Implement the PhoneDirectory class:

PhoneDirectory(int maxNumbers) Initializes the phone directory with the number of available slots maxNumbers.
int get() Provides a number that is not assigned to anyone. Returns -1 if no number is available.
bool check(int number) Returns true if the slot number is available and false otherwise.
void release(int number) Recycles or releases the slot number.

Example 1:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

Explanation
PhoneDirectory phoneDirectory = new PhoneDirectory(3);
phoneDirectory.get();      // It can return any available phone number. Here we assume it returns 0.
phoneDirectory.get();      // Assume it returns 1.
phoneDirectory.check(2);   // The number 2 is available, so return true.
phoneDirectory.get();      // It returns 2, the only number that is left.
phoneDirectory.check(2);   // The number 2 is no longer available, so return false.
phoneDirectory.release(2); // Release number 2 back to the pool.
phoneDirectory.check(2);   // Number 2 is available again, return true.

Constraints: