LeBlanc’s law: "Later equals never".
Summary A spanning tree of some graph G is a subgraph that is a tree which includes all of the vertices of G, with a minimum possible number of edges. A Minimum Spanning Tree (MST) is a spanning tree whose sum of edge weights is as small as possible. Kruskal’s Algorithm Please refer to this page for its concepts and pseudo codes. The following code…
Summary An Eulerian path is a path in a finite graph that visits every edge exactly once (allowing for revisiting vertices). An Eulerian cycle is a Eulerian path that starts and ends on the same vertex. We give the following properties without proof. An undirected graph has an Eulerian trail iif exactly 0 or 2 vertices have odd degree, its…
Summary No one is supposed to invent the Boyer–Moore voting algorithm during the interview. The point is how to write bug-free codes and make interviewers happy. The order of the branches are quite tricky here. Please remember to increase cnt first, then check if cnt==0, and finally decrease cnt. Several good points here to mention,…
Summary Pimpl is used to hide implementation details for library consumers. It hides headers, data members, as well as private functions. Note that ~foo() has to be defined after foo::impl gets fulfilled. This is a requirement from unique_ptr: std::unique_ptr may be constructed for an incomplete type T, such as to facilitate the use as a handle in…
Summary Lowest Common Ancestor (LCA) is a typical rooted tree related problem. A simple solution is use dfs to traverse the graph from root to leaves. If at some point it is first time we find out two nodes are in the same subtree, the current node is the LCA. The solution costs O(n) time….
Summary Given a modular MOD, if we want to calculate the division of two integers, we could use the technique Modular Multiplicative Inverse. To calculate b_, we could use Fermat’s little theorem. If mod is a prime number, we have If we use Binary Exponentiation technique, we could calculate b_ efficiently.
Summary Quick Select is typical technique to select the top k elements (the rest of array is not sorted) from an array in amortized O(n) time. If we use a smart way to choose pivot (Introselect), the algorithm is guaranteed to have O(n) worst case performance. Quick Sort is an unstable sort. It has amortized…
Summary A common problem in undirected or directed graph is to calculate the shortest path between two nodes. There are several typical technologies that we could use. Floyd-Warshall Shortest paths (multiple sources) in such graphs that: It is actually a DP problem. We define alg[k][x][y] as the shortest path from x to y using the…
Summary There are a number of questions in the form that given a string, evaluate the value of it. These questions can be all solved by the routine Infix Notation to Reverse Polish Notation and Evaluate Reverse Polish Notation.