Create design-phone-directory.cpp

kamyu104 · web-flow · commit 5609361cf116 · 2016-08-03T22:11:37.000+08:00
diff --git a/C++/design-phone-directory.cpp b/C++/design-phone-directory.cpp
@@ -0,0 +1,56 @@
+// init:     Time: O(n), Space: O(n)
+// get:      Time: O(1), Space: O(1)
+// check:    Time: O(1), Space: O(1)
+// release:  Time: O(1), Space: O(1)
+
+class PhoneDirectory {
+public:
+    /** Initialize your data structure here
+        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
+    PhoneDirectory(int maxNumbers) :
+        curr_(0), numbers_(maxNumbers), used_(maxNumbers) {  // Time: O(n), Space: O(n)
+
+        iota(numbers_.begin(), numbers_.end(), 0);
+    }
+    
+    /** Provide a number which is not assigned to anyone.
+        @return - Return an available number. Return -1 if none is available. */
+    int get() { // Time: O(1), Space: O(1)
+        if (curr_ == numbers_.size()) {
+            return -1;
+        }
+        const auto number = numbers_[curr_++];
+        used_[number] = true;
+        return number;
+    }
+    
+    /** Check if a number is available or not. */
+    bool check(int number) { // Time: O(1), Space: O(1)
+        if (number < 0 || number >= numbers_.size()) {
+            return false;
+        }
+        return !used_[number];
+    }
+    
+    /** Recycle or release a number. */
+    void release(int number) { // Time: O(1), Space: O(1)
+        if (number < 0 || number >= numbers_.size() || !used_[number]) {
+            return;
+        }
+        used_[number] = false;
+        numbers_[--curr_] = number ;
+    }
+
+private:
+    int curr_;
+    vector<int> numbers_;
+    vector<bool> used_;
+};
+
+/**
+ * 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);
+ */
