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

Bit tricks

See https://www.geeksforgeeks.org/bit-tricks-competitive-programming/

The most useful one is

n & n-1

which zeros the least significant set bit. E.g. this can be used to count the number of set bits.

Tricks

Bitmask

Counting

Counting as in tabulate not as in combinatorial counting.

Prefix Sum

Data Structures

Hashmap

Also known as a dictionary or associative array. Theses are used everywhere.

Segment Trees

See CP Algorithms segment tree

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.