Problem Explanation

The problem requires us to design a phone directory to store and retrieve phone numbers. The phone directory must support the following operations:

1. get(): This operation should provide an available phone number which is not assigned to anyone. It should return -1 if no phone numbers are available.

2. check(int number): This operation should check if a phone number is available or not. It should return true if the number is available, otherwise false.

3. release(int number): This operation should recycle or release a phone number, making it available again in the phone directory.

The directory will be initialized with a maximum number of phone numbers and each phone number will be a digit starting from 0 up to maxNumbers.

Solution Approach

In our solution, we are maintaining an array called next of size maxNumbers which stores the next available number for the directory. Initially all numbers are available, hence for each index i, next[i] is i+1. Once numbers start to be assigned and released, this array will dynamically update the next available numbers.

Our current available number is stored in the variable number. Initially it is zero.

1. When get() is called, we check if our current number is available (next[number] != -1), if not, we return -1 as no numbers are available. If it is available, we return the number, update our current number to next[number] and set next[our returned number] to -1, indicating it is not available anymore.

2. For check(int number), we simply return next[number] != -1, i.e., whether the number is available or not.

3. For release(int number), we first check if the number is already available, then do nothing. If not, we make it available by setting next[number] to our current number and then update our current number to number.

Python

1
2python
3class PhoneDirectory:
4    def __init__(self, maxNumbers):
5        self.next = [i + 1 for i in range(maxNumbers)] # initialize next array
6        self.next.append(-1) # append -1 at the end
7        self.number = 0 # current number
8
9    def get(self):
10        if self.next[self.number] == -1:
11            return -1
12        ret = self.number
13        self.number = self.next[self.number]
14        self.next[ret] = -1
15        return ret
16
17    def check(self, number):
18        return self.next[number] != -1
19
20    def release(self, number):
21        if self.next[number] != -1:
22            return
23        self.next[number] = self.number
24        self.number = number

Java

1
2java
3public class PhoneDirectory {
4    private int[] next;
5    private int number;
6
7    public PhoneDirectory(int maxNumbers) {
8        next = new int[maxNumbers];
9        for (int i = 0; i < maxNumbers; i++) {
10            next[i] = (i + 1) % maxNumbers;
11        }
12        number = 0;
13    }
14
15    public int get() {
16        if (next[number] == -1) return -1;
17        int ans = number;
18        number = next[number];
19        next[ans] = -1;
20        return ans;
21    }
22
23    public boolean check(int number) {
24        return next[number] != -1;
25    }
26
27    public void release(int number) {
28        if (next[number] != -1) return;
29        next[number] = this.number;
30        this.number = number;
31    }
32}

JavaScript

1
2javascript
3class PhoneDirectory {
4    constructor(maxNumbers) {
5        this.next = new Array(maxNumbers).fill().map((_, idx) => idx + 1);
6        this.next.push(-1);
7        this.number = 0;
8    }
9
10    get() {
11        if (this.next[this.number] === -1) return -1;
12        const ret = this.number;
13        this.number = this.next[this.number];
14        this.next[ret] = -1;
15        return ret;
16    }
17
18    check(number) {
19        return this.next[number] !== -1;
20    }
21
22    release(number) {
23        if (this.next[number] !== -1) return;
24        this.next[number] = this.number;
25        this.number = number;
26    }
27}

C++

1
2C++
3class PhoneDirectory {
4    vector<int> next;
5    int number;
6
7public:
8    PhoneDirectory(int maxNumbers) {
9        next = vector<int>(maxNumbers);
10        for (int i = 0; i < maxNumbers - 1; ++i)
11            next[i] = i + 1;
12        next.back() = 0;
13        number = 0;
14    }
15
16    int get() {
17        if (next[number] == -1)
18            return -1;
19        const int ans = number;
20        number = next[number];
21        next[ans] = -1;  // Mark as used
22        return ans;
23    }
24
25    bool check(int number) {
26        return next[number] != -1;
27    }
28
29    void release(int number) {
30        if (next[number] != -1)
31            return;
32        next[number] = this->number;
33        this->number = number;
34    }
35};

C#

1
2csharp
3public class PhoneDirectory {
4    private int[] next;
5    private int number;
6
7    public PhoneDirectory(int maxNumbers) {
8        next = new int[maxNumbers];
9        for (int i = 0; i < maxNumbers; i++)
10            next[i] = (i + 1) % maxNumbers;
11        number = 0;
12    }
13
14    public int Get() {
15        if (next[number] == -1) return -1;
16        int ans = number;
17        number = next[number];
18        next[ans] = -1;
19        return ans;
20    }
21
22    public bool Check(int number) {
23        return next[number] != -1;
24    }
25
26    public void Release(int number) {
27        if (next[number] != -1) return;
28        next[number] = this.number;
29        this.number = number;
30    }
31}

These solutions have a constant time complexity due to a single array traversal. Hence they are efficient and optimal solutions for the problem.In summary, we have successfully tackled the problem using a straightforward but effective approach. The most complex part is managing the availability of numbers in the phone directory. We accomplished this by maintaining an array which keeps track of the next available number, and accordingly updating that array whenever a number is fetched or released. This approach ensures that we can operate in constant time, making it very efficient even for large inputs. We have provided the implementation details in multiple widely-used programming languages, demonstrating how the core idea can be applied irrespective of the specific language syntax.