Interview Algorithms: Difference between revisions

← Older edit

@@ Line 1: / Line 1: @@
 Insights from Leetcode problems.
-==Linear Searching==
+==Two Pointers Algorithms==
+Having two pointers can make your algorithm run in linear time.
 ====Finding a cycle in a linked-list====
 Use two runners. <math>O(n)</math><br>
@@ Line 8: / Line 10: @@
 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==
@@ Line 68: / Line 87: @@
 }}
-==Bit tricks==
+==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
@@ Line 78: / Line 144: @@
 E.g. this can be used to count the number of set bits.
-==Tricks==
 ===Bitmask===
 ===Counting===
 Counting as in tabulate not as in combinatorial counting.
-===Prefix Sum===
-==Data Structures==
-===Hashmap===
-Also known as a dictionary or associative array. Theses are used everywhere.
-===Segment Trees===
-See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree]
-==Misc Tricks==
 ====Finding duplicates in an array====