Initial commit.HEADmain

35 files changed, 1139 insertions, 0 deletions

diff --git a/top-interview-questions/easy/array/01_remove_duplicates_from_sorted_array.cc b/top-interview-questions/easy/array/01_remove_duplicates_from_sorted_array.cc
new file mode 100644
index 0000000..8f5224b
--- /dev/null
+++ b/top-interview-questions/easy/array/01_remove_duplicates_from_sorted_array.cc
@@ -0,0 +1,13 @@
+class Solution {
+public:
+    int removeDuplicates(vector<int>& nums) {
+        size_t i = nums.size() > 0 ? 1 : 0;
+        for (size_t j = 1; j < nums.size(); ++j) {
+            if (nums[j] != nums[i-1]) {
+                nums[i++] = nums[j];
+            }
+        }
+        nums.resize(i);
+        return i;
+    }
+};
diff --git a/top-interview-questions/easy/array/02_best_time_to_buy_and_sell_stock_2.cc b/top-interview-questions/easy/array/02_best_time_to_buy_and_sell_stock_2.cc
new file mode 100644
index 0000000..abc4aa9
--- /dev/null
+++ b/top-interview-questions/easy/array/02_best_time_to_buy_and_sell_stock_2.cc
@@ -0,0 +1,24 @@
+class Solution {
+public:
+    int maxProfit(vector<int>& prices) {
+        int profit = 0;
+        int buy    = -1;
+        int sell   = -1;
+        for (size_t day = 0; day < prices.size(); ++day) {
+            if ((sell == -1) &&
+                ((buy == -1) || (prices[day] < buy))) {
+                buy = prices[day];
+            } else if ((sell == -1) || (prices[day] > sell)) {
+                sell = prices[day];
+            } else {
+                profit += sell - buy;
+                buy  = prices[day];
+                sell = -1;
+            }
+        }
+        if (buy < sell) {
+            profit += sell - buy;
+        }
+        return profit;
+    }
+};
diff --git a/top-interview-questions/easy/array/03_rotate_array.cc b/top-interview-questions/easy/array/03_rotate_array.cc
new file mode 100644
index 0000000..19f66dd
--- /dev/null
+++ b/top-interview-questions/easy/array/03_rotate_array.cc
@@ -0,0 +1,39 @@
+class Solution {
+public:
+    // Works, but it's slow.
+    /*int gcd(int a, int b) {
+        if (a == 0) return b;
+        if (b == 0) return a;
+        if (a == b) return a;
+        if (a  > b) return gcd(a-b, b);
+        else        return gcd(a, b-a);
+    }*/
+
+    // Much faster than the above implementation.
+    int gcd(int a, int b) {
+        if (b == 0) return a;
+        else        return gcd(b, a%b);
+    }
+
+    void rotate(vector<int>& nums, int k) {
+        const size_t N = nums.size();
+        if ((N <= 1) || (k == 0)) {
+            return;
+        }
+        // Original algorithm only works for (N,k) coprime.
+        // Break the cycles when we complete a loop around the array.
+        const int gcdNk = gcd(N,k);
+        const int steps = (gcdNk != 1) ? (N / gcdNk) : N;
+        int start = -1;
+        for (size_t n = 0; n < N; n += steps) {
+            ++start;
+            int i = start;
+            int i_val = nums[i];
+            for (size_t s = 0; s < steps; ++s) {
+                const int next = (i+k) % N;
+                std::swap(i_val, nums[next]);
+                i = next;
+            }
+        }
+    }
+};
diff --git a/top-interview-questions/easy/array/04_contains_duplicate.cc b/top-interview-questions/easy/array/04_contains_duplicate.cc
new file mode 100644
index 0000000..d40d1e4
--- /dev/null
+++ b/top-interview-questions/easy/array/04_contains_duplicate.cc
@@ -0,0 +1,14 @@
+class Solution {
+public:
+    bool containsDuplicate(vector<int>& nums) {
+        std::sort(nums.begin(), nums.end());
+
+        for (size_t i = 1; i < nums.size(); ++i) {
+            if (nums[i-1] == nums[i]) {
+                return true;
+            }
+        }
+
+        return false;
+    }
+};
diff --git a/top-interview-questions/easy/array/05_single_number.cc b/top-interview-questions/easy/array/05_single_number.cc
new file mode 100644
index 0000000..ad55712
--- /dev/null
+++ b/top-interview-questions/easy/array/05_single_number.cc
@@ -0,0 +1,10 @@
+class Solution {
+public:
+    int singleNumber(vector<int>& nums) {
+        int x = 0;
+        for (int n : nums) {
+            x = x ^ n;
+        }
+        return x;
+    }
+};
diff --git a/top-interview-questions/easy/array/06_intersection_of_two_arrays_II.cc b/top-interview-questions/easy/array/06_intersection_of_two_arrays_II.cc
new file mode 100644
index 0000000..0921be8
--- /dev/null
+++ b/top-interview-questions/easy/array/06_intersection_of_two_arrays_II.cc
@@ -0,0 +1,27 @@
+class Solution {
+public:
+    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
+        std::sort(nums1.begin(), nums1.end());
+        std::sort(nums2.begin(), nums2.end());
+
+        std::vector<int> result;
+        result.reserve(std::max(nums1.size(), nums2.size()));
+
+        size_t i = 0;
+        size_t j = 0;
+
+        while ((i < nums1.size()) && (j < nums2.size())) {
+            if (nums1[i] == nums2[j]) {
+                result.push_back(nums1[i]);
+                ++i;
+                ++j;
+            } else if (nums1[i] < nums2[j]) {
+                ++i;
+            } else {
+                ++j;
+            }
+        }
+
+        return result;
+    }
+};
diff --git a/top-interview-questions/easy/array/07_plus_one.cc b/top-interview-questions/easy/array/07_plus_one.cc
new file mode 100644
index 0000000..05c7b21
--- /dev/null
+++ b/top-interview-questions/easy/array/07_plus_one.cc
@@ -0,0 +1,25 @@
+class Solution {
+public:
+    vector<int> plusOne(vector<int>& digits) {
+        int carry = 1;
+
+        for (int i = digits.size()-1; (i >= 0) && (carry == 1); --i) {
+            const int sum = digits[i] + carry;
+            digits[i] = sum % 10;
+            carry     = (sum >= 10) ? 1 : 0;
+        }
+
+        if (carry == 1) { // Overflow.
+            digits.resize(digits.size() + 1);
+
+            // Shift right.
+            for (size_t i = digits.size()-1; i > 0; --i) {
+                digits[i] = digits[i-1];
+            }
+
+            digits[0] = 1;
+        }
+
+        return digits;
+    }
+};
diff --git a/top-interview-questions/easy/array/08_move_zeroes.cc b/top-interview-questions/easy/array/08_move_zeroes.cc
new file mode 100644
index 0000000..074944c
--- /dev/null
+++ b/top-interview-questions/easy/array/08_move_zeroes.cc
@@ -0,0 +1,23 @@
+class Solution {
+public:
+    void moveZeroes(vector<int>& nums) {
+        // Invariant: left subset of array satisfies requirement.
+        bool sorted = false;
+        for (size_t i = 0; (i < nums.size()) && !sorted; ++i) {
+            if (nums[i] == 0) {
+                // Look for j>i with which to swap this 0.
+                // If not found, then we're done.
+                bool found = false;
+                for (size_t j = i+1; j < nums.size(); ++j) {
+                    if (nums[j] != 0) {
+                        nums[i] = nums[j];
+                        nums[j] = 0;
+                        found = true;
+                        break;
+                    }
+                }
+                sorted = !found;
+            }
+        }
+    }
+};
diff --git a/top-interview-questions/easy/array/09_two_sum.cc b/top-interview-questions/easy/array/09_two_sum.cc
new file mode 100644
index 0000000..72d2014
--- /dev/null
+++ b/top-interview-questions/easy/array/09_two_sum.cc
@@ -0,0 +1,24 @@
+class Solution {
+public:
+    vector<int> twoSum(vector<int>& nums, int target) {
+        // When you find, e.g., 2, map (2 -> idx 0) for the event
+        // in which you find the 7.
+        std::vector<int> pair(2);
+        std::unordered_map<int, int> val_to_idx;
+
+        for (size_t i = 0; i < nums.size(); ++i) {
+            const int other = target - nums[i];
+            const auto other_idx = val_to_idx.find(other);
+
+            if (other_idx != val_to_idx.end()) {
+                pair[0] = i;
+                pair[1] = other_idx->second;
+                break;
+            }
+
+            val_to_idx[nums[i]] = i;
+        }
+
+        return pair;
+    }
+};
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();
+ */
diff --git a/top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc b/top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc
new file mode 100644
index 0000000..19aa6a1
--- /dev/null
+++ b/top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc
@@ -0,0 +1,22 @@
+class Solution {
+public:
+    int climbStairs(int n) {
+        /*
+        ways(n-1, n) = 1                            -- one step to n
+        ways(n-2, n) = 1 + 1                        -- 1x two-step + 2x one-step
+        ways(  k, n) = ways(k-1, n) + ways(k-2, n)
+        */
+        if (n == 1) return 1;
+        if (n == 2) return 2;
+
+        int ways_n_1 = 1; // ways(n-1, n)
+        int ways_n_2 = 2; // ways(n-2, n)
+        for (int i = n-3; i >= 0; --i) {
+            const int ways_n_3 = ways_n_1 + ways_n_2;
+            // Update
+            ways_n_1 = ways_n_2;
+            ways_n_2 = ways_n_3;
+        }
+        return ways_n_2;
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/01_delete_node_in_a_linked_list.cc b/top-interview-questions/easy/linked_list/01_delete_node_in_a_linked_list.cc
new file mode 100644
index 0000000..47f9559
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/01_delete_node_in_a_linked_list.cc
@@ -0,0 +1,22 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode(int x) : val(x), next(NULL) {}
+ * };
+ */
+class Solution {
+public:
+    void deleteNode(ListNode* node) {
+        while (node) {
+            if (node->next) {
+                node->val = node->next->val;
+                if (!node->next->next) {
+                    node->next = NULL;
+                }
+            }
+            node = node->next;
+        }
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/02_remove_nth_node_from_end_of_list.cc b/top-interview-questions/easy/linked_list/02_remove_nth_node_from_end_of_list.cc
new file mode 100644
index 0000000..6773f04
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/02_remove_nth_node_from_end_of_list.cc
@@ -0,0 +1,32 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    // Return the number of elements in the list.
+    int removeNth(ListNode* node, int n) {
+        if (!node) {
+            return 0;
+        }
+        const int tailLength = removeNth(node->next, n);
+        if (tailLength == n) {
+            node->next = node->next->next;
+        }
+        return tailLength + 1;
+    }
+
+    ListNode* removeNthFromEnd(ListNode* head, int n) {
+        const int listLength = removeNth(head, n);
+        if (listLength == n) {
+            head = head->next;
+        }
+        return head;
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/03_reverse_linked_list.cc b/top-interview-questions/easy/linked_list/03_reverse_linked_list.cc
new file mode 100644
index 0000000..d97bd33
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/03_reverse_linked_list.cc
@@ -0,0 +1,26 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    // Reverse the list and return the head of the new list.
+    ListNode* reverse(ListNode* node) {
+        if (!node)       { return nullptr; }
+        if (!node->next) { return node; }
+        ListNode* head = reverse(node->next);
+        node->next->next = node;
+        node->next = nullptr;
+        return head;
+    }
+
+    ListNode* reverseList(ListNode* head) {
+        return reverse(head);
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/04_merge_two_sorted_lists.cc b/top-interview-questions/easy/linked_list/04_merge_two_sorted_lists.cc
new file mode 100644
index 0000000..9724ef0
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/04_merge_two_sorted_lists.cc
@@ -0,0 +1,52 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
+        ListNode* mergedHead = nullptr;
+        ListNode* merged     = nullptr;
+        while (list1 && list2) {
+            if (list1->val <= list2->val) {
+                if (merged) {
+                    merged->next = list1;
+                    merged = merged->next;
+                } else {
+                    merged = list1;
+                    mergedHead = merged;
+                }
+                list1 = list1->next;
+            } else {
+                if (merged) {
+                    merged->next = list2;
+                    merged = merged->next;
+                } else {
+                    merged = list2;
+                    mergedHead = merged;
+                }
+                list2 = list2->next;
+            }
+        }
+        if (list1) {
+            if (merged) {
+                merged->next = list1;
+            } else {
+                mergedHead = list1;
+            }
+        } else if (list2) {
+            if (merged) {
+                merged->next = list2;
+            } else {
+                mergedHead = list2;
+            }
+        }
+        return mergedHead;
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/05_palindrome_linked_list.cc b/top-interview-questions/easy/linked_list/05_palindrome_linked_list.cc
new file mode 100644
index 0000000..3f42e4a
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/05_palindrome_linked_list.cc
@@ -0,0 +1,48 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    // Copy the list.
+    ListNode* clone(const ListNode* node) {
+        if (!node) return nullptr;
+        ListNode* copy = new ListNode();
+        copy->val = node->val;
+        if (node->next) {
+            copy->next = clone(node->next);
+        } else {
+            copy->next = nullptr;
+        }
+        return copy;
+    }
+
+    // Reverse a list and return the new of the reversed list.
+    ListNode* reverse(ListNode* node) {
+        if (!node)       return nullptr;
+        if (!node->next) return node;
+        ListNode* head = reverse(node->next);
+        node->next->next = node;
+        node->next = nullptr;
+        return head;
+    }
+
+    // Compare two lists for equality.
+    bool eq(const ListNode* a, const LideNode* b) {
+        if (!a && !b)         return true;
+        if (!a)               return false;
+        if (!b)               return false;
+        if (a->val != b->val) return false;
+        return eq(a->next, b->next);
+    }
+
+    bool isPalindrome(ListNode* head) {
+        return eq(head, reverse(clone(head)));
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/05_palindrome_linked_list_2.cc b/top-interview-questions/easy/linked_list/05_palindrome_linked_list_2.cc
new file mode 100644
index 0000000..590c485
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/05_palindrome_linked_list_2.cc
@@ -0,0 +1,63 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode() : val(0), next(nullptr) {}
+ *     ListNode(int x) : val(x), next(nullptr) {}
+ *     ListNode(int x, ListNode *next) : val(x), next(next) {}
+ * };
+ */
+class Solution {
+public:
+    // Return the length of the list.
+    size_t length(const ListNode* node) {
+        if (!node) return 0;
+        return 1 + length(node->next);
+    }
+
+    // Return the nth element of the list.
+    const ListNode* nth(const ListNode* node, size_t n) {
+        if (!node)  return nullptr;
+        if (n == 0) return node;
+        return nth(node->next, n-1);
+    }
+
+    // Reverse the list up to, and not including, the nth element.
+    // Return the head of the reversed list (nth-1 node).
+    ListNode* reverse(ListNode* node, size_t n) {
+        if (!node)       return nullptr;
+        if (!node->next) return node;
+        if (n == 1) {
+            node->next = nullptr;
+            return node;
+        }
+
+        ListNode* head = reverse(node->next, n-1);
+        node->next->next = node;
+        node->next = nullptr;
+        return head;
+    }
+
+    // Compare two lists for equality.
+    bool eq(const ListNode* a, const ListNode* b) {
+        if (!a && !b)         return true;
+        if (!a)               return false;
+        if (!b)               return false;
+        if (a->val != b->val) return false;
+        return eq(a->next, b->next);
+    }
+
+    bool isPalindrome(ListNode* head) {
+        if (!head)       return true;
+        if (!head->next) return true;
+
+        // If odd,  get the middle element.
+        // If even, get the first element of the second half.
+        const size_t len      = length(head);
+        const size_t middle   = len/2;
+        const ListNode* head1 = nth(head, middle + (len & 1));
+        const ListNode* head2 = reverse(head, middle);
+        return eq(head1, head2);
+    }
+};
diff --git a/top-interview-questions/easy/linked_list/06_linked_list_cycle.cc b/top-interview-questions/easy/linked_list/06_linked_list_cycle.cc
new file mode 100644
index 0000000..e8b4d1d
--- /dev/null
+++ b/top-interview-questions/easy/linked_list/06_linked_list_cycle.cc
@@ -0,0 +1,29 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode(int x) : val(x), next(NULL) {}
+ * };
+ */
+class Solution {
+public:
+    bool hasCycle(ListNode *head) {
+        if (!head)       return false;
+        if (!head->next) return false;
+
+        const ListNode* next1 = head;
+        const ListNode* next2 = head;
+
+        do {
+            next1 = next1->next;
+            next2 = next2->next;
+            if (next2) {
+                next2 = next2->next;
+            }
+        }
+        while ((next1 != head) && next1 && next2 && (next1 != next2));
+
+        return next1 && next2 && (next1 == next2);
+    }
+};
diff --git a/top-interview-questions/easy/others/05_valid_parentheses.cc b/top-interview-questions/easy/others/05_valid_parentheses.cc
new file mode 100644
index 0000000..3f6d020
--- /dev/null
+++ b/top-interview-questions/easy/others/05_valid_parentheses.cc
@@ -0,0 +1,41 @@
+class Solution {
+public:
+    char matchingChar(char c) {
+        switch (c) {
+            case ')': return '(';
+            case '}': return '{';
+            case ']': return '[';
+            default: throw;
+        }
+    }
+
+    bool isValid(string s) {
+        // ([])  -- valid
+        // ([)]  -- invalid
+        std::stack<char> st;
+        for (char c : s) {
+            switch (c) {
+                case '(':
+                case '{':
+                case '[': {
+                    st.push(c);
+                    break;
+                }
+                case ')':
+                case '}':
+                case ']': {
+                    const char expected = matchingChar(c);
+                    if (st.empty() ||
+                        (st.top() != expected)) {
+                        return false;
+                    }
+                    st.pop();
+                    break;
+                }
+                default:
+                    throw;
+            }
+        }
+        return st.empty();
+    }
+};
diff --git a/top-interview-questions/easy/others/06_missing_number.cc b/top-interview-questions/easy/others/06_missing_number.cc
new file mode 100644
index 0000000..0487bcc
--- /dev/null
+++ b/top-interview-questions/easy/others/06_missing_number.cc
@@ -0,0 +1,13 @@
+class Solution {
+public:
+    int missingNumber(vector<int>& nums) {
+        const size_t expectedSum = nums.size() * (nums.size()+1) / 2;
+
+        size_t sum = 0;
+        for (int x : nums) {
+            sum += x;
+        }
+
+        return expectedSum - sum;
+    }
+};
diff --git a/top-interview-questions/easy/sorting_and_searching/01_merge_sorted_array.cc b/top-interview-questions/easy/sorting_and_searching/01_merge_sorted_array.cc
new file mode 100644
index 0000000..9abb974
--- /dev/null
+++ b/top-interview-questions/easy/sorting_and_searching/01_merge_sorted_array.cc
@@ -0,0 +1,24 @@
+class Solution {
+public:
+    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
+        int i = m-1;
+        int j = n-1;
+        int k = n+m-1;
+
+        while ((i >= 0) && (j >= 0)) {
+            if (nums1[i] >= nums2[j]) {
+                nums1[k--] = nums1[i--];
+            } else {
+                nums1[k--] = nums2[j--];
+            }
+        }
+
+        while (i >= 0) {
+            nums1[k--] = nums1[i--];
+        }
+
+        while (j >= 0) {
+            nums1[k--] = nums2[j--];
+        }
+    }
+};
diff --git a/top-interview-questions/easy/sorting_and_searching/02_first_bad_version.cc b/top-interview-questions/easy/sorting_and_searching/02_first_bad_version.cc
new file mode 100644
index 0000000..15e2504
--- /dev/null
+++ b/top-interview-questions/easy/sorting_and_searching/02_first_bad_version.cc
@@ -0,0 +1,21 @@
+// The API isBadVersion is defined for you.
+// bool isBadVersion(int version);
+
+class Solution {
+public:
+    int FirstBad(int left, int right) {
+        if (left == right) {
+            return left;
+        }
+        const int mid = left + (right - left) / 2;
+        if (isBadVersion(mid)) {
+            return FirstBad(left, mid);
+        } else {
+            return FirstBad(mid+1, right);
+        }
+    }
+
+    int firstBadVersion(int n) {
+        return FirstBad(1, n);
+    }
+};
diff --git a/top-interview-questions/easy/strings/03_first_unique_character.cc b/top-interview-questions/easy/strings/03_first_unique_character.cc
new file mode 100644
index 0000000..871f761
--- /dev/null
+++ b/top-interview-questions/easy/strings/03_first_unique_character.cc
@@ -0,0 +1,18 @@
+class Solution {
+public:
+    int firstUniqChar(string s) {
+        int count[256] = {};
+
+        for (char c : s) {
+            count[c]++;
+        }
+
+        for (size_t i = 0; i < s.size(); ++i) {
+            if (count[s[i]] == 1) {
+                return i;
+            }
+        }
+
+        return -1;
+    }
+};
diff --git a/top-interview-questions/easy/strings/04_valid_anagram.cc b/top-interview-questions/easy/strings/04_valid_anagram.cc
new file mode 100644
index 0000000..3ca6b7c
--- /dev/null
+++ b/top-interview-questions/easy/strings/04_valid_anagram.cc
@@ -0,0 +1,29 @@
+class Solution {
+public:
+    static void count(const string& s, int* counts) {
+        for (char c : s) {
+            counts[c]++;
+        }
+    }
+
+    bool isAnagram(string s, string t) {
+        if (s.size() != t.size()) {
+            return false;
+        }
+        // strings are equal length
+
+        int sCount[256] = {};
+        int tCount[256] = {};
+
+        count(s, sCount);
+        count(t, tCount);
+
+        for (char c : s) {
+            if (sCount[c] != tCount[c]) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+};
diff --git a/top-interview-questions/easy/strings/05_valid_palindrome.cc b/top-interview-questions/easy/strings/05_valid_palindrome.cc
new file mode 100644
index 0000000..1b4ca6f
--- /dev/null
+++ b/top-interview-questions/easy/strings/05_valid_palindrome.cc
@@ -0,0 +1,30 @@
+class Solution {
+public:
+    bool IsAlphaNum(char c) {
+        return
+            (('a' <= c) && (c <= 'z')) ||
+            (('A' <= c) && (c <= 'Z')) ||
+            (('0' <= c) && (c <= '9'));
+    }
+
+    void Transform(string& s) {
+        size_t j = 0;
+        for (size_t i = 0; i < s.size(); ++i) {
+            if (IsAlphaNum(s[i])) {
+                s[j] = std::tolower(s[i]);
+                j++;
+            }
+        }
+        s.resize(j);
+    }
+
+    bool isPalindrome(string s) {
+        Transform(s);
+        for (size_t i = 0; i < s.size()/2; ++i) {
+            if (s[i] != s[s.size()-i-1]) {
+                return false;
+            }
+        }
+        return true;
+    }
+};
diff --git a/top-interview-questions/easy/trees/01_maximum_depth_of_binary_tree.cc b/top-interview-questions/easy/trees/01_maximum_depth_of_binary_tree.cc
new file mode 100644
index 0000000..4d13af7
--- /dev/null
+++ b/top-interview-questions/easy/trees/01_maximum_depth_of_binary_tree.cc
@@ -0,0 +1,20 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    int max(int a, int b) { return a > b ? a : b; }
+
+    int maxDepth(TreeNode* root) {
+        if (!root) return 0;
+        return 1 + max(maxDepth(root->left), maxDepth(root->right));
+    }
+};
diff --git a/top-interview-questions/easy/trees/02_valid_binary_search_tree.cc b/top-interview-questions/easy/trees/02_valid_binary_search_tree.cc
new file mode 100644
index 0000000..a071daf
--- /dev/null
+++ b/top-interview-questions/easy/trees/02_valid_binary_search_tree.cc
@@ -0,0 +1,54 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    bool isValidBSTRec(TreeNode* root, int* min, int* max) {
+        if (root->left && root->right) {
+            int leftMin, leftMax, rightMin, rightMax;
+            if (!isValidBSTRec(root->left,  &leftMin,  &leftMax) ||
+                !isValidBSTRec(root->right, &rightMin, &rightMax)) {
+                return false;
+            }
+            *min = std::min(std::min(leftMin, rightMin), root->val);
+            *max = std::max(std::max(leftMax, rightMax), root->val);
+            return (leftMax < root->val) && (root->val < rightMin);
+        }
+        else if (root->left) {
+            int leftMin, leftMax;
+            if (!isValidBSTRec(root->left, &leftMin, &leftMax)) {
+                return false;
+            }
+            *min = std::min(leftMin, root->val);
+            *max = std::max(leftMax, root->val);
+            return (leftMax < root->val);
+        }
+        else if (root->right) {
+            int rightMin, rightMax;
+            if (!isValidBSTRec(root->right, &rightMin, &rightMax)) {
+                return false;
+            }
+            *min = std::min(rightMin, root->val);
+            *max = std::max(rightMax, root->val);
+            return (root->val < rightMin);
+        }
+        else {
+            *min = *max = root->val;
+            return true;
+        }
+    }
+
+    bool isValidBST(TreeNode* root) {
+        if (!root) return true;
+        int minVal, maxVal;
+        return isValidBSTRec(root, &minVal, &maxVal);
+    }
+};
diff --git a/top-interview-questions/easy/trees/03_symmetric_tree.cc b/top-interview-questions/easy/trees/03_symmetric_tree.cc
new file mode 100644
index 0000000..bbdc52b
--- /dev/null
+++ b/top-interview-questions/easy/trees/03_symmetric_tree.cc
@@ -0,0 +1,52 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    bool isSymmetricVector(const std::vector<const TreeNode*>& nodes) {
+        if (nodes.empty())     return true;
+        if (nodes.size() == 1) return true;
+        for (size_t i = 0; i < nodes.size()/2; ++i) {
+            const size_t j = nodes.size() - i - 1;
+            if ((nodes[i]  && !nodes[j]) ||
+                (!nodes[i] && nodes[j]) ||
+                (nodes[i]  && nodes[j] && (nodes[i]->val != nodes[j]->val))) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    bool isSymmetricBfs(std::vector<const TreeNode*>& current_level,
+                        std::vector<const TreeNode*>& next_level) {
+        if (current_level.empty()) {
+            return true;
+        }
+        if (!isSymmetricVector(current_level)) {
+            return false;
+        }
+        for (const TreeNode* node : current_level) {
+            if (node) {
+                next_level.push_back(node->left);
+                next_level.push_back(node->right);
+            }
+        }
+        current_level.clear(); // New next level.
+        return isSymmetricBfs(next_level, current_level);
+    }
+
+    bool isSymmetric(TreeNode* root) {
+        if (!root) return true;
+        std::vector<const TreeNode*> current_level({root});
+        std::vector<const TreeNode*> next_level;
+        return isSymmetricBfs(current_level, next_level);
+    }
+};
diff --git a/top-interview-questions/easy/trees/04_binary_tree_level_order_traversal.cc b/top-interview-questions/easy/trees/04_binary_tree_level_order_traversal.cc
new file mode 100644
index 0000000..9c506ab
--- /dev/null
+++ b/top-interview-questions/easy/trees/04_binary_tree_level_order_traversal.cc
@@ -0,0 +1,44 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    void bfs(vector<vector<int>>& levels,
+             vector<const TreeNode*>& current_level,
+             vector<const TreeNode*>& next_level) {
+        if (current_level.empty()) {
+            return;
+        }
+        levels.push_back({});
+        vector<int>& level = levels.back();
+        level.reserve(current_level.size());
+        for (const TreeNode* node : current_level) {
+            level.push_back(node->val);
+            if (node->left) {
+                next_level.push_back(node->left);
+            }
+            if (node->right) {
+                next_level.push_back(node->right);
+            }
+        }
+        current_level.clear(); // New next level.
+        bfs(levels, next_level, current_level);
+    }
+
+    vector<vector<int>> levelOrder(TreeNode* root) {
+        if (!root) return {};
+        vector<vector<int>> levels;
+        vector<const TreeNode*> current_level({root});
+        vector<const TreeNode*> next_level;
+        bfs(levels, current_level, next_level);
+        return levels;
+    }
+};
diff --git a/top-interview-questions/easy/trees/05_convert_sorted_array_to_binary_search_tree.cc b/top-interview-questions/easy/trees/05_convert_sorted_array_to_binary_search_tree.cc
new file mode 100644
index 0000000..4882a2a
--- /dev/null
+++ b/top-interview-questions/easy/trees/05_convert_sorted_array_to_binary_search_tree.cc
@@ -0,0 +1,27 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    // 'end' is one past the end.
+    TreeNode* makeTree(const vector<int>& nums, size_t start, size_t end) {
+        if (start >= end) return nullptr;
+        const size_t middle = start + (end - start) / 2;
+        TreeNode* root = new TreeNode(nums[middle]);
+        root->left  = makeTree(nums, start, middle);
+        root->right = makeTree(nums, middle+1, end);
+        return root;
+    }
+
+    TreeNode* sortedArrayToBST(vector<int>& nums) {
+        return makeTree(nums, 0, nums.size());
+    }
+};
diff --git a/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc b/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc
new file mode 100644
index 0000000..6a2762b
--- /dev/null
+++ b/top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc
@@ -0,0 +1,27 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    void inorder(TreeNode* node, vector<int>& vals) {
+        if (node == nullptr) return;
+
+        inorder(node->left, vals);
+        vals.push_back(node->val);
+        inorder(node->right, vals);
+    }
+
+    vector<int> inorderTraversal(TreeNode* root) {
+        vector<int> vals;
+        inorder(root, vals);
+        return vals;
+    }
+};
diff --git a/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc b/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc
new file mode 100644
index 0000000..2abb093
--- /dev/null
+++ b/top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc
@@ -0,0 +1,53 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    void push(vector<const TreeNode*>& level, vector<int>& values, const TreeNode* node) {
+        level.push_back(node);
+        values.push_back(node->val);
+    }
+
+    void zigZag(bool leftRight, const vector<const TreeNode*>& level, vector<vector<int>>& values) {
+        vector<const TreeNode*> next_level;
+        vector<int>             next_values;
+
+        if (leftRight) {
+            for (int i = level.size()-1; i >= 0; --i) {
+                const TreeNode* node = level[i];
+                if (node->left)  push(next_level, next_values, node->left);
+                if (node->right) push(next_level, next_values, node->right);
+            }
+        }
+        else {
+            for (int i = level.size()-1; i >= 0; --i) {
+                const TreeNode* node = level[i];
+                if (node->right) push(next_level, next_values, node->right);
+                if (node->left)  push(next_level, next_values, node->left);
+            }
+        }
+
+        if (!next_level.empty()) {
+            values.push_back(next_values);
+            zigZag(!leftRight, next_level, values);
+        }
+    }
+
+    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
+        if (root == nullptr) return {};
+
+        vector<const TreeNode*> level  = {root};
+        vector<vector<int>>     values = {{root->val}};
+
+        zigZag(false, level, values);
+        return values;
+    }
+};
diff --git a/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc b/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc
new file mode 100644
index 0000000..95e3655
--- /dev/null
+++ b/top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc
@@ -0,0 +1,49 @@
+/**
+ * Definition for a binary tree node.
+ * struct TreeNode {
+ *     int val;
+ *     TreeNode *left;
+ *     TreeNode *right;
+ *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
+ *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
+ * };
+ */
+class Solution {
+public:
+    TreeNode* build(const vector<int>& preorder, const vector<int>& inorder,
+                    int& preIdx, int leftIdx, int rightIdx) {
+        // Base case.
+        if (leftIdx > rightIdx) {
+            return nullptr;
+        }
+
+        // Root value.
+        const int root = preorder[preIdx++];
+
+        // Base case.
+        if (leftIdx == rightIdx) {
+            return new TreeNode{root, nullptr, nullptr};
+        }
+        // Recursive case.
+        else {
+            // Find the root in the inorder array.
+            int inorderRootIdx = -1;
+            for (int i = 0; i < inorder.size(); ++i) {
+                if (inorder[i] == root) {
+                    inorderRootIdx = i;
+                    break;
+                }
+            }
+            // Build recursively.
+            TreeNode* left  = build(preorder, inorder, preIdx, leftIdx, inorderRootIdx-1);
+            TreeNode* right = build(preorder, inorder, preIdx, inorderRootIdx+1, rightIdx);
+            return new TreeNode{root, left, right};
+        }
+    }
+
+    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
+        int preIdx = 0;
+        return build(preorder, inorder, preIdx, 0, preorder.size()-1);
+    }
+};
diff --git a/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc b/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc
new file mode 100644
index 0000000..17a5874
--- /dev/null
+++ b/top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc
@@ -0,0 +1,47 @@
+/*
+// Definition for a Node.
+class Node {
+public:
+    int val;
+    Node* left;
+    Node* right;
+    Node* next;
+
+    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
+
+    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
+
+    Node(int _val, Node* _left, Node* _right, Node* _next)
+        : val(_val), left(_left), right(_right), next(_next) {}
+};
+*/
+
+class Solution {
+public:
+    // The obvious solution is to do a BFS and connect the nodes in each level.
+    // However, the problem asks us to use "constant space" (depth of tree).
+
+    void connectLeftRight(Node* leftTree, Node* rightTree) {
+        while (leftTree && rightTree) {
+            leftTree->next = rightTree;
+
+            leftTree  = leftTree->right;
+            rightTree = rightTree->left;
+        }
+    }
+
+    Node* connect(Node* root) {
+        if (root == nullptr) {
+            return root;
+        }
+
+        connect(root->left);
+        connect(root->right);
+
+        if (root->left) { // Non-leaf node.
+            connectLeftRight(root->left, root->right);
+        }
+
+        return root;
+    }
+};