Problem Description

The "Design Phone Directory" problem asks you to implement a phone directory that manages a pool of phone numbers. The directory should support three main operations:

• get(): Provide an available number from the directory. If no number is available, return -1.
• check(number): Check if a specific number is available in the directory.
• release(number): Recycle or release a previously assigned number back to the pool, making it available again.

The directory is initialized with a maximum number of phone numbers, maxNumbers. All numbers in the range 0 to maxNumbers - 1 are initially available. You must ensure that:

• No number is assigned more than once at a time.
• Numbers can be released and reassigned efficiently.

Thought Process

At first glance, you might consider using a simple array or list to track which numbers are available or assigned. For example, you could use a boolean array where each index represents a number's availability. However, this approach could be inefficient for the get() operation, as you may need to scan the entire array to find an available number.

To optimize, we need a way to quickly assign and recycle numbers. Ideally, we want get(), check(), and release() to all operate in constant time (O(1)). This suggests using data structures like a queue (to track available numbers) and a set (to check availability quickly).

The challenge is to ensure that assigned numbers are not given out again until they are released, and that checking and releasing are both efficient.

Solution Approach

We will use two main data structures:

• Queue (or set): To keep track of available numbers. We can use a queue to efficiently pop the next available number for get() and add numbers back on release().
• Set: To quickly check if a number is available or not in check(). This prevents assigning the same number twice.

The steps are:

1. Initialization: Fill the queue with all numbers from 0 to maxNumbers - 1. The set contains all these numbers as well.
2. get(): Remove and return a number from the queue (if available), and remove it from the set to mark it as assigned. If no numbers are left, return -1.
3. check(number): Return true if the number is in the set (i.e., available), false otherwise.
4. release(number): If the number is not already available (i.e., not in the set), add it back to the queue and the set.

This design ensures that all operations are efficient and that no number is assigned more than once without being released.

Example Walkthrough

Suppose maxNumbers = 3. The directory is initialized with numbers 0, 1, 2 available.

1. get() returns 0. Now, available numbers are 1, 2.
2. get() returns 1. Now, available number is 2.
3. check(2) returns true (since 2 is available).
4. get() returns 2. Now, no numbers are available.
5. get() returns -1 (since all numbers are assigned).
6. release(1) makes 1 available again.
7. get() returns 1 (since it was just released).

At each step, the set and queue ensure that numbers are not assigned twice, and released numbers become available again.

Time and Space Complexity

Brute-force approach: Using only an array or list, get() could take O(N) time in the worst case (where N is the total number of phone numbers), as you may need to scan for an available number.

Optimized approach: With a queue and set:

• get(): O(1), as we pop from the queue and remove from the set.
• check(number): O(1), as set lookup is constant time.
• release(number): O(1), as set and queue insertions are constant time.
• Space: O(N) for storing the set and queue of numbers.

This makes the optimized approach very efficient for all required operations.

Summary

The Phone Directory problem is elegantly solved using a combination of a queue (to track available numbers) and a set (to enable fast availability checks). This approach ensures all operations—get(), check(), and release()—are performed in constant time. By carefully managing which numbers are available and assigned, we guarantee correctness and efficiency, making this solution both practical and optimal for real-world scenarios.

Code Implementation

from collections import deque

class PhoneDirectory:
    def __init__(self, maxNumbers: int):
        self.available = deque(range(maxNumbers))
        self.available_set = set(range(maxNumbers))

    def get(self) -> int:
        if not self.available:
            return -1
        number = self.available.popleft()
        self.available_set.remove(number)
        return number

    def check(self, number: int) -> bool:
        return number in self.available_set

    def release(self, number: int) -> None:
        if number not in self.available_set:
            self.available.append(number)
            self.available_set.add(number)
      

#include <queue>
#include <unordered_set>

class PhoneDirectory {
private:
    std::queue<int> available;
    std::unordered_set<int> available_set;
public:
    PhoneDirectory(int maxNumbers) {
        for (int i = 0; i < maxNumbers; ++i) {
            available.push(i);
            available_set.insert(i);
        }
    }
    
    int get() {
        if (available.empty()) return -1;
        int number = available.front();
        available.pop();
        available_set.erase(number);
        return number;
    }
    
    bool check(int number) {
        return available_set.count(number) > 0;
    }
    
    void release(int number) {
        if (available_set.count(number) == 0) {
            available.push(number);
            available_set.insert(number);
        }
    }
};
      

import java.util.*;

class PhoneDirectory {
    private Queue<Integer> available;
    private Set<Integer> availableSet;

    public PhoneDirectory(int maxNumbers) {
        available = new LinkedList<>();
        availableSet = new HashSet<>();
        for (int i = 0; i < maxNumbers; i++) {
            available.offer(i);
            availableSet.add(i);
        }
    }

    public int get() {
        if (available.isEmpty()) return -1;
        int number = available.poll();
        availableSet.remove(number);
        return number;
    }

    public boolean check(int number) {
        return availableSet.contains(number);
    }

    public void release(int number) {
        if (!availableSet.contains(number)) {
            available.offer(number);
            availableSet.add(number);
        }
    }
}
      

class PhoneDirectory {
    constructor(maxNumbers) {
        this.available = [];
        this.availableSet = new Set();
        for (let i = 0; i < maxNumbers; i++) {
            this.available.push(i);
            this.availableSet.add(i);
        }
    }

    get() {
        if (this.available.length === 0) return -1;
        const number = this.available.shift();
        this.availableSet.delete(number);
        return number;
    }

    check(number) {
        return this.availableSet.has(number);
    }

    release(number) {
        if (!this.availableSet.has(number)) {
            this.available.push(number);
            this.availableSet.add(number);
        }
    }
}