Summary: Problems solved by BFS I: Graph

interview

---

BFS For Graph

/** 
 * BFS Version Graph Traversal Template:
 */
BFS(V){
    let Q be a queue
    Q.push(V)
    label V as visted
    while(!Q.empty()){
        u = Q.pop()
        for all edges from u to w
            if w is not visited
                enqueue w
                mark w visited
}

/** 
 * BFS Version Topological Sort Template:
 */
let L be an empty list
let S be the set of nodes without incoming edges
while( !S.empty()){
    remove a node n from S
    append n to L
    foreach node m with edge e from n to m
        remove e from graph
        if m has no incoming edge
            insert m to S
}
if still there are some incoming edges for some nodes 
    return // the graph has a cycle
return L

1. Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example :
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

Idea:
- BFSearch 'O's on the boards, replace 'O's with 'Y's
- For the remaining 'O's, replace with 'X's
- Recover 'Y's with 'O's

Also can be solved with DFS, but large data test case will throw a stack overflow error

class Pos{
    int x, y;
    Pos(int i, int j){ x = i; y = j;}
}
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
public void bfs(char [][] board, int i, int j){
    if(board[i][j] !='O') return;
    int m = board.length;
    int n = board[0].length;
    Queue<Pos> Q = new LinkedList<Pos>();
    Q.offer(new Pos(i, j));
    while(!Q.isEmpty()){
        Pos cur = Q.poll();
        if(cur.x < 0|| cur.y<0 || cur.x==m || cur.y ==n) continue;
        if(board[cur.x][cur.y]!='O') continue; 
        board[cur.x][cur.y] = 'Y';
        for(int k=0; k<4; k++){
            Pos neighbor = new Pos(cur.x+dx[k], cur.y+dy[k]);
            Q.offer(neighbor);
        }
    }
}
public void solve(char[][] board) {
    int m = board.length;
    if(m==0) return;
    int n= board[0].length;
    for(int row=0; row<m; row++){ // left/right column
        bfs(board, row, 0); 
        bfs(board, row, n-1);
    }
    for(int col=0; col<n; col++){ // top/bottom row
        bfs(board, 0, col);
        bfs(board, m-1, col);
    }
    // check inner area, fill 'O's with 'X's
    for(int i=1; i<m-1; i++){
        for(int j=1; j<n-1; j++){
            if(board[i][j]=='O') board[i][j]='X';
        }
    }
    // recover 'Y's back to 'O's
    for(int i=0; i<m; i++){
        for(int j=0;j<n; j++){
            if(board[i][j]=='Y') board[i][j]='O';
        }
    }
}

2. Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
You may assume all four edges of the grid are all surrounded by water.

Example 1:
11110
11010
11000
00000
Answer: 1

Example 2:
11000
11000
00100
00011
Answer: 3

Idea:
BFSearch from a position of '1' (update count at the same time)
Mark visited '1' as '0'

class Pos{
    int x, y;
    Pos(int i, int j){x=i; y=j;}
}
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
public void bfs(char[][] grid, int i, int j){
    if(grid[i][j] != '1') return; // water, return 
    int m = grid.length;
    int n = grid[0].length;
    Queue<Pos> Q= new LinkedList<Pos>();
    Q.offer(new Pos(i, j));
    while(!Q.isEmpty()){
        Pos cur = Q.poll();
        if(cur.x <0 || cur.y<0|| cur.x==m || cur.y==n) continue;
        if(grid[cur.x][cur.y]!='1') continue;
        grid[cur.x][cur.y] = '0'; // mark visited land as water
        for(int k=0; k<4; k++){
            Pos neighbor = new Pos(cur.x+dx[k], cur.y+dy[k]);
            Q.offer(neighbor);
        }
    }
}
public int numIslands(char[][] grid) {
    int m = grid.length;
    if(m==0) return 0;
    int n = grid[0].length;
    int count = 0;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(grid[i][j]=='1'){
                count++;  
                bfs(grid, i, j);
            } 
        }
    }
    return count;
}

3. Course Schedule I/II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should
also have finished course 1. So it is impossible.

Idea: topological sort
- There is an implicit fact here: the courses numbers are from $0, \ldots, n-1$. We can represent $n$ graph nodes using integers from $0 \to n-1$.
- Use hashmap to represent the graph: map: key is the node id $i$, value is the list of of nodes' id's: so that node $i$ has outgoing edges to these nodes.
- Use array incoming[] to record the number of incoming edges for each node: incoming[i] = j means node $i$ has $j$ incoming edges.

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int n = prerequisites.length;
    if(n==0) return true;
    HashMap<Integer, ArrayList<Integer>> pre_posts = new HashMap<Integer, ArrayList<Integer>>();
    int incoming[] = new int [numCourses]; // mistake: numCousrses is not necessarily equal to n!
    for(int [] pair : prerequisites){
        int pre = pair[1];
        int post = pair[0];
        incoming[post]++;
        if(!pre_posts.containsKey(pre)){
            pre_posts.put(pre, new ArrayList<Integer>());
        }
        pre_posts.get(pre).add(post);
    }
    // find nodes without incoming edges
    Queue<Integer> Q = new LinkedList<Integer>();
    for(int i=0; i<numCourses; i++){
        if(incoming[i]==0) Q.offer(i);
    }
    while(!Q.isEmpty()){
        Integer pre = Q.poll();
        // important! must check key existance
        if(!pre_posts.containsKey(pre)) continue;
        for(Integer post : pre_posts.get(pre)){
            incoming[post]--;
            if(incoming[post]==0){
                Q.offer(post);
            }
        }
    }
    for(int i: incoming){
        if(i>0) return false;
    }
    return true;
}

4. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
//BFS version solution
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if(node == null) return null;
    HashMap<Integer, UndirectedGraphNode> cloned = new HashMap<Integer, UndirectedGraphNode>();
    Queue<UndirectedGraphNode> Q = new LinkedList<UndirectedGraphNode>();
    Q.offer(node);
    cloned.put(node.label, new UndirectedGraphNode(node.label));
    while(!Q.isEmpty()){
        UndirectedGraphNode cur = Q.poll();
        for(UndirectedGraphNode neighbor : cur.neighbors){
            if(!cloned.containsKey(neighbor.label)){
                cloned.put(neighbor.label, new UndirectedGraphNode(neighbor.label));
                Q.offer(neighbor);
            }
            cloned.get(cur.label).neighbors.add(cloned.get(neighbor.label));
        }
    }
    return cloned.get(node.label);
}

5. Word Ladder

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

Example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

    public ArrayList<String> getOneEditWords(String word){
        ArrayList<String> neighbors = new ArrayList<String>();
        char wd[] = word.toCharArray();
        for(int i=0; i<wd.length; i++){
            char origin = wd[i];
            for(char c = 'a'; c<='z'; c++){
                if(wd[i] != c) { 
                    wd[i] = c;
                    neighbors.add(new String(wd));
                    wd[i] = origin;
                }
            }
        }
        return neighbors;
    }
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        if(wordDict.size()==0) return 0;
        Queue<String> Q = new LinkedList<String>();
        Q.offer(beginWord);
        HashSet<String> visited = new HashSet<String>();
        visited.add(beginWord);
        int len = 1;
        int curr_level = 1, next_level=0;
        while(!Q.isEmpty()){
            String cur = Q.poll();
            curr_level--;
            for(String next : getOneEditWords(cur)){
                if(next.equals(endWord)){ return len+1;}
                if(wordDict.contains(next)) {
                    if(!visited.contains(next)){
                        Q.offer(next);
                        visited.add(next);
                        next_level++;
                    }
                }
            }
            if(curr_level==0){
                curr_level = next_level;
                next_level = 0;
                len++;
            }
        }
        return 0;
    }