We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Phone Directory

Number: 379

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Design a phone directory that can manage a pool of phone numbers. It should support retrieving an available number, checking if a specific number is available, and releasing a number so it can be used again.

Key Insights

  • Use a queue to keep track of available phone numbers in order.
  • Use a set (or equivalent hash table) to support O(1) lookups when checking if a number is available.
  • On releasing a number, ensure it is added back only if it wasn’t already available.
  • Efficiently manage operations to meet the constraints of up to 10^4 numbers and 2 * 10^4 operations.

Space and Time Complexity

Time Complexity: O(1) per operation on average. Space Complexity: O(maxNumbers)

Solution

The solution utilizes two main data structures: a queue and a hash set. The queue stores the available phone numbers in order to quickly provide a number when requested by the get() method. The hash set is used to check the availability of any given number in O(1) time. When a number is allocated, it’s removed from both the queue and the set to mark it as in use. When a number is released, it is reinserted into both data structures (only if it isn’t already available) to ensure proper recycling. This combination of data structures satisfies the problem constraints and enables efficient operations.

Code Solutions

from collections import deque

class PhoneDirectory:
    def __init__(self, maxNumbers):
        # Initialize a deque with all numbers from 0 to maxNumbers-1.
        self.availableQueue = deque(range(maxNumbers))
        # Use a set to check if a number is available in O(1) time.
        self.availableSet = set(range(maxNumbers))
    
    def get(self):
        # If no phone number is available, return -1.
        if not self.availableQueue:
            return -1
        number = self.availableQueue.popleft()
        # Remove the number from the set since it's now taken.
        self.availableSet.remove(number)
        return number
    
    def check(self, number):
        # Return True if the number is in the availableSet.
        return number in self.availableSet
    
    def release(self, number):
        # Only add the number back if it's not already available.
        if number not in self.availableSet:
            self.availableQueue.append(number)
            self.availableSet.add(number)
            
# Example usage:
# phoneDirectory = PhoneDirectory(3)
# print(phoneDirectory.get())
# print(phoneDirectory.check(2))
← Back to All Questions