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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1class PhoneDirectory:
2    def __init__(self, max_numbers: int):
3        """
4        Initialize the phone directory.
5        @param max_numbers: The maximum numbers that can be stored in the phone directory.
6        """
7        self.is_provided = [False] * max_numbers  # List to track availability of numbers.
8
9    def get(self) -> int:
10        """
11        Provide a number that is not assigned to anyone.
12        @return: Return an available number. Return -1 if none is available.
13        """
14        for i, available in enumerate(self.is_provided):
15            if not available:  # If the number is available
16                self.is_provided[i] = True  # Mark the number as taken
17                return i  # Return the number
18        return -1  # Return -1 if no numbers are available
19
20    def check(self, number: int) -> bool:
21        """
22        Check if a number is available or not.
23        @param number: The number to be checked.
24        @return: True if the number is available, False otherwise.
25        """
26        return not self.is_provided[number]  # Return the negation of the provided status of the number
27
28    def release(self, number: int) -> None:
29        """
30        Recycle or release a number.
31        @param number: The number to be released.
32        """
33        self.is_provided[number] = False  # Mark the number as available again
34
35# Example usage:
36# obj = PhoneDirectory(max_numbers)
37# available_number = obj.get()
38# is_available = obj.check(number)
39# obj.release(number)
40
1class PhoneDirectory {
2
3    // Array to track the allocation status of numbers.
4    private boolean[] isNumberAvailable;
5
6    /**
7     * Initializes a phone directory for a given maximum number of phone numbers.
8     * 
9     * @param maxNumbers - The maximum numbers that can be stored in the phone directory.
10     */
11    public PhoneDirectory(int maxNumbers) {
12        isNumberAvailable = new boolean[maxNumbers];
13        // Initialize with all numbers available.
14        for (int i = 0; i < maxNumbers; i++) {
15            isNumberAvailable[i] = true;
16        }
17    }
18
19    /**
20     * Provides a number that is not currently assigned to anyone.
21     * 
22     * @return - Returns an available number, or -1 if no number is available.
23     */
24    public int get() {
25        for (int i = 0; i < isNumberAvailable.length; i++) {
26            if (isNumberAvailable[i]) {
27                isNumberAvailable[i] = false; // Mark the number as not available.
28                return i; // Return the available number.
29            }
30        }
31        return -1; // No number is available.
32    }
33
34    /**
35     * Checks if a number is available or not.
36     * 
37     * @param number - The number to check for availability.
38     * @return - Returns true if the number is available, false otherwise.
39     */
40    public boolean check(int number) {
41        return number >= 0 && number < isNumberAvailable.length && isNumberAvailable[number];
42    }
43
44    /**
45     * Recycles or releases a number that was previously assigned.
46     * 
47     * @param number - The number to release.
48     */
49    public void release(int number) {
50        if (number >= 0 && number < isNumberAvailable.length) {
51            isNumberAvailable[number] = true; // Mark the number as available again.
52        }
53    }
54}
55
56// The PhoneDirectory class can be used as follows:
57/*
58PhoneDirectory directory = new PhoneDirectory(maxNumbers);
59int availableNumber = directory.get();
60boolean isAvailable = directory.check(number);
61directory.release(number);
62*/
63
1#include <vector>
2
3class PhoneDirectory {
4private:
5    // Vector to track the allocation status of numbers.
6    std::vector<bool> is_number_available;
7
8public:
9    /**
10     * Initializes a phone directory for a given maximum number of phone numbers.
11     * 
12     * @param max_numbers - The maximum numbers that can be stored in the phone directory.
13     */
14    PhoneDirectory(int max_numbers) : is_number_available(max_numbers, true) {
15        // Vector is initialized with all numbers available.
16    }
17
18    /**
19     * Provides a number that is not currently assigned to anyone.
20     * 
21     * @return - Returns an available number, or -1 if no number is available.
22     */
23    int get() {
24        for (size_t i = 0; i < is_number_available.size(); ++i) {
25            if (is_number_available[i]) {
26                is_number_available[i] = false; // Mark the number as not available.
27                return i; // Return the available number.
28            }
29        }
30        return -1; // No number is available.
31    }
32
33    /**
34     * Checks if a number is available or not.
35     * 
36     * @param number - The number to check for availability.
37     * @return - Returns true if the number is available, false otherwise.
38     */
39    bool check(int number) const {
40        return number >= 0 && static_cast<size_t>(number) < is_number_available.size() && is_number_available[number];
41    }
42
43    /**
44     * Recycles or releases a number that was previously assigned.
45     * 
46     * @param number - The number to release.
47     */
48    void release(int number) {
49        if (number >= 0 && static_cast<size_t>(number) < is_number_available.size()) {
50            is_number_available[number] = true; // Mark the number as available again.
51        }
52    }
53};
54
55// The PhoneDirectory class can be used as follows:
56/*
57PhoneDirectory directory(max_numbers);
58int available_number = directory.get();
59bool is_available = directory.check(number);
60directory.release(number);
61*/
62
1// Type declaration for the phone directory.
2type PhoneDirectoryType = {
3    isNumberAvailable: boolean[];
4    maxNumbers: number;
5    get: () => number;
6    check: (number: number) => boolean;
7    release: (number: number) => void;
8};
9
10// Array to track the allocation status of numbers.
11let isNumberAvailable: boolean[];
12
13// Initializes the phone directory for a given maximum number of phone numbers.
14function initialize(maxNumbers: number): void {
15    isNumberAvailable = new Array(maxNumbers).fill(true);
16}
17
18// Provides a number that is not currently assigned to anyone.
19function get(): number {
20    for (let i = 0; i < isNumberAvailable.length; i++) {
21        if (isNumberAvailable[i]) {
22            isNumberAvailable[i] = false; // Mark the number as not available.
23            return i; // Return the available number.
24        }
25    }
26    return -1; // No number is available.
27}
28
29// Checks if a number is available or not.
30function check(number: number): boolean {
31    return number >= 0 && number < isNumberAvailable.length && isNumberAvailable[number];
32}
33
34// Recycles or releases a number that was previously assigned.
35function release(number: number): void {
36    if (number >= 0 && number < isNumberAvailable.length) {
37        isNumberAvailable[number] = true; // Mark the number as available again.
38    }
39}
40
41// The phone directory can be initialized and used as follows:
42/*
43initialize(maxNumbers);
44let availableNumber = get();
45let isAvailable = check(number);
46release(number);
47*/
48
49// If you still want to group the functionalities under a 'PhoneDirectory' variable as an object:
50let PhoneDirectory: PhoneDirectoryType = {
51    isNumberAvailable: [],
52    maxNumbers: 0,
53    get,
54    check,
55    release,
56};
57
58// Initialize a phone directory with a specified maximum number of phone numbers.
59PhoneDirectory.maxNumbers = 10; // Example maximum size of the directory
60initialize(PhoneDirectory.maxNumbers);
61
62// Use the PhoneDirectory methods as necessary.
63// PhoneDirectory.get(); PhoneDirectory.check(3); PhoneDirectory.release(3);
64

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.