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 ++++++++++ .../01_binary_tree_inorder_traversal.cc | 27 ++++++++++ .../02_binary_tree_zigzag_level_order_traversal.cc | 53 ++++++++++++++++++ ...ary_tree_from_preorder_and_inorder_traversal.cc | 49 +++++++++++++++++ ..._populating_next_right_pointers_in_each_node.cc | 47 ++++++++++++++++ 35 files changed, 1139 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 create mode 100644 top-interview-questions/medium/trees_and_graphs/01_binary_tree_inorder_traversal.cc create mode 100644 top-interview-questions/medium/trees_and_graphs/02_binary_tree_zigzag_level_order_traversal.cc create mode 100644 top-interview-questions/medium/trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder_traversal.cc create mode 100644 top-interview-questions/medium/trees_and_graphs/04_populating_next_right_pointers_in_each_node.cc (limited to 'top-interview-questions') 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& 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& 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& 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& 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& 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 intersect(vector& nums1, vector& nums2) { + std::sort(nums1.begin(), nums1.end()); + std::sort(nums2.begin(), nums2.end()); + + std::vector 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 plusOne(vector& 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& 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 twoSum(vector& nums, int target) { + // When you find, e.g., 2, map (2 -> idx 0) for the event + // in which you find the 7. + std::vector pair(2); + std::unordered_map 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& nums) + : m_original(nums) {} + + vector reset() { + return m_original; + } + + vector shuffle() { + std::vector 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 m_original; + std::uint64_t m_random = 16240738485554559101; +}; + +/** + * Your Solution object will be instantiated and called as such: + * Solution* obj = new Solution(nums); + * vector param_1 = obj->reset(); + * vector 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 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& 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& nums1, int m, vector& 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& 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& current_level, + std::vector& 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 current_level({root}); + std::vector 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>& levels, + vector& current_level, + vector& next_level) { + if (current_level.empty()) { + return; + } + levels.push_back({}); + vector& 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> levelOrder(TreeNode* root) { + if (!root) return {}; + vector> levels; + vector current_level({root}); + vector 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& 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& 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& vals) { + if (node == nullptr) return; + + inorder(node->left, vals); + vals.push_back(node->val); + inorder(node->right, vals); + } + + vector inorderTraversal(TreeNode* root) { + vector 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& level, vector& values, const TreeNode* node) { + level.push_back(node); + values.push_back(node->val); + } + + void zigZag(bool leftRight, const vector& level, vector>& values) { + vector next_level; + vector 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> zigzagLevelOrder(TreeNode* root) { + if (root == nullptr) return {}; + + vector level = {root}; + vector> 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& preorder, const vector& 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& preorder, vector& 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; + } +}; -- cgit v1.2.3