Interview Algorithms: Difference between revisions

← Older edit

@@ Line 86: / Line 86: @@
 </syntaxhighlight>
 }}
-==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.
-===Prefix Sum===
 ==Data Structures==
@@ Line 146: / Line 125: @@
 If you're given an arbitrary function with <code>n*m</code> possible inputs, you should aim to find an O(n*m) solution.
-==Misc Tricks==
+==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====