Design Phone Directory - Video Solutions
Design Phone Directory
Design Phone Directory - Video Solution
Watch 8 video solutions for Design Phone Directory, a medium level problem involving Array, Hash Table, Linked List. This walkthrough by Scott has 2,694 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 slotsmaxNumbers.int get()Provides a number that is not assigned to anyone. Returns-1if no number is available.bool check(int number)Returnstrueif the slotnumberis available andfalseotherwise.void release(int number)Recycles or releases the slotnumber.
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 < maxNumbers- At most
2 * 104calls will be made toget,check, andrelease.
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.
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 |