Interview Algorithms: Difference between revisions

No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 86: Line 86:
</syntaxhighlight>
</syntaxhighlight>
}}
}}
==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.
==Tricks==
===Bitmask===
===Counting===
Counting as in tabulate not as in combinatorial counting.
===Prefix Sum===


==Data Structures==
==Data Structures==
===Hashmap===
===Hashmap===
Also known as a dictionary or associative array. Theses are used everywhere.
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===
===Segment Trees===
Line 138: Line 120:
</syntaxhighlight>
</syntaxhighlight>


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