379. Design Phone Directory

Version I - queue + set

it will be faster to use arraydeque

public class PhoneDirectory {
    private Queue<Integer> unused;
    private Set<Integer> used;
    private int maxNumber;
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        this.maxNumber = maxNumbers;
        this.unused = new ArrayDeque<>();
        this.used = new HashSet<>();

        for (int i = 0; i < maxNumber; ++i) {
            this.unused.offer(i);
        }
    }

    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        if (unused.isEmpty()) return -1;
        int result = unused.poll();
        used.add(result);
        return result;
    }

    /** Check if a number is available or not. */
    public boolean check(int number) {
        if (number < maxNumber && !used.contains(number)) {
            return true;
        }

        return false;
    }

    /** Recycle or release a number. */
    public void release(int number) {
        if (number < maxNumber && used.contains(number)) {
            used.remove(number);
            unused.offer(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);
 */

Version II - queue + set - also o(1) in constructor

queue is for remembering released number

public class PhoneDirectory {
    private Queue<Integer> released;
    private Set<Integer> used;
    private int maxNumber;
    private int index;
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        this.maxNumber = maxNumbers;
        this.released = new ArrayDeque<>();
        this.used = new HashSet<>();
        this.index = 0;
    }

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

        if (!released.isEmpty()) {
            result = released.poll();
        } else if (index < maxNumber) {
            result = index++;
        }

        if (result != -1) {
            used.add(result);
        }

        return result;
    }

    /** Check if a number is available or not. */
    public boolean check(int number) {
        return number < maxNumber && !used.contains(number);
    }

    /** Recycle or release a number. */
    public void release(int number) {
        if (number < maxNumber && used.contains(number)) {
            used.remove(number);
            released.offer(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);
 */