Interview Algorithms: Difference between revisions
No edit summary |
|||
Line 86: | Line 86: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
}} | }} | ||
==Data Structures== | ==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. | 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==== | ====Finding duplicates in an array==== |