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

fishercoder1534 · fishercoder1534 · commit ea1cf12be1bf · 2016-08-03T08:51:18.000-07:00
diff --git a/MEDIUM/src/medium/PhoneDirectory.java b/MEDIUM/src/medium/PhoneDirectory.java
@@ -1,7 +1,12 @@
 package medium;
 
-public class PhoneDirectory {
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Queue;
+import java.util.Set;
 
+public class PhoneDirectory {
+//this runs in 669 ms, its get() method is O(n)
     boolean[] availableNumbers;
     
     /** Initialize your data structure here
@@ -36,3 +41,44 @@ public void release(int number) {
     }
 
 }
+
+class PhoneDirectory_use_set {
+    //this runs in 532 ms, its get() method is O(1)
+
+    Queue<Integer> phoneBooks;
+    Set<Integer> used;
+    
+    /** Initialize your data structure here
+        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
+    public PhoneDirectory_use_set(int maxNumbers) {
+        phoneBooks = new LinkedList<Integer>();
+        int number = 0;
+        while(maxNumbers-- > 0){
+            phoneBooks.add(number++);
+        }
+        used = new HashSet<Integer>();
+    }
+    
+    /** Provide a number which is not assigned to anyone.
+        @return - Return an available number. Return -1 if none is available. */
+    public int get() {
+        if(phoneBooks.peek() == null) return -1;
+        int number = phoneBooks.poll();
+        used.add(number);
+        return number;
+    }
+    
+    /** Check if a number is available or not. */
+    public boolean check(int number) {
+        return !used.contains(number);
+    }
+    
+    /** Recycle or release a number. */
+    public void release(int number) {
+        if(used.remove(number)){
+            phoneBooks.add(number);
+        }
+    }
+
+
+}
