Problem# Design a Phone Directory which supports the following operations:
get
: Provide a number which is not assigned to anyone.check
: Check if a number is available or not.release
: Recycle or release a number.Examples# Example 1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);
// It can return any available phone number. Here we assume it returns 0.
directory.get ();
// Assume it returns 1.
directory.get ();
// The number 2 is available, so return true.
directory.check (2);
// It returns 2, the only number that is left.
directory.get ();
// The number 2 is no longer available, so return false.
directory.check (2);
// Release number 2 back to the pool.
directory.release (2);
// Number 2 is available again, return true.
directory.check (2);
Solution# Method 1 – Queue and Set for Available Numbers# Intuition# To efficiently manage available and assigned phone numbers, we use a queue to store available numbers and a set to track assigned numbers. The queue allows us to quickly provide an available number, while the set enables fast checks and releases.
Approach# Initialize a queue with all numbers from 0 to maxNumbers - 1. Use a set to keep track of assigned numbers. On get, remove and return a number from the queue if available, and add it to the set. On check, return true if the number is not in the set and is within range. On release, if the number is in the set, remove it and add it back to the queue. Complexity# ⏰ Time complexity: O(1)
for get, check, and release, as all operations are direct queue and set accesses. 🧺 Space complexity: O(n)
, where n is the total number of phone numbers. Code#
Cpp
Java
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class PhoneDirectory {
queue< int > available;
unordered_set< int > assigned;
int maxNum;
public :
PhoneDirectory(int maxNumbers) {
maxNum = maxNumbers;
for (int i = 0 ; i < maxNum; ++ i) available.push(i);
}
int get () {
if (available.empty()) return - 1 ;
int num = available.front(); available.pop();
assigned.insert(num);
return num;
}
bool check (int num) {
return num >= 0 && num < maxNum && ! assigned.count(num);
}
void release (int num) {
if (assigned.erase(num)) available.push(num);
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class PhoneDirectory {
private final Queue< Integer> available = new LinkedList<> ();
private final Set< Integer> assigned = new HashSet<> ();
private final int maxNum;
public PhoneDirectory (int maxNumbers) {
maxNum = maxNumbers;
for (int i = 0; i < maxNum; i++ ) available.offer (i);
}
public int get () {
if (available.isEmpty ()) return - 1;
int num = available.poll ();
assigned.add (num);
return num;
}
public boolean check (int num) {
return num >= 0 && num < maxNum && ! assigned.contains (num);
}
public void release (int num) {
if (assigned.remove (num)) available.offer (num);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import deque
class PhoneDirectory :
def __init__ (self, maxNumbers: int) -> None :
self. available: deque[int] = deque(range(maxNumbers))
self. assigned: set[int] = set()
self. maxNum: int = maxNumbers
def get (self) -> int:
if not self. available:
return - 1
num = self. available. popleft()
self. assigned. add(num)
return num
def check (self, num: int) -> bool:
return 0 <= num < self. maxNum and num not in self. assigned
def release (self, num: int) -> None :
if num in self. assigned:
self. assigned. remove(num)
self. available. append(num)