Notes for Algorithm Practice

vector<int> topologicalSort(int num, vector<vector<int>>& edges) {
  vector<vector<int>> graph(num);
  vector<int> incoming(num, 0);
  for (auto& edge: edges) {
    graph[edge[1]].push_back(edge[0]);
    incoming[edge[0]]++;
  }
  queue<int> q;
  for (int i = 0; i < num; i++) {
    if (incoming[i] == 0) {
      q.push(i);
    }
  }
  vector<int> ans;
  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    ans.push_back(curr);
    num--;
    for (auto n: graph[curr]) {
      incoming[n]--;
      if (incoming[n] == 0) {
        q.push(n);
      }
    }
  }
  if (num) {
    throw "no topological soring";
  } else {
    return ans;
  }
}

Binary Indexed Tree

topcoder: Binary Indexed Tree

Update and find element <= x in O(log m) time

struct BinaryIndexTree {

  vector<int> tree;
  int maxidx;

  BinaryIndexTree(int maxidx) {
    this->maxidx = maxidx;
    tree = vector<int> (maxidx, 0);
  }

  void update(int idx, int val) {
    while (idx <= maxidx) {
      tree[idx] += val;
      idx += (idx & -idx);
    }
  }

  int read(int idx) {
    int s = 0;
    while (idx > 0) {
      s += tree[idx];
      idx -= (idx & -idx);
    }
    return s;
  }

};

Time Complexity: O(log m) where m is max index

2D BIT

308. Range Sum Query 2D - Mutable

Sliding Window

Maximum of Window

Use a Deque to maintain the maximum(minimum) value in a window.

Keep this Deque weak monotonical decreasing.

deque<int> maxd; // keeps reference of array positions

// expend window
while (not maxd.empty() and nums[maxd.back()] <= nums[i])
  maxd.pop_back();
maxd.push_back(i);

// shrink window
if (maxd.front() == j)
  maxd.popfront();

// get maximum
auto maxvalue = nums[maxd.front()];

862. Shortest Subarray with Sum at Least K

Since negative numbers are allowed, a normal sliding window cannot solve it.

Sliing Window on matrix

1074. Number of Submatrices That Sum to Target

Should in O(n^3) time complexity.

Base Question: 560. Subarray Sum Equals K

Use hash map and reversed query.

Binary Search

Find Upper and Lower bound

[#A] 4. Median of Two Sorted Arrays

Finding the Median of 2 Sorted Arrays in Logarithmic Time

Hard Binary Search

Check out the following code to 3 different hard questions. And you can see they are almost the same. I am sure you can figure out the template.

862. Shortest Subarray with Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:
Input: A = [1], K = 1
Output: 1

Example 2:
Input: A = [1,2], K = 4
Output: -1

Example 3:
Input: A = [2,-1,2], K = 3
Output: 3

Note:
1.    1 <= A.length <= 50000
2.    -10 ^ 5 <= A[i] <= 10 ^ 5
3.    1 <= K <= 10 ^ 9

int maximizeSweetness(vector<int>& sweetness, int K) {
  auto isValid = [&](int target) {
    int cnt = 0, sum = 0;
    for (auto v : sweetness) {
      sum += v;
      if (sum >= target) cnt++, sum = 0;
    }
    return cnt >= K+1;
  };

  int left = *min_element(sweetness.begin(), sweetness.end());
  int right = accumulate(sweetness.begin(), sweetness.end(), 0);

  while (left < right) {
    int mid = left + (right - left + 1) / 2;
    if (!isValid(mid)) right = mid - 1;
    else left = mid;
  }
  return left;
}

int splitArray(vector<int>& nums, int m) {
  // greedy split into sums <= target
  auto isValid = [&] (int target) {
    int cnt = 0, sum = 0;
    for (auto v : nums) {
      sum += v;
      if (sum > target) cnt++, sum = v;
    }
    return cnt+1 <= m;
  };

  int left = *max_element(nums.begin(), nums.end());
  int right = accumulate(nums.begin(), nums.end(), 0);
  while (left < right) {
    int mid = left + (right - left) / 2;
    if (!isValid(mid)) left = mid + 1;
    else right = mid;
  }
  return left;
}

Union Find

class UnionFind {
  vector<int> table;
public:
  UnionFind(int size) {
    table = vector(size, -1);
  }

  int find(int a) {
    while (table[a] >= 0)
      a = table[a];
    return a;
  }

  void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (table[b] < table[a]) swap(a, b);
    table[a] += table[b];
    table[b] = a;
  }
};

685. Redundant Connection II

Dijkstra

dijkstra in different usage

KMP

Knuth-Morris-Pratt algorithm

// haystack, needle
assert(needle.size() > 0);
pos = 1;
cnd = 0;
while (pos < needle.size()) {
  if (needle[pos] == needle[cnd]) {
    table[pos] = table[cnd];
  } else {
    table[pos] = cnd;
    while (cnd >= 0 and needle[pos] != needle[cnd])
      cnd = table[cnd];
  }
  pos++;
  cnd++;
}
table[pos] = cnd;

