From 4689e4e80b479be25f7557d05818f5caa723aafa Mon Sep 17 00:00:00 2001
From: 3gg <3gg@shellblade.net>
Date: Wed, 5 Feb 2025 18:36:31 -0800
Subject: Initial commit.
---
.../01_remove_duplicates_from_sorted_array.cc | 13 +++++
.../array/02_best_time_to_buy_and_sell_stock_2.cc | 24 +++++++++
.../easy/array/03_rotate_array.cc | 39 ++++++++++++++
.../easy/array/04_contains_duplicate.cc | 14 +++++
.../easy/array/05_single_number.cc | 10 ++++
.../easy/array/06_intersection_of_two_arrays_II.cc | 27 ++++++++++
top-interview-questions/easy/array/07_plus_one.cc | 25 +++++++++
.../easy/array/08_move_zeroes.cc | 23 ++++++++
top-interview-questions/easy/array/09_two_sum.cc | 24 +++++++++
.../easy/design/01_shuffle_an_array.cc | 41 ++++++++++++++
.../easy/design/02_min_stack.cc | 56 +++++++++++++++++++
.../easy/dynamic_programming/01_climbing_stairs.cc | 22 ++++++++
.../linked_list/01_delete_node_in_a_linked_list.cc | 22 ++++++++
.../02_remove_nth_node_from_end_of_list.cc | 32 +++++++++++
.../easy/linked_list/03_reverse_linked_list.cc | 26 +++++++++
.../easy/linked_list/04_merge_two_sorted_lists.cc | 52 ++++++++++++++++++
.../easy/linked_list/05_palindrome_linked_list.cc | 48 +++++++++++++++++
.../linked_list/05_palindrome_linked_list_2.cc | 63 ++++++++++++++++++++++
.../easy/linked_list/06_linked_list_cycle.cc | 29 ++++++++++
.../easy/others/05_valid_parentheses.cc | 41 ++++++++++++++
.../easy/others/06_missing_number.cc | 13 +++++
.../sorting_and_searching/01_merge_sorted_array.cc | 24 +++++++++
.../sorting_and_searching/02_first_bad_version.cc | 21 ++++++++
.../easy/strings/03_first_unique_character.cc | 18 +++++++
.../easy/strings/04_valid_anagram.cc | 29 ++++++++++
.../easy/strings/05_valid_palindrome.cc | 30 +++++++++++
.../easy/trees/01_maximum_depth_of_binary_tree.cc | 20 +++++++
.../easy/trees/02_valid_binary_search_tree.cc | 54 +++++++++++++++++++
.../easy/trees/03_symmetric_tree.cc | 52 ++++++++++++++++++
.../trees/04_binary_tree_level_order_traversal.cc | 44 +++++++++++++++
...5_convert_sorted_array_to_binary_search_tree.cc | 27 ++++++++++
31 files changed, 963 insertions(+)
create mode 100644 top-interview-questions/easy/array/01_remove_duplicates_from_sorted_array.cc
create mode 100644 top-interview-questions/easy/array/02_best_time_to_buy_and_sell_stock_2.cc
create mode 100644 top-interview-questions/easy/array/03_rotate_array.cc
create mode 100644 top-interview-questions/easy/array/04_contains_duplicate.cc
create mode 100644 top-interview-questions/easy/array/05_single_number.cc
create mode 100644 top-interview-questions/easy/array/06_intersection_of_two_arrays_II.cc
create mode 100644 top-interview-questions/easy/array/07_plus_one.cc
create mode 100644 top-interview-questions/easy/array/08_move_zeroes.cc
create mode 100644 top-interview-questions/easy/array/09_two_sum.cc
create mode 100644 top-interview-questions/easy/design/01_shuffle_an_array.cc
create mode 100644 top-interview-questions/easy/design/02_min_stack.cc
create mode 100644 top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc
create mode 100644 top-interview-questions/easy/linked_list/01_delete_node_in_a_linked_list.cc
create mode 100644 top-interview-questions/easy/linked_list/02_remove_nth_node_from_end_of_list.cc
create mode 100644 top-interview-questions/easy/linked_list/03_reverse_linked_list.cc
create mode 100644 top-interview-questions/easy/linked_list/04_merge_two_sorted_lists.cc
create mode 100644 top-interview-questions/easy/linked_list/05_palindrome_linked_list.cc
create mode 100644 top-interview-questions/easy/linked_list/05_palindrome_linked_list_2.cc
create mode 100644 top-interview-questions/easy/linked_list/06_linked_list_cycle.cc
create mode 100644 top-interview-questions/easy/others/05_valid_parentheses.cc
create mode 100644 top-interview-questions/easy/others/06_missing_number.cc
create mode 100644 top-interview-questions/easy/sorting_and_searching/01_merge_sorted_array.cc
create mode 100644 top-interview-questions/easy/sorting_and_searching/02_first_bad_version.cc
create mode 100644 top-interview-questions/easy/strings/03_first_unique_character.cc
create mode 100644 top-interview-questions/easy/strings/04_valid_anagram.cc
create mode 100644 top-interview-questions/easy/strings/05_valid_palindrome.cc
create mode 100644 top-interview-questions/easy/trees/01_maximum_depth_of_binary_tree.cc
create mode 100644 top-interview-questions/easy/trees/02_valid_binary_search_tree.cc
create mode 100644 top-interview-questions/easy/trees/03_symmetric_tree.cc
create mode 100644 top-interview-questions/easy/trees/04_binary_tree_level_order_traversal.cc
create mode 100644 top-interview-questions/easy/trees/05_convert_sorted_array_to_binary_search_tree.cc
(limited to 'top-interview-questions/easy')
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());
+ }
+};
--
cgit v1.2.3