Design Phone Directory

Medium

Asked by:

4 views

Topics:

Arrays

Design a phone directory system that can perform the following operations:

get(): Provide a number which is not assigned to anyone.
check(number): Check if a number is available or not.
release(number): Recycle or release a number.

Implement the PhoneDirectory class:

PhoneDirectory(int maxNumbers) Initializes the phone directory with the range of numbers [0, maxNumbers - 1].
int get() Provides a number which is not assigned to anyone. Returns -1 if no number is available.
boolean check(int number) Returns true if the number is available and not assigned, and false otherwise.
void release(int number) Recycles or releases a number.

Example 1:

PhoneDirectory directory = new PhoneDirectory(3);
directory.get();   // It can return any available phone number. Here we assume it returns 0.
directory.get();   // It returns 1.
directory.check(2); // Returns true, the number 2 is available.
directory.get();   // It returns 2.
directory.check(2); // Returns false, the number 2 is no longer available.
directory.release(2);
directory.check(2); // Returns true, the number 2 is available again.

Constraints:

1 <= maxNumbers <= 10⁴
0 <= number < maxNumbers
At most 2 * 10⁴ calls will be made to get, check, and release.

Try coding it in LeetCode

Design Phone Directory

Medium

Asked by:

4 views

Topics:

Arrays

Design a phone directory system that can perform the following operations:

get(): Provide a number which is not assigned to anyone.
check(number): Check if a number is available or not.
release(number): Recycle or release a number.

Implement the PhoneDirectory class:

PhoneDirectory(int maxNumbers) Initializes the phone directory with the range of numbers [0, maxNumbers - 1].
int get() Provides a number which is not assigned to anyone. Returns -1 if no number is available.
boolean check(int number) Returns true if the number is available and not assigned, and false otherwise.
void release(int number) Recycles or releases a number.

Example 1:

PhoneDirectory directory = new PhoneDirectory(3);
directory.get();   // It can return any available phone number. Here we assume it returns 0.
directory.get();   // It returns 1.
directory.check(2); // Returns true, the number 2 is available.
directory.get();   // It returns 2.
directory.check(2); // Returns false, the number 2 is no longer available.
directory.release(2);
directory.check(2); // Returns true, the number 2 is available again.

Constraints:

1 <= maxNumbers <= 10⁴
0 <= number < maxNumbers
At most 2 * 10⁴ calls will be made to get, check, and release.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of phone numbers that the directory needs to support?
Are phone numbers represented as integers, strings, or some other data type?
What is the expected behavior if I try to recycle a number that is not currently in use?
What is the valid range for phone numbers (e.g., positive integers only)?
How should I handle concurrent access from multiple threads or processes?

Brute Force Solution

Approach

The phone directory problem asks us to manage a pool of phone numbers. The brute force strategy involves simply keeping track of all allocated numbers and, when asked to provide a number, checking every available number to see if it's free.

Here's how the algorithm would work step-by-step:

When the system starts, consider all numbers in the specified range as available.
When someone asks for a phone number, go through the available numbers one by one.
If you find a number that hasn't been given out yet, give it to the person.
Mark that number as no longer available, so you don't give it out again.
When someone releases a phone number, mark it as available again so someone else can use it later.
If someone asks if a particular number is available, just check if that number is currently marked as available or not.

Code Implementation

class PhoneDirectory:

    def __init__(self, max_numbers: int):
        self.available_numbers = list(range(max_numbers))
        self.max_numbers = max_numbers

    def get(self) -> int:
        # If no numbers left, return -1
        if not self.available_numbers:
            return -1

        phone_number = self.available_numbers.pop(0)

        return phone_number

    def check(self, phone_number: int) -> bool:
        # Checks if the number is available.
        return phone_number in self.available_numbers

    def release(self, phone_number: int) -> None:
        # Only add back numbers in the valid range
        if 0 <= phone_number < self.max_numbers:
            # Releasing a number makes it available again.
            self.available_numbers.append(phone_number)
            self.available_numbers.sort()

Big(O) Analysis

Time Complexity

O(n) – Let n be the total number of phone numbers in the directory. The get() operation iterates through the available numbers in the worst-case scenario to find an available one, which can take O(n) time if the first available number is at the very end. The contains() operation directly checks if a number is available in O(1) time assuming a good data structure like a set or boolean array. The release() operation marks a number as available, taking O(1) time. Therefore, the dominant operation get() takes O(n) time in the worst case.

Space Complexity

O(N) – The given solution needs to keep track of available and allocated phone numbers within the specified range. The most straightforward way to implement this, based on the description, is to use a boolean array or a set of size N, where N represents the total number of phone numbers in the directory. This data structure is used to mark each number as either available or unavailable. Therefore, the auxiliary space required grows linearly with the number of phone numbers, N, resulting in O(N) space complexity.

Optimal Solution

Approach

The phone directory design requires us to efficiently manage and track phone numbers. The optimal approach involves using data structures that allow for quick checks of availability and assignment of numbers. We will maintain a pool of available numbers and efficiently mark numbers as used or available.

Here's how the algorithm would work step-by-step:

Start with a set containing all the phone numbers within the given range.
When a request comes to get a number, check if the set is empty. If it is, you're out of numbers and can't fulfill the request.
If the set is not empty, choose one of the numbers from the set and remove it. This marks the number as used.
When a request comes to release a number, add that number back into the set of available numbers. This makes it available for use again.
The set allows you to quickly check if a number is available without having to search through a list.

Code Implementation

class PhoneDirectory:

    def __init__(self, max_numbers: int):
        self.available_numbers = set(range(max_numbers))
        self.max_numbers = max_numbers

    def get(self) -> int:
        # Check if numbers are available before assigning.
        if not self.available_numbers:
            return -1

        available_number = self.available_numbers.pop()
        return available_number

    def check(self, number: int) -> bool:
        return number in self.available_numbers

    def release(self, number: int) -> None:
        # Only release numbers within the valid range.
        if 0 <= number < self.max_numbers and number not in self.available_numbers:
            # Add number back to the available set
            self.available_numbers.add(number)

Big(O) Analysis

Time Complexity

O(1) – The phone directory uses a set to store available numbers. The get() operation involves checking if the set is empty and removing an element, which are both O(1) operations on a set. The release() operation involves adding an element back to the set, which is also an O(1) operation. Therefore, all operations have a constant time complexity.

Space Complexity

O(N) – The solution utilizes a set to store available phone numbers. In the worst case, when all numbers within the given range are initially available, the set will contain all N phone numbers, where N is the total number of phone numbers in the directory. Therefore, the auxiliary space required to store the set scales linearly with the number of phone numbers. Thus, the space complexity is O(N).

Edge Cases

Case	How to Handle
maxNumbers is zero or negative	Throw an IllegalArgumentException or return an error code as no phone numbers can be allocated in this case.
Calling get() on a number not yet recycled/released	Return -1 to indicate the number is still in use and not available.
Very large maxNumbers leading to potential integer overflow or memory issues	Consider using long instead of int for storing the number range or choose an appropriate data structure such as a bitset to minimize memory footprint.
Repeated release of the same phone number.	Ensure the released number is not already in the available set to prevent it being allocated multiple times (could use a set for available numbers).
Attempting to recycle a number that was never allocated.	Ignore the recycle request or throw an exception to indicate invalid operation.
Running out of phone numbers after multiple allocations and releases.	Return -1 when get() is called and no available numbers are found.
Concurrent access to the phone directory from multiple threads.	Use synchronization mechanisms (e.g., locks or atomic operations) to ensure thread safety when accessing and modifying the directory's state.
maxNumbers is close to Integer.MAX_VALUE	Be aware of potential integer overflow issues when calculating indices or sizes related to the phone directory.