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.
// 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.
// Assume it returns 1.
// The number 2 is available, so return true.
// It returns 2, the only number that is left.
// The number 2 is no longer available, so return false.
// Release number 2 back to the pool.
// Number 2 is available again, return true.
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):
Initialize your data structure here
@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
self.active_phone_nums.add(self.iter - 1)
return self.iter - 1
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:
# 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)