Interview Algorithms
Insights from Leetcode problems.
Contents
Linear Searching
Finding a cycle in a linked-list
Use two runners. \(\displaystyle O(n)\)
Runner 1 goes two steps per iteration.
Runner 2 goes one step per iteration.
If there is a cycle, runner 2 will lap runner 1 within 2 cycles.
Backtracking
Permutations
Print all permutations of an array.
The idea here is that you need a for-loop nested for each element of an array.
So n elements means n nested for-loops. You use recursion to nest the loops.
You can also think of this as a graph problem when you need to find every possible path with DFS.
A more advanced solution would use backtracking, however it is time-consuming to implement for an interview.
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
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;
}
<br />
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;
}
<br />
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);
}
}
<br />
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);
}
};
Tricks
Bitmask
Counting
Counting as in tabulate not as in combinatorial counting.
Prefix Sum
Misc Tricks
Finding duplicates in an array
If you have an array of ints where each number appears \(\displaystyle n\) times and one number appears \(\displaystyle m\gt n\) times where \(\displaystyle gcd(n,m)==1\),
then you count the number of times each bit appears and take it mod \(\displaystyle n\).
The remaining bits will remain \(\displaystyle m \mod n\) times.
