Interview Algorithms: Difference between revisions
No edit summary |
|||
| (9 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
Insights from Leetcode problems. | Insights from Leetcode problems. | ||
== | ==Two Pointers Algorithms== | ||
Having two pointers can make your algorithm run in linear time. | |||
====Finding a cycle in a linked-list==== | ====Finding a cycle in a linked-list==== | ||
Use two runners. <math>O(n)</math><br> | 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. | 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== | ==Backtracking== | ||
| Line 67: | Line 86: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
}} | }} | ||
==Data Structures== | ==Data Structures== | ||
===Hashmap=== | ===Hashmap=== | ||
Also known as a dictionary or associative array. | 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 117: | Line 120: | ||
</syntaxhighlight> | </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 | |||
<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==== | ||