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 listself.provided
with the length ofmaxNumbers
, filling it withFalse
to indicate that initially, all numbers are available. The indexing of this list corresponds to phone numbers. Ifself.provided[i]
isFalse
, then the numberi
is available; otherwise, it is already taken.def __init__(self, maxNumbers: int): self.provided = [False] * maxNumbers
-
Get a Number (
get
): This method looks for an unassigned number by iterating throughself.provided
. When it finds an element that isFalse
, it marks this element asTrue
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 isO(n)
in the worst case, wheren
ismaxNumbers
.def get(self) -> int: for i in range(len(self.provided)): if not self.provided[i]: self.provided[i] = True return i return -1
-
Check a Number (
check
): Thecheck
method checks the availability of a numbernumber
by returning notself.provided[number]
. Since list access isO(1)
, this method is very efficient. It returnsTrue
if the number is available, otherwiseFalse
.def check(self, number: int) -> bool: return not self.provided[number]
-
Release a Number (
release
): The release method makes a number available again by settingself.provided[number]
back toFalse
. The given number is thus recycled and can be allocated again in the future.def release(self, number: int) -> None: 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 EvaluatorExample 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.
directory = PhoneDirectory(3)
print(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.
number = directory.get()
print(number) # Output: 0
print(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.
is_available = directory.check(1)
print(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.
number = directory.get()
print(number) # Output: 1
print(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.
is_available = directory.check(0)
print(is_available) # Output: False
- Acquire the Last Number:
Acquiring the third number will give us 2, which is the last available number.
number = directory.get()
print(number) # Output: 2
print(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
.
number = directory.get()
print(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.
directory.release(1)
print(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.
number = directory.get()
print(number) # Output: 1
print(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 = {