Review: Graph Problems – Prepare For Coder Interview

Graph related questions mainly focus on depth first search and breath first search.

Basic Abstractions

Name	Summary
bfs and dfs relationship	Leetcode: Word Ladder II
From BFS to Bidirectional BFS	Half of the time. Leetcode: Word Ladder
3 cases: state is invalid/visited/unexamined	Leetcode: Word Ladder
Bridge	Bridge is an edge, when removed, will disconnect the graph
Duplicate edge
Cycle in undirected graphs
Cycle in DAG	Leetcode: Redundant Connection II

Questions

Name	Example
For matrix graph problems: rectangle vs square
Kruskal’s algorithm: Minimum spanning tree of a weighted graph	Leetcode: Connecting Cities With Minimum Cost
Dijkstra’s algorithm: shortest path for two nodes in a weighted graph
Floyd-Warshall algorithm: find shortest paths in a weighted graph
Move in different directions: 4 directions, 8 directions	Leetcode: Queens That Can Attack the King
Keep moving in the same direction	Leetcode: Queens That Can Attack the King

Floyd-Warshall algorithm: Time O(n*n*n)

BFS/DFS/UnionFind; Binarysearch

1. How to get the initial set to examine?
2. How to move to next? What's the time complexity?
3. What if we want all possible answers, instead of the min step count?

Move in 4 directions

// https://code.dennyzhang.com/as-far-from-land-as-possible
// ...
    for len(queue) > 0 {
        nexts := [][]int{}
        for _, node := range queue {
            i, j := node[0], node[1]
            for _, offset := range [][]int{[]int{1, 0}, []int{-1, 0},
                                           []int{0, 1}, []int{0, -1}} {
                i2, j2 := i+offset[0], j+offset[1]
                if i2<0 || i2>=len(grid) || 
                        j2<0 || j2>=len(grid[0]) || grid[i2][j2] == 1 {
                    continue
                }
                grid[i2][j2] = 1
                nexts = append(nexts, []int{i2, j2})
            }
        }
        level++
        queue = nexts
    }

Move in 9 directions

// https://code.dennyzhang.com/queens-that-can-attack-the-king
// ...
    i, j := king[0], king[1]
    for x:=-1; x<=1; x++ {
        for y:=-1; y<=1; y++ {
            if x==0 && y==0 {
                continue
            }
            // keep searching this direction
            i2, j2 := i+x, j+y
            for i2>=0 && i2<8 && j2>=0 && j2<8 {
                if m[[2]int{i2,j2}] {
                    res = append(res, []int{i2, j2})
                    break
                }
                i2, j2 = i2+x, j2+y
            }
        }
    }

Questions:

Why so many algorithms to find the shortest path? Shouldn’t it be some optimal one(s)?

BFS:

When to update visited_set? When add or when pop? Employee Importance

BFS:

visit all neighbors before visiting neighbors of your neighbors
Keep a queue of nodes to visit
The performamce may be different if we search from starting point or target point. Perfect Squares

Common graph algorithm problems:

Find length of shortest path from node s to all other nodes
Search all nodes for a node containing a given value
Find shortest path from node s to all other nodes

DFS:

visit all neighbors of a neighbor before visiting your other neighbors
It doesn’t use queue, but mark nodes as to their status. White(unchecked), Gray(Seen, but not finished), Black(finished)

Key points:

How to evaluable the time complexity. Normally it’s O(m*n). But how we can convince people with solid argument?

For DFS, if the path is too deep, we might run into stack overflow.

The most impressive problems to me:

CheatSheet: Leetcode For Code Interview

See all grap problems: #graph

See more blog_posts.

Post Views: 7