Apart from the well-known BFS and DFS algorithms, I find the following algorithms useful for Coding Interview.

Topology sort & circle check
  • Given directed graph, sort the nodes in graph so that, if exist an edge (u->v), v comes after u in the sorted array.
  • We cannot sort if there is at least 1 circle in the graph, (u->v->u), so we need to check whether there is at least 1 circle in the graph.
    vector<vector<int>> adj;
    vector<bool> visited;
    vector<bool> inDfs;
    // the sorted order of node
    vector<int> q;
    int id = n;
    bool ok;

    void dfs(int u) {
        visited[u] = true;
        inDfs[u] = true;
        for(int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if (!visited[v]) {
                dfs(v);
            } else if (inDfs[v]) {
                ok = false;
                return;
            }
        }
        q[id--] = u;
        inDfs[u] = false;
    }  

Runtime: O(n+m)
Practice:

  1. https://leetcode.com/problems/course-schedule
  2. https://leetcode.com/problems/course-schedule-ii
  3. https://leetcode.com/problems/alien-dictionary
  4. https://leetcode.com/problems/parallel-courses
Dijkstra

Finding the shortest distance between 2 nodes in non-negative weights graph

    int dijstra(vector<vector<int>>& edges, int N, int Source) {
        vector<ii> a[N+1];
        for(auto e: edges) {
            int u = e[0], v = e[1], w = e[2];
            a[u].push_back(ii(v, w));
        }
        priority_queue<ii, vector<ii>, greater<ii> > q;
        int fx[N+1];
        for(int i = 1; i <= N; i++) fx[i] = INT_MAX;
        fx[Source] = 0;
        q.push(ii(0, Source));

        while (q.size()) {
            int u = q.top().second;
            q.pop();
            for(auto pair: a[u]) {
                int v = pair.first;
                int w = pair.second;
                if (fx[v] > fx[u] + w) {
                    fx[v] = fx[u] + w;
                    q.push(ii(fx[v], v));
                }
            }
        }
  }

Runtime: O(n + m log n)
Practice: https://leetcode.com/problems/network-delay-time

Euler circle finding
  • An Eulerian cycle exists if and only if the degrees of all vertices are even
  • An Eulerian path exists if and only if the number of vertices with odd degrees is two
    vector<int> circle;
    unordered_set<int> g[100];

    void dfs(int u) {
        while (!g[u].empty()) {
            int v = *g[u].begin();
            g[u].erase(v);
            g[v].erase(u);
            dfs(v);
        }

        circle.push_back(u);
    }

Runtime: O(m)
Practice:

  1. https://leetcode.com/problems/reconstruct-itinerary/
Kruskal - finding Minimum Spaning Tree
    int p[10001];
    int r[10001];

    int find(int i) {
        if (i == p[i]) return i;
        return (find(p[i]));
    }

    void merge(int i, int j) {
        if (r[i] > r[j]) {
            p[j] = i;
        } else {
            p[i] = j;
            if (r[i] == r[j]) r[j]++;
        }
    }

    int kruskal(int n, vector<vector<int>>& connections) {
        vector<pair<int, pair<int, int>>> a;
        for(auto e: connections) {
            int w = e[2];
            int u = e[0];
            int v = e[1];
            a.push_back(make_pair(w, make_pair(u, v)));
        }
        sort(a.begin(), a.end());
        for(int i = 0; i < n; i++) {
            p[i] = i;
            r[i] = 0;
        }

        int res = 0;
        int count = 0;
        for(int i = 0; i < a.size(); i++) {
            int u = a[i].second.first;
            int v = a[i].second.second;
            int uRoot = find(u);
            int vRoot = find(v);
            if (uRoot != vRoot) {
                res += a[i].first;
                count++;
                merge(uRoot, vRoot);
            }
        }
        return count == n-1 ? res : -1;
    }

Runtime: O(m log m)
Practice:

  1. https://leetcode.com/problems/connecting-cities-with-minimum-cost
  2. https://leetcode.com/problems/satisfiability-of-equality-equations
  3. https://leetcode.com/problems/regions-cut-by-slashes
  4. https://leetcode.com/problems/redundant-connection
  5. https://leetcode.com/problems/number-of-islands-ii
  6. https://leetcode.com/problems/optimize-water-distribution-in-a-village
Bipartite Graph Check

Bipartite Graph is a special graph with the following characteristics: The set of vertices V can be partitioned into two disjoint sets V1 and V2 and all edges in (u,v) ∈ E has the property that u ∈ V1 and v ∈ V2.

    vector<bool> visit;
    vector<bool> color;

    bool dfs(int u, bool c) {
        visit[u] = true;
        color[u] = c;
        for(int v: a[u]) {
            if (!visit[v]) {
                if (!dfs(v, !c)) return false;
            } else {
                if (color[u] == color[v]) return false;
            }
        }
        return true;
    }

Runtime: O(n+m)
Practice: https://leetcode.com/problems/possible-bipartition/

Check if a node is in circle in graph

The idea is to colour node with 3 colors: 0, 1, 2.
If the node is not visited, its color is 0
If the node is in the process of visiting by DFS, its color is 1
If the node dfs process is completed, its color is 2.

    int color[10001];
    vector<vector<int>> g;
    /*
        0: white
        1: grey
        2: black
    */
    bool dfs(int u) {
        if (color[u] != 0) return color[u] == 2;
        
        color[u] = 1;
        for(int v: g[u]) {
            if (color[v] != 2) {
                if (color[v] == 1 || !dfs(v)) return false;
            }
        }
        color[u] = 2;
        return true;
    }

Runtime: O(n+m)
Practice: https://leetcode.com/problems/find-eventual-safe-states/