379 Design Phone Directory

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.

Example:

// 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);

The Idea: Use a 2 hash tables for reserved and free numbers. Append and erase between these two hash tables are as elements get reserved and freed.

Complexity: O(1) time, O(N) space

class PhoneDirectory {
public:
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    PhoneDirectory(int maxNumbers) {
        free.reserve(maxNumbers);
        reserved.reserve(maxNumbers);
        for (int i = 0; i < maxNumbers; i++) {
            free.insert(i);
        }
    }

    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    int get() {
        if (free.empty()) return -1;

        int get = *(free.begin());
        free.erase(get);
        reserved.insert(get);
        return get;
    }

    /** Check if a number is available or not. */
    bool check(int number) {
        return free.find(number) != free.end();
    }

    /** Recycle or release a number. */
    void release(int number) {
        reserved.erase(number);
        free.insert(number);
    }

    unordered_set<int> free, reserved;
};

/**
 * 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);
 */