379. Design Phone Directory 🔒

Description

Design a phone directory that initially has maxNumbers empty slots that can store numbers. The directory should store numbers, check if a certain slot is empty or not, and empty a given slot.

Implement the PhoneDirectory class:

• PhoneDirectory(int maxNumbers) Initializes the phone directory with the number of available slots maxNumbers.
• int get() Provides a number that is not assigned to anyone. Returns -1 if no number is available.
• bool check(int number) Returns true if the slot number is available and false otherwise.
• void release(int number) Recycles or releases the slot number.

 

Example 1:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

Explanation
PhoneDirectory phoneDirectory = new PhoneDirectory(3);
phoneDirectory.get();      // It can return any available phone number. Here we assume it returns 0.
phoneDirectory.get();      // Assume it returns 1.
phoneDirectory.check(2);   // The number 2 is available, so return true.
phoneDirectory.get();      // It returns 2, the only number that is left.
phoneDirectory.check(2);   // The number 2 is no longer available, so return false.
phoneDirectory.release(2); // Release number 2 back to the pool.
phoneDirectory.check(2);   // Number 2 is available again, return true.

 

Constraints:

• 1 <= maxNumbers <= 104
• 0 <= number < maxNumbers
• At most 2 * 104 calls will be made to get, check, and release.

Solutions

Solution 1: Hash Table

We can use a hash set available to store unallocated phone numbers. Initially, the hash set contains [0, 1, 2, ..., maxNumbers - 1].

When the get method is called, we take an unallocated phone number from available. If available is empty, we return -1. The time complexity is $O(1)$.

When the check method is called, we just need to check whether number is in available. The time complexity is $O(1)$.

When the release method is called, we add number to available. The time complexity is $O(1)$.

The space complexity is $O(n)$, where $n$ is the value of maxNumbers.

Python3JavaC++GoTypeScript

class PhoneDirectory:

    def __init__(self, maxNumbers: int):
        self.available = set(range(maxNumbers))

    def get(self) -> int:
        if not self.available:
            return -1
        return self.available.pop()

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

    def release(self, number: int) -> None:
        self.available.add(number)


# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number)

class PhoneDirectory {
    private Set<Integer> available = new HashSet<>();

    public PhoneDirectory(int maxNumbers) {
        for (int i = 0; i < maxNumbers; ++i) {
            available.add(i);
        }
    }

    public int get() {
        if (available.isEmpty()) {
            return -1;
        }
        int x = available.iterator().next();
        available.remove(x);
        return x;
    }

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

    public void release(int number) {
        available.add(number);
    }
}

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * boolean param_2 = obj.check(number);
 * obj.release(number);
 */

class PhoneDirectory {
public:
    PhoneDirectory(int maxNumbers) {
        for (int i = 0; i < maxNumbers; ++i) {
            available.insert(i);
        }
    }

    int get() {
        if (available.empty()) {
            return -1;
        }
        int x = *available.begin();
        available.erase(x);
        return x;
    }

    bool check(int number) {
        return available.contains(number);
    }

    void release(int number) {
        available.insert(number);
    }

private:
    unordered_set<int> available;
};

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory* obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj->get();
 * bool param_2 = obj->check(number);
 * obj->release(number);
 */

type PhoneDirectory struct {
    available map[int]bool
}

func Constructor(maxNumbers int) PhoneDirectory {
    available := make(map[int]bool)
    for i := 0; i < maxNumbers; i++ {
        available[i] = true
    }
    return PhoneDirectory{available}
}

func (this *PhoneDirectory) Get() int {
    for k