# 379 Design Phone Directory

Design a Phone Directory which supports the following operations:
1. 1.
`get`: Provide a number which is not assigned to anyone. If the numbers in the PhoneDirectory exceed the maximum constructed size, return -1. Otherwise return the smallest avail phone number.
2. 2.
`check`: Check if a number is available or not.
3. 3.
`release`: Recycle or release a number.
Example:
// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);
// It can return any available phone number. Here we assume it returns 0.
directory.get();
// Assume it returns 1.
directory.get();
// The number 2 is available, so return true.
directory.check(2);
// It returns 2, the only number that is left.
directory.get();
// The number 2 is no longer available, so return false.
directory.check(2);
// Release number 2 back to the pool.
directory.release(2);
// Number 2 is available again, return true.
directory.check(2);
The Idea: We can use a combination of a priority queue and hash table to efficiently solve this problem. A hash table can be used to store all the active phone numbers, while a priority queue can be used to retrieve the smallest available option when a phone number get released.
Complexity: get - O(1) time, check - O(1) time, release - O(log(k) time where k is the number of times released has been call consecutively. O(n) space where n is the total number of active phone numbers in the directory
from queue import PriorityQueue
class PhoneDirectory:
def __init__(self, maxNumbers):
"""
@param maxNumbers - The maximum numbers that can be stored in the phone directory.
:type maxNumbers: int
"""
self.max_nums = maxNumbers
self.active_phone_nums = set()
self.avail_phone_nums = PriorityQueue()
self.iter = 0
def get(self):
"""
Provide a number which is not assigned to anyone.
@return - Return an available number. Return -1 if none is available.
:rtype: int
"""
if len(self.active_phone_nums) >= self.max_nums:
return -1
if self.avail_phone_nums.empty():
self.iter += 1
return self.iter - 1
else:
min_avail = self.avail_phone_nums.get()
return min_avail
def check(self, number):
"""
Check if a number is available or not.
:type number: int
:rtype: bool
"""
return number not in self.active_phone_nums
def release(self, number):
"""
Recycle or release a number.
:type number: int
:rtype: void
"""
if number in self.active_phone_nums:
self.avail_phone_nums.put(number)
self.active_phone_nums.remove(number)
# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number)
# sanity check
obj = PhoneDirectory(1)
print(obj.check(0))
print(obj.get())
print(obj.check(0))
print(obj.get())