Design Phone Directory - Solution & Explanation

Q: 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.

Q: 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().

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumPremiumFree on FleetCodeArray Hash Table Linked List Design8 min readAsked at: Google

Practice this problem

Problem Statement

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:

1 <= maxNumbers <= 10⁴
0 <= number < maxNumbers
At most 2 * 10⁴ calls will be made to get, check, and release.

Approach Overview

Problem Overview: Design a phone directory that manages a pool of phone numbers from 0 to maxNumbers - 1. The system must support three operations: assign an available number (get()), check if a number is free (check()), and release a number back to the pool (release()).

Approach 1: Linear Scan with Availability Array (O(n) time, O(n) space)

The simplest design keeps a boolean array where each index represents whether a number is currently assigned. The get() operation scans the array from the beginning to find the first unused number, marks it as used, and returns it. check() directly reads the boolean value at the index, and release() flips the value back to available. The downside is the get() operation can take O(n) time when most numbers are assigned because it must iterate through the array to find a free slot.

Approach 2: Hash Table + Queue of Available Numbers (O(1) time, O(n) space)

The efficient design stores all currently available numbers in a queue and tracks assigned numbers using a hash table or boolean array. During initialization, push all numbers 0..maxNumbers-1 into the queue. When get() is called, pop from the queue and mark the number as used in the hash structure. The check() operation performs a constant-time lookup to see whether the number is currently assigned. When release() is called, verify the number is marked as used, remove it from the assigned set, and push it back into the queue.

The key insight is separating two responsibilities: the queue guarantees fast access to the next available number, while the hash structure provides constant-time membership checks. This avoids scanning the entire number range. Each operation—get, check, and release—runs in O(1) average time while using O(n) space to store availability information.

Recommended for interviews: The queue + hash table design is what interviewers typically expect for this design problem. Mentioning the linear scan approach first shows you understand the baseline solution, but implementing the constant-time queue-based design demonstrates stronger system thinking and efficient data structure usage.

Solution

We can use a hash set available to store unallocated phone numbers. Initially, the hash set contains [0, 1, 2, ..., maxNumbers - 1].

When the get method is called, we take an unallocated phone number from available. If available is empty, we return -1. The time complexity is O(1).

When the check method is called, we just need to check whether number is in available. The time complexity is O(1).

When the release method is called, we add number to available. The time complexity is O(1).

The space complexity is O(n), where n is the value of maxNumbers.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Linear Scan with Availability Array	O(n) for get, O(1) for check/release	O(n)	Simple implementation when the number pool is small
Hash Table + Queue of Available Numbers	O(1) average per operation	O(n)	Best general solution for constant-time allocation and release

Video Solution

Design Phone Directory • Scott • 2,694 views views

Watch 7 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Design Phone Directory with our built-in code editor and test cases.

Practice on FleetCode

Seat Reservation Manager

Problem Info

DifficultyMedium

Acceptance52.7%

Approaches1

Reading time8 min

Asked at

Google