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.

Sliding Window

If you need to find a contiguous subarray or contiguous substring, chances are it's a sliding window problem.

Usually the structure will be something like:

int best_case = WORST_POSSIBLE_VALUE;
int left = 0;
for (int right = 0; right < arr.size(); right++) {
  // Add right to your subarray
  int subarray_length = right + 1 - left;
  // Do some checks to see if the subarray is valid
  // Do left++ while keeping the subarray valid
  // Update best_case
}
return best_case;

Example problems: https://leetcode.com/discuss/study-guide/3630462/Top-20-Sliding-Window-Problems-for-beginners

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

Data Structures

Hashmap

Also known as a dictionary or associative array. These are used everywhere.
If you know your inputs are bounded non-negative values, then you can use an array like std::vector.
Otherwise, just use a hashmap to build a lookup table.

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

Dynamic Programming

DP is mostly used for Google interviews. Meta for example will not ask DP problems. You should study DP after everything else or if you've secured a Google interview.

If you're given an arbitrary function with n*m possible inputs, you should aim to find an O(n*m) solution.

Prefix Sum

If you need to do a reduce operation on a continuous subarray, chances are you can turn that O(n) into O(1) by building a prefix sum. Similarly for 2D with axis-aligned regions.

Tricks

Bit tricks

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

It's rare that you will need bit tricks for an interview. However some leetcode questions may require them to get decent performance.

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.

Bitmask

Counting

Counting as in tabulate not as in combinatorial counting.

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.