# Interview Algorithms


Insights from Leetcode problems.

## 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.

Permute Brute-force solution

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

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.