Least steps to cover a range

Method:

sorted by lhs, move forward until lhs <= bound counter, count a step, bound counter be maximum of rhs, and loop.

Heuristics:

Trie

class Trie {
    struct Node {
        bool endStr = false;
        Node* table[26] = {nullptr};

        ~Node() {
            for (int i = 0; i < 26; i++) {
                if (table[i])
                    delete table[i];
            }
        }
    } *root;

public:
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }

    ~Trie() {
        delete root;
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        Node* node = root;
        for (auto ch: word) {
            if (!node->table[ch - 'a']) {
                node->table[ch - 'a'] = new Node();
            }
            node = node->table[ch - 'a'];
        }
        node->endStr = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Node* node = root;
        for (auto ch: word) {
            if (node->table[ch - 'a']) {
                node = node->table[ch - 'a'];
            } else {
                return false;
            }
        }
        return node->endStr;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Node* node = root;
        for (auto ch: prefix) {
            if (node->table[ch - 'a']) {
                node = node->table[ch - 'a'];
            } else {
                return false;
            }
        }
        return true;
    }
};

Heap

Use an ordered map if you want to delete randomly in a heap

855. Exam Room

HOLD 857. Minimum Cost to Hire K Workers

1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

Use a BFS to peek minimum sum every time, and get result when pick k times. (Thanks to Meow-Meow)

Simple Solution Using Set As Priority_Queue O(k * n * logn)

Range Query

Knapsack Problem

https://zhuanlan.zhihu.com/p/93857890

0-1 Knapsack Problem

DP on weights and nth items (put or not)

Time Complexity: O(w * n) where w is size of weight and n is count of items

HOLD Meet in the Middle

Longest Increasing Subsequence (LIS)

int lengthOfLIS(vector<int>& nums) {
  vector<int> table;
  for (auto n: nums) {
    auto it = lower_bound(table.begin(), table.end(), n);
    if (it == table.end()) {
      table.push_back(n);
    } else {
      *it = min(*it, n);
    }
  }
  return table.size();
}

Longest Common Subsequence (LCS)

Primes

SymPy has many good implementations for number theory.

[ ] Consecutive Primes

Sieve of Eratosthenes

Resources

Experience

Google Interview

FAQ
GOCC 18
short intro
ask clarify questions
pseudo-code
brute force solution
optimized solution
test cases

https://leetcode.com/discuss/interview-experience/423119/Google-or-L3-or-Japan-or-Oct-2019-Reject

Questions:

range of input
null pointer
is distinct element?

[#A] LeetCode Tour

327. Count of Range Sum

1751. Maximum Number of Events That Can Be Attended II

1353. Maximum Number of Events That Can Be Attended

[#C] 685. Redundant Connection II

871. Minimum Number of Refueling Stops

Tips

Try Brute Force First
Use easier Data Structure first
Do NOT use iterator first

Snippets

C++ use pair as key

struct pair_hash {
  template<class T1, class T2>
  std::size_t operator() (const std::pair<T1, T2> &pair) const {
    return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
  }
};

https://www.techiedelight.com/use-std-pair-key-std-unordered_map-cpp/

Using context-sensitive comparing function

Stackoverflow: declare a custom sort function

auto comp = [](int a, int b) { return std::bitset<32>(a).count() < std::bitset<32>(b).count(); };
std::map<int, int, decltype(comp)> m(comp);

Using a structure

struct Compare {
  vector<int> &context;
  bool operator() (const int &a, const int &b) const {
    return context[a] < context[b];
  }
};

set<int, Compare> ss(Compare{arr});

Python Data Structure

Heap

import heapq
vec = []
# max-heap
heapq.heapify(vec)
heapq.heappush(vec, el)
heapq.heappop(vec)

Deque

import collections
dq = collections.deque()
dq.append(x)     # push_back
dp.appendleft(x) # push_front
dp.pop()         # back  and pop_back
dp.popleft()     # front and pop_front

Counter

import collections
c = collections.Counter()
# like a hash dict

citrus-lemon/algorithm-notes

Notes for Algorithm Practice

Data Structures and Algorithm

Search

Segment Tree

Dynamic Programming

2D Table Questions

887. Super Egg Drop DP with Optimality Criterion

Factorization

Topological Sorting

Binary Indexed Tree

2D BIT

Sliding Window

Maximum of Window

Sliing Window on matrix

Binary Search

[#A] 4. Median of Two Sorted Arrays

Union Find

Dijkstra

KMP

Least steps to cover a range

Trie

Heap

HOLD 857. Minimum Cost to Hire K Workers

Range Query

Knapsack Problem

0-1 Knapsack Problem

HOLD Meet in the Middle

Longest Increasing Subsequence (LIS)

Longest Common Subsequence (LCS)

Primes

Sieve of Eratosthenes

Resources

Experience

Google Interview

[#A] LeetCode Tour

[#C] 685. Redundant Connection II

Tips

Snippets

C++ use pair as key

Using context-sensitive comparing function

Python Data Structure

Heap

Deque

Counter