Watch 10 video solutions for Design Phone Directory, a medium level problem involving Array, Hash Table, Linked List. This walkthrough by NeetCodeIO has 320,904 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1040 <= number < maxNumbers2 * 104 calls will be made to get, check, and release.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.
| 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 |