Interview Algorithms: Difference between revisions

Retrieved from "https://wiki.davidl.me/view/Interview_Algorithms"

@@ Line 1: / Line 1: @@
 Insights from Leetcode problems.
+==Two Pointers Algorithms==
+Having two pointers can make your algorithm run in linear time.
 ====Finding a cycle in a linked-list====
@@ Line 7: / Line 9: @@
 Runner 2 goes one step per iteration.<br>
 If there is a cycle, runner 2 will lap runner 1 within 2 cycles.
+==Sliding Window==
+If you need to find a '''contiguous subarray''' or '''contiguous substring''', chances are it's a sliding window problem.
+Usually the structure will be something like:
+<syntaxhighlight lang=cpp>
+int best_case = WORST_POSSIBLE_VALUE;
+int left = 0;
+for (int right = 0; right < arr.size(); right++) {
+  // Add right to your subarray
+  int subarray_length = right + 1 - left;
+  // Do some checks to see if the subarray is valid
+  // Do left++ while keeping the subarray valid
+  // Update best_case
+}
+return best_case;
+</syntaxhighlight>
+Example problems: https://leetcode.com/discuss/study-guide/3630462/Top-20-Sliding-Window-Problems-for-beginners
+==Backtracking==
+====Permutations====
+Print all permutations of an array.<br>
+The idea here is that you need a for-loop nested for each element of an array.<br>
+So n elements means n nested for-loops. You use recursion to nest the loops.<br>
+You can also think of this as a graph problem when you need to find every possible path with DFS.<br>
+* [https://leetcode.com/problems/permutations/ Permutations]
+* [https://leetcode.com/problems/permutations-ii/ Permutations-ii]
+{{ hidden | Permute Brute-force solution |
+A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br>
+Here is a quick brute-force solution.
+* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits
+<syntaxhighlight lang="cpp">
+class Solution {
+public:
+    vector<vector<int>> permute(vector<int>& nums) {
+        vector<vector<int>> ans;
+        vector<int> indices(nums.size());
+        permuteHelper(nums, indices, 0, ans);
+        return ans;
+    }
+    bool isValid(vector<int>& indices) {
+        vector<char> check(indices.size(), false);
+        for (int i = 0; i < indices.size(); i++) {
+            if (check[indices[i]]) {
+                return false;
+            }
+            check[indices[i]] = true;
+        }
+        return true;
+    }
+    void permuteHelper(vector<int>& nums, vector<int>& indices,
+                       int col, vector<vector<int>>& ans) {
+        if (col == nums.size()) {
+            if (isValid(indices))
+                print(nums, indices, ans);
+            return;
+        }
+        for (int i = 0; i < nums.size(); i++) {
+            indices[col] = i;
+            permuteHelper(nums, indices, col+1, ans);
+        }
+    }
+    void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) {
+        vector<int> new_nums(nums.size());
+        for (int i = 0; i < nums.size(); i++) {
+            new_nums[i] = nums[indices[i]];
+        }
+        ans.push_back(new_nums);
+    }
+};
+</syntaxhighlight>
+}}
+==Data Structures==
+===Hashmap===
+Also known as a dictionary or associative array. These are used everywhere.<br>
+If you know your inputs are bounded non-negative values, then you can use an array like <code>std::vector</code>.<br>
+Otherwise, just use a hashmap to build a lookup table.
+===Segment Trees===
+See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree]
+===Union Find===
+In Union Find, you build a tree where each tree represents a set.<br>
+Your given a pair of relations where (a, b) indices a and b are in the same set.<br>
+The ''Union'' operation places a and b in the same set by attaching the root of b to the root of a.
+The ''Find'' operation recursively looks up the parent of a to find the root of the tree of a.
+<syntaxhighlight lang="python">
+parents = {}
+def find(a):
+  while parents[a] != a:
+    a = parents[a]
+  return a
+for (a, b) in relations:
+  if a not in parents:
+    parent[a] = a
+  a_root = find(a)
+  if b not in parents:
+    parent[b] = b
+  b_root = find(b)
+  parents[b_root] = a_root  # Attach b_root to a_root
+</syntaxhighlight>
+==Dynamic Programming==
+DP is mostly used for Google interviews. Meta for example will not ask DP problems. You should study DP after everything else or if you've secured a Google interview.
+If you're given an arbitrary function with <code>n*m</code> possible inputs, you should aim to find an O(n*m) solution.
+==Prefix Sum==
+If you need to do a reduce operation on a continuous subarray, chances are you can turn that O(n) into O(1) by building a prefix sum. Similarly for 2D with axis-aligned regions.
+==Tricks==
+===Bit tricks===
+See https://www.geeksforgeeks.org/bit-tricks-competitive-programming/
+It's rare that you will need bit tricks for an interview. However some leetcode questions may require them to get decent performance.
+The most useful one is
+<pre>
+n & n-1
+</pre>
+which zeros the least significant set bit.
+E.g. this can be used to count the number of set bits.
+===Bitmask===
+===Counting===
+Counting as in tabulate not as in combinatorial counting.
+====Finding duplicates in an array====
+If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>,
+then you count the number of times each bit appears and take it mod <math>n</math>.<br>
+The remaining bits will remain <math>m \mod n</math> times.<br>
+* [https://leetcode.com/problems/single-number/ single-number]
+* [https://leetcode.com/problems/single-number-ii/ single-number-ii]
+* [https://leetcode.com/problems/single-number-iii/ single-number-iii]