Interview Algorithms

From David's Wiki
\( \newcommand{\P}[]{\unicode{xB6}} \newcommand{\AA}[]{\unicode{x212B}} \newcommand{\empty}[]{\emptyset} \newcommand{\O}[]{\emptyset} \newcommand{\Alpha}[]{Α} \newcommand{\Beta}[]{Β} \newcommand{\Epsilon}[]{Ε} \newcommand{\Iota}[]{Ι} \newcommand{\Kappa}[]{Κ} \newcommand{\Rho}[]{Ρ} \newcommand{\Tau}[]{Τ} \newcommand{\Zeta}[]{Ζ} \newcommand{\Mu}[]{\unicode{x039C}} \newcommand{\Chi}[]{Χ} \newcommand{\Eta}[]{\unicode{x0397}} \newcommand{\Nu}[]{\unicode{x039D}} \newcommand{\Omicron}[]{\unicode{x039F}} \DeclareMathOperator{\sgn}{sgn} \def\oiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x222F}\,}{\unicode{x222F}}{\unicode{x222F}}{\unicode{x222F}}}\,}\nolimits} \def\oiiint{\mathop{\vcenter{\mathchoice{\huge\unicode{x2230}\,}{\unicode{x2230}}{\unicode{x2230}}{\unicode{x2230}}}\,}\nolimits} \)

Insights from Leetcode problems.


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.


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.


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);
    }
};