Interview Algorithms: Difference between revisions
Created page with "Insights from Leetcode problems. ====Finding a cycle in a linked-list==== Use two runners. <math>O(n)</math><br> Runner 1 goes two steps per iteration.<br> Runner 2 goes one..." |
No edit summary |
||
(29 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==== | ||
Line 7: | Line 9: | ||
Runner 2 goes one step per iteration.<br> | Runner 2 goes one step per iteration.<br> | ||
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== | |||
====Permutations==== | |||
Print all permutations of an array.<br> | |||
The idea here is that you need a for-loop nested for each element of an array.<br> | |||
So n elements means n nested for-loops. You use recursion to nest the loops.<br> | |||
You can also think of this as a graph problem when you need to find every possible path with DFS.<br> | |||
* [https://leetcode.com/problems/permutations/ Permutations] | |||
* [https://leetcode.com/problems/permutations-ii/ Permutations-ii] | |||
{{ hidden | Permute Brute-force solution | | |||
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.<br> | |||
Here is a quick brute-force solution. | |||
* Enumerate all possible n^n numbers from 000 to 999 and then filter out number with duplicate digits | |||
<syntaxhighlight lang="cpp"> | |||
class Solution { | |||
public: | |||
vector<vector<int>> permute(vector<int>& nums) { | |||
vector<vector<int>> ans; | |||
vector<int> indices(nums.size()); | |||
permuteHelper(nums, indices, 0, ans); | |||
return ans; | |||
} | |||
bool isValid(vector<int>& indices) { | |||
vector<char> check(indices.size(), false); | |||
for (int i = 0; i < indices.size(); i++) { | |||
if (check[indices[i]]) { | |||
return false; | |||
} | |||
check[indices[i]] = true; | |||
} | |||
return true; | |||
} | |||
void permuteHelper(vector<int>& nums, vector<int>& indices, | |||
int col, vector<vector<int>>& ans) { | |||
if (col == nums.size()) { | |||
if (isValid(indices)) | |||
print(nums, indices, ans); | |||
return; | |||
} | |||
for (int i = 0; i < nums.size(); i++) { | |||
indices[col] = i; | |||
permuteHelper(nums, indices, col+1, ans); | |||
} | |||
} | |||
void print(vector<int>& nums, vector<int>& indices, vector<vector<int>>& ans) { | |||
vector<int> new_nums(nums.size()); | |||
for (int i = 0; i < nums.size(); i++) { | |||
new_nums[i] = nums[indices[i]]; | |||
} | |||
ans.push_back(new_nums); | |||
} | |||
}; | |||
</syntaxhighlight> | |||
}} | |||
==Data Structures== | |||
===Hashmap=== | |||
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=== | |||
See [https://cp-algorithms.com/data_structures/segment_tree.html CP Algorithms segment tree] | |||
===Union Find=== | |||
In Union Find, you build a tree where each tree represents a set.<br> | |||
Your given a pair of relations where (a, b) indices a and b are in the same set.<br> | |||
The ''Union'' operation places a and b in the same set by attaching the root of b to the root of a. | |||
The ''Find'' operation recursively looks up the parent of a to find the root of the tree of a. | |||
<syntaxhighlight lang="python"> | |||
parents = {} | |||
def find(a): | |||
while parents[a] != a: | |||
a = parents[a] | |||
return a | |||
for (a, b) in relations: | |||
if a not in parents: | |||
parent[a] = a | |||
a_root = find(a) | |||
if b not in parents: | |||
parent[b] = b | |||
b_root = find(b) | |||
parents[b_root] = a_root # Attach b_root to a_root | |||
</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==== | |||
If you have an array of ints where each number appears <math>n</math> times and one number appears <math>m>n</math> times where <math>gcd(n,m)==1</math>, | |||
then you count the number of times each bit appears and take it mod <math>n</math>.<br> | |||
The remaining bits will remain <math>m \mod n</math> times.<br> | |||
* [https://leetcode.com/problems/single-number/ single-number] | |||
* [https://leetcode.com/problems/single-number-ii/ single-number-ii] | |||
* [https://leetcode.com/problems/single-number-iii/ single-number-iii] |