Initial commit.HEADmain

9 files changed, 199 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;
+    }
+};