379. Design Phone Directory π
Description
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-1
if no number is available.bool check(int number)
Returnstrue
if the slotnumber
is available andfalse
otherwise.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 <= 104
0 <= number < maxNumbers
- At most
2 * 104
calls will be made toget
,check
, andrelease
.
Solutions
Solution 1: Hash Table
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
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|