Problem

Design a Phone Directory which supports the following operations:

  1. get: Provide a number which is not assigned to anyone.
  2. check: Check if a number is available or not.
  3. 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

  1. Initialize a queue with all numbers from 0 to maxNumbers - 1.
  2. Use a set to keep track of assigned numbers.
  3. On get, remove and return a number from the queue if available, and add it to the set.
  4. On check, return true if the number is not in the set and is within range.
  5. 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.
C++
 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);
    }
};
Java
 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);
    }
}
Python
 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)