package medium;

public class PhoneDirectory {

    boolean[] availableNumbers;
    
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        availableNumbers = new boolean[maxNumbers];
        for(int i = 0; i < maxNumbers; i++){
            availableNumbers[i] = true;
        }
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        for(int i = 0; i < availableNumbers.length; i++){
            if(availableNumbers[i]) {
                availableNumbers[i] = false;
                return i;
            }
        }
        return -1;
    }
    
    /** Check if a number is available or not. */
    public boolean check(int number) {
        return availableNumbers[number];
    }
    
    /** Recycle or release a number. */
    public void release(int number) {
        availableNumbers[number] =true;
    }

}

@@ -14,38 +14,187 @@
 m;%0A%0A
-public class PhoneDirectory %7B%0A
+import java.util.HashSet;%0Aimport java.util.LinkedList;%0Aimport java.util.Queue;%0Aimport java.util.Set;%0A%0Apublic class PhoneDirectory %7B%0A//this runs in 669 ms, its get() method is O(n)
 %0A   
@@ -1218,8 +1218,1161 @@
    %7D%0A%0A%7D%0A
+%0Aclass PhoneDirectory_use_set %7B%0A    //this runs in 532 ms, its get() method is O(1)%0A%0A    Queue%3CInteger%3E phoneBooks;%0A    Set%3CInteger%3E used;%0A    %0A    /** Initialize your data structure here%0A        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */%0A    public PhoneDirectory_use_set(int maxNumbers) %7B%0A        phoneBooks = new LinkedList%3CInteger%3E();%0A        int number = 0;%0A        while(maxNumbers-- %3E 0)%7B%0A            phoneBooks.add(number++);%0A        %7D%0A        used = new HashSet%3CInteger%3E();%0A    %7D%0A    %0A    /** Provide a number which is not assigned to anyone.%0A        @return - Return an available number. Return -1 if none is available. */%0A    public int get() %7B%0A        if(phoneBooks.peek() == null) return -1;%0A        int number = phoneBooks.poll();%0A        used.add(number);%0A        return number;%0A    %7D%0A    %0A    /** Check if a number is available or not. */%0A    public boolean check(int number) %7B%0A        return !used.contains(number);%0A    %7D%0A    %0A    /** Recycle or release a number. */%0A    public void release(int number) %7B%0A        if(used.remove(number))%7B%0A            phoneBooks.add(number);%0A        %7D%0A    %7D%0A%0A%0A%7D

optimize phone directory to O(1) get() time