Design Phone Directory

Problem Statement

The objective is to design a phone directory system where initially there are maxNumbers empty slots that can store phone numbers. Each slot can only store one phone number at a time.

The PhoneDirectory class should be able to:

• Initialize the phone directory with a specified number of available slots.
• Provide an unassigned number which isn't already given out.
• Check the status of a specific slot (whether it is available or not).
• Recycle or release a number back into the directory to make the slot available again.

For instance:

• The constructor PhoneDirectory(int maxNumbers) sets up the directory with maxNumbers slots.
• The method int get() returns the next available number, or -1 if no numbers are available.
• The method bool check(int number) checks if a particular number is available (returns true) or not (returns false).
• The method void release(int number) releases a previously assigned number, making it available again.

These functions ensure efficient management of available and assigned phone numbers within specified limits.

Examples

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.

Approach and Intuition

Understanding the Requirements:

• The directory begins with all slots unassigned. Each slot corresponds to an integer from 0 to maxNumbers-1.
• An available number is retrieved and marked as unavailable when get() is called.
• We can check if a number is available using check(int number).
• A number can be released (made available again) using release(int number).

Example Walk-through based on the given example:

1. Initialization:

   • Instantiate the phone directory with 3 numbers. All numbers (0, 1, and 2) are initially available.

2. Get Operations:

   • Call get(): Returns 0, the first available number. Now, the available numbers are 1 and 2.
   • Call get() again: Returns 1. Now, the only available number is 2.

3. Check Operation:

   • Call check(2): Returns true since 2 is still available.

4. Get Operation:

   • Call get(): Returns 2. Now, no numbers are left. All numbers (0, 1, and 2) are assigned.

5. Check Operation:

   • Call check(2): Returns false since 2 is now assigned and not available.

6. Release Operation:

   • Call release(2): This makes number 2 available again.

7. Check Operation:

   • Call check(2): Returns true now since 2 is available again after release.

Structural Implementation Details:

• Maintain a set or list to keep track of available numbers.
• Utilize efficient data structures to ensure that operations like get, check, and release happen in reasonable time, especially given the constraints that up to 2 * 104 calls might be made.
• Handling edge cases such as releasing an already available number or getting when no numbers are available are crucial to prevent errors.

Implementing the above methods with attention to performance while effectively managing available and assigned slots will provide a robust phone directory system.

Solutions

class DirectoryService {
    unordered_set<int> availableNumbers;
    
public:
    DirectoryService(int maxNumbers) {
        for (int idx = 0; idx < maxNumbers; ++idx) {
            availableNumbers.insert(idx);
        }
    }
    
    int acquire() {
        if (availableNumbers.empty()) {
            return -1;
        }
    
        int num = *(availableNumbers.begin());
        availableNumbers.erase(num);
        return num;
    }
    
    bool isAvailable(int number) {
        return availableNumbers.find(number) != availableNumbers.end();
    }
    
    void free(int number) {
        availableNumbers.insert(number);
    }
};