379 Design Phone Directory

Design a Phone Directory which supports the following operations:

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. check: Check if a number is available or not.

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):
        """
        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
        else:
            min_avail = self.avail_phone_nums.get()
            self.active_phone_nums.add(min_avail)
            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())