Interview Algorithms

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

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

Union Find

In Union Find, you build a tree where each tree represents a set.
Your given a pair of relations where (a, b) indices a and b are in the same set.
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.

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

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.