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.1def __init__(self, maxNumbers: int): 2 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
.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
): 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
.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 settingself.provided[number]
back toFalse
. 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 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.
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 theprovided
list of sizen
(wheren
ismaxNumbers
) withFalse
, which is done in linear time relative tomaxNumbers
.get
: O(n). Iterates through theprovided
list in the worst case, which requires linear time relative tomaxNumbers
to find an available number.check
: O(1). Checks if a specific number is available by accessing theprovided
list's index, which is a constant time operation.release
: O(1). Sets theprovided
list's index toFalse
, indicating the number is available, which is a constant time operation.
Space Complexity
- The space complexity for the
PhoneDirectory
class is O(n), wheren
ismaxNumbers
. Theprovided
list is the only data structure used, and its size is dependent on the value ofmaxNumbers
.
Learn more about how to find time and space complexity quickly using problem constraints.
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
Queue Intro Think of the last time you stood in line to buy movie tickets The first person in line gets their ticket first and any newcomers join the end of the line This system where the first person to arrive is the first to be served is a queue in real
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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.