Interview Algorithms: Difference between revisions

No edit summary
 
Line 86: Line 86:
</syntaxhighlight>
</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==
==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.


==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====
====Finding duplicates in an array====