Initial commit.HEADmain

2 files changed, 97 insertions, 0 deletions

diff --git a/top-interview-questions/easy/design/01_shuffle_an_array.cc b/top-interview-questions/easy/design/01_shuffle_an_array.cc
new file mode 100644
index 0000000..5c40d60
--- /dev/null
+++ b/top-interview-questions/easy/design/01_shuffle_an_array.cc
@@ -0,0 +1,41 @@
+class Solution {
+public:
+    Solution(vector<int>& nums)
+      : m_original(nums) {}
+
+    vector<int> reset() {
+        return m_original;
+    }
+
+    vector<int> shuffle() {
+        std::vector<int> shuffled = m_original;
+        for (size_t i = 0; i < shuffled.size(); ++i) {
+            const size_t j = random() % shuffled.size();
+            std::swap(shuffled[i], shuffled[j]);
+        }
+        return shuffled;
+    }
+
+private:
+    size_t random() {
+        uint64_t x = m_random;
+
+        // xorshift64
+        x ^= x << 13;
+        x ^= x >> 7;
+        x ^= x << 17;
+
+        m_random = x;
+        return x;
+    }
+
+    std::vector<int> m_original;
+    std::uint64_t    m_random = 16240738485554559101;
+};
+
+/**
+ * Your Solution object will be instantiated and called as such:
+ * Solution* obj = new Solution(nums);
+ * vector<int> param_1 = obj->reset();
+ * vector<int> param_2 = obj->shuffle();
+ */
diff --git a/top-interview-questions/easy/design/02_min_stack.cc b/top-interview-questions/easy/design/02_min_stack.cc
new file mode 100644
index 0000000..1bcb36a
--- /dev/null
+++ b/top-interview-questions/easy/design/02_min_stack.cc
@@ -0,0 +1,56 @@
+class MinStack {
+public:
+    MinStack() {}
+
+    void push(int val) {
+        const int minVal = (m_minStack != nullptr) ? std::min(m_minStack->val, val) : val;
+        Node* top    = new Node{m_stack,    val};
+        Node* minTop = new Node{m_minStack, minVal};
+        m_stack      = top;
+        m_minStack   = minTop;
+    }
+
+    void pop() {
+        assertNonEmpty();
+        Node* top    = m_stack;
+        Node* minTop = m_minStack;
+        m_stack      = m_stack->next;
+        m_minStack   = m_minStack->next;
+        delete top;
+        delete minTop;
+    }
+
+    int top() {
+        assertNonEmpty();
+        return m_stack->val;
+    }
+
+    int getMin() {
+        assertNonEmpty();
+        return m_minStack->val;
+    }
+
+private:
+    struct Node {
+        Node* next;
+        int   val;
+    };
+
+    void assertNonEmpty() const {
+        if (m_stack == nullptr) {
+            throw "empty stack";
+        }
+    }
+
+    Node* m_stack    = nullptr; // The actual stack.
+    Node* m_minStack = nullptr; // Stack of mins.
+};
+
+/**
+ * Your MinStack object will be instantiated and called as such:
+ * MinStack* obj = new MinStack();
+ * obj->push(val);
+ * obj->pop();
+ * int param_3 = obj->top();
+ * int param_4 = obj->getMin();
+ */