379. Design Phone Directory

Problem Description

In this problem, we are tasked with designing a phone directory that manages phone number allocations. The directory starts with maxNumbers of unassigned or available numbers. The core functionality that we need to provide includes:

• Acquiring a phone number from the directory which has not been allocated to anyone.
• Checking to determine if a particular number is available for allocation.
• Releasing a phone number so it can become available again for allocation.

This directory should work efficiently, handle requests for a number, query the status of a number, and recycle or release a number back to the directory.

Intuition

The intuition behind this solution leverages a basic data structure, a list, to track the utilization of phone numbers. The list is initialized to have a size equal to the maximum number of phone numbers the directory can manage, with each element representing whether a particular phone number has been allocated (True) or is available (False).

When a number is requested, the directory searches through the list to find the first available (False) number, marks it as allocated (True), and returns it. If no numbers are available, it returns -1.

To check if a number is available, we simply check the corresponding value in the list. If it is False, the number is available, so we return True; otherwise, we return False.

Releasing a number involves setting the corresponding list element back to False, making the number available again.

This approach is straightforward and efficient for a small scale directory. For larger directories with more numbers, more complex data structures and algorithms would be needed for efficient performance. However, for the scope of this problem, a list is sufficient to track the allocation status of each phone number efficiently.

Learn more about Queue and Linked List patterns.

Solution Approach

The solution implements the PhoneDirectory class with the methods get, check, and release. Let's break down the implementation for each method and the constructor:

• Constructor (__init__): The constructor is responsible for initializing the directory. We use a list self.provided with the length of maxNumbers, filling it with False to indicate that initially, all numbers are available. The indexing of this list corresponds to phone numbers. If self.provided[i] is False, then the number i is available; otherwise, it is already taken.

  1def __init__(self, maxNumbers: int):
  2    self.provided = [False] * maxNumbers

• Get a Number (get): This method looks for an unassigned number by iterating through self.provided. When it finds an element that is False, it marks this element as True to signify that the number is now taken and returns the index, which represents the phone number itself.

  If all numbers are taken (every element in the list is True), the method returns -1. This operation is O(n) in the worst case, where n is maxNumbers.

  1def get(self) -> int:
  2    for i in range(len(self.provided)):
  3        if not self.provided[i]:
  4            self.provided[i] = True
  5            return i
  6    return -1

• Check a Number (check): The check method checks the availability of a number number by returning not self.provided[number]. Since list access is O(1), this method is very efficient. It returns True if the number is available, otherwise False.

  1def check(self, number: int) -> bool:
  2    return not self.provided[number]

• Release a Number (release): The release method makes a number available again by setting self.provided[number] back to False. The given number is thus recycled and can be allocated again in the future.

  1def release(self, number: int) -> None:
  2    self.provided[number] = False

The use of a list here is a deliberate choice based on simplicity and ease of implementation. The solution is easy to understand and reason about, which is often valuable in software design, especially when performance requirements are met as they are in this case for smaller datasets.

Example Walkthrough

In this example, we will create a phone directory with a maximum of 3 phone numbers (0, 1, and 2) and walk through the process of acquiring, checking, and releasing phone numbers.

• Initialization:

First, we initialize the phone directory with a capacity of 3 numbers. All numbers are available at the beginning.

1directory = PhoneDirectory(3)
2print(directory.provided) # Output: [False, False, False]

• Acquire a Number:

Next, let's acquire a number using the get method. It should give us the first available number, which is 0.

1number = directory.get()
2print(number) # Output: 0
3print(directory.provided) # Output: [True, False, False]

The state of directory.provided after calling get shows that the number 0 has been marked as taken (True).

• Check Number Availability:

Now, let's check if the number 1 is available using the check method.

1is_available = directory.check(1)
2print(is_available) # Output: True

The output is True, which means number 1 is available.

• Acquire Another Number:

Let's get another number. This time it should give us the next available number, which is 1.

1number = directory.get()
2print(number) # Output: 1
3print(directory.provided) # Output: [True, True, False]

Now, numbers 0 and 1 are marked as taken.

• Try to Acquire a Non-available Number:

If we try to check if number 0 is available, it should return False since we've already acquired it.

1is_available = directory.check(0)
2print(is_available) # Output: False

• Acquire the Last Number:

Acquiring the third number will give us 2, which is the last available number.

1number = directory.get()
2print(number) # Output: 2
3print(directory.provided) # Output: [True, True, True]

Now all numbers are taken.

• Trying to Acquire a Fourth Number:

If we try to acquire another number, since all are taken, the get method should return -1.

1number = directory.get()
2print(number) # Output: -1

• Release a Number:

Let's say the user of number 1 has decided to give up their number. We release it using the release method.

1directory.release(1)
2print(directory.provided) # Output: [True, False, True]

Number 1 is now available again.

• Acquire a Number After Release:

Finally, if we acquire a number again, it should give us the number we just released, which is 1.

1number = directory.get()
2print(number) # Output: 1
3print(directory.provided) # Output: [True, True, True]

Number 1 has been reassigned, and now all numbers are taken once more. This example demonstrates the flow of acquiring, checking the status, and releasing phone numbers within our phone directory.

Solution Implementation

Time and Space Complexity

Time Complexity

• __init__: O(n). Initializes the provided list of size n (where n is maxNumbers) with False, which is done in linear time relative to maxNumbers.
• get: O(n). Iterates through the provided list in the worst case, which requires linear time relative to maxNumbers to find an available number.
• check: O(1). Checks if a specific number is available by accessing the provided list's index, which is a constant time operation.
• release: O(1). Sets the provided list's index to False, indicating the number is available, which is a constant time operation.

Space Complexity

• The space complexity for the PhoneDirectory class is O(n), where n is maxNumbers. The provided list is the only data structure used, and its size is dependent on the value of maxNumbers.

Learn more about how to find time and space complexity quickly using problem constraints.