Sunday, February 14, 2016

Git Version

Find all git commits, and print it out in order.

Solution:
Using BFS.

Code (Java):
import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

public class Solution {
    public List<Integer> findCommits(GraphNode root) {  
        List<Integer> result = new ArrayList<>();
        Set<GraphNode> visited = new HashSet<>();
        Queue<GraphNode> queue = new LinkedList<>();
        
        findCommitsHelper(root, visited, queue, result);
        
        return result;
    }
    
    private void findCommitsHelper(GraphNode root, Set<GraphNode> visited, 
                                   Queue<GraphNode> queue, List<Integer> result) {
        if (root == null) {
            return;
        }
        
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            GraphNode curr = queue.poll();
            if (!visited.contains(curr)) {
                visited.add(curr);
                result.add(curr.val);
                
                for (GraphNode neighbor : curr.neighbors) {
                    queue.offer(neighbor);
                }
            }
        }
    }
    
    private GraphNode buildGraph(int[][] commits) {
          if (commits == null || commits.length == 0) {
            return null;
        }
        
        // step 1: constrcut the graph
        Map<Integer, GraphNode> map = new HashMap<>();
        
        for (int[] commit : commits) {
            int from = commit[0];
            int to = commit[1];
            
            GraphNode fromNode = null;
            if (map.containsKey(from)) {
                fromNode = map.get(from);
            } else {
                fromNode = new GraphNode(from);
            }
            
            if (map.containsKey(to)) {
                GraphNode toNode = map.get(to);
                fromNode.neighbors.add(toNode);
                
            } else {
                GraphNode toNode = new GraphNode(to);
                fromNode.neighbors.add(toNode);
                map.put(to, toNode);
            }
            
            map.put(from, fromNode);
        }
        
        // Step 2: find out the root of the graph
        GraphNode root = null;
        Map<GraphNode, Integer> inDegree = new HashMap<>();
        for (GraphNode node : map.values()) {
            if (!inDegree.containsKey(node)) {
                inDegree.put(node, 0);
            }
            
            for (GraphNode neighbor : node.neighbors) {
                if (inDegree.containsKey(neighbor)) {
                    int degree = inDegree.get(neighbor);
                    inDegree.put(neighbor, degree + 1);
                } else {
                    inDegree.put(neighbor, 1);
                }
            }
        }
        
        for (GraphNode node : inDegree.keySet()) {
            if (inDegree.get(node) == 0) {
                root = node;
                break;
            }
        }
        
        System.out.println("Root is " + root.val);
        
        return root;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] commits = new int[][]{{0, 1}, {1, 3}, {3, 5}, {0, 2}, {2, 4}, {4, 5}};
        
        GraphNode root = sol.buildGraph(commits);
        
        List<Integer> result = sol.findCommits(root);
        
        for (Integer elem : result) {
            System.out.println(elem);
        }
    }
    
    class GraphNode {
        int val;
        List<GraphNode> neighbors;
        
        public GraphNode(int val) {
            this.val = val;
            this.neighbors = new ArrayList<>();
        }
    }
}


Follow-up: 
找两个commits 的 LCA. 先BFS搜索一个node的 parents, 然后再搜索第二个node 的 parents.

Code (Java):
import java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

public class Solution {
    public List<Integer> findCommits(GraphNode root) {  
        List<Integer> result = new ArrayList<>();
        Set<GraphNode> visited = new HashSet<>();
        Queue<GraphNode> queue = new LinkedList<>();
        
        findCommitsHelper(root, visited, queue, result);
        
        return result;
    }
    
    private void findCommitsHelper(GraphNode root, Set<GraphNode> visited, 
                                   Queue<GraphNode> queue, List<Integer> result) {
        if (root == null) {
            return;
        }
        
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            GraphNode curr = queue.poll();
            if (!visited.contains(curr)) {
                visited.add(curr);
                result.add(curr.val);
                
                for (GraphNode neighbor : curr.neighbors) {
                    queue.offer(neighbor);
                }
            }
        }
    }

    public int findLCA(GraphNode node1, GraphNode node2) {
        if (node1 == null || node2 == null) {
            throw new NullPointerException();
        }
        
        List<Integer> result1 = new ArrayList<>();
        bfs(node1, result1);
        
        List<Integer> result2 = new ArrayList<>();
        bfs(node2, result2);
        
        int i = result1.size() - 1;
        int j = result2.size() - 1;
        
        for (; i >= 0 && j >= 0; i--, j--) {
            if (result1.get(i) == result2.get(j)) {
                continue;
            } else {
                break;
            }
        }
        
        return result1.get(i + 1);
    }
    
    private void bfs(GraphNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        
        Set<GraphNode> visited = new HashSet<>();
        Queue<GraphNode> queue = new LinkedList<>();
        
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            GraphNode curr = queue.poll();
            
            if (!visited.contains(curr)) {
                result.add(curr.val);
                visited.add(curr);
                
                for (GraphNode parent : curr.parents) {
                    queue.offer(parent);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] commits = new int[][]{{0, 1}, {1, 3}, {3, 5}, {0, 2}, {2, 4}, {4, 5}};
        
        GraphNode node1 = null;
        GraphNode node2 = null;
        
        // step 1: constrcut the graph
        Map<Integer, GraphNode> map = new HashMap<>();
        
        for (int[] commit : commits) {
            int from = commit[0];
            int to = commit[1];
            
            GraphNode fromNode = null;
            GraphNode toNode = null;
            if (map.containsKey(from)) {
                fromNode = map.get(from);
            } else {
                fromNode = new GraphNode(from);
            }
            
            if (map.containsKey(to)) {
                toNode = map.get(to);
                fromNode.neighbors.add(toNode);
            } else {
                toNode = new GraphNode(to);
                fromNode.neighbors.add(toNode);
                map.put(to, toNode);
            }
            
            toNode.parents.add(fromNode);
            map.put(from, fromNode);
            map.put(to, toNode);
        }
        
        // Step 2: find out the root of the graph
        GraphNode root = null;
        Map<GraphNode, Integer> inDegree = new HashMap<>();
        for (GraphNode node : map.values()) {
            if (!inDegree.containsKey(node)) {
                inDegree.put(node, 0);
            }
            
            for (GraphNode neighbor : node.neighbors) {
                if (inDegree.containsKey(neighbor)) {
                    int degree = inDegree.get(neighbor);
                    inDegree.put(neighbor, degree + 1);
                } else {
                    inDegree.put(neighbor, 1);
                }
            }
        }
        
        for (GraphNode node : inDegree.keySet()) {
            if (inDegree.get(node) == 0) {
                root = node;
                break;
            }
        }
        
        System.out.println("Root is " + root.val);
        
        node1 = map.get(3);
        node2 = map.get(4);
        
        
        List<Integer> result = sol.findCommits(root);
        
        System.out.println("Node 1 is " + node1.val + " node 2 is " + node2.val);
        int lca = sol.findLCA(node1, node2);
        
        System.out.println("LCA is " + lca);
        
        for (Integer elem : result) {
            System.out.println(elem);
        }
    }
    
    static class GraphNode {
        int val;
        List<GraphNode> neighbors;
        List<GraphNode> parents;
        
        public GraphNode(int val) {
            this.val = val;
            this.neighbors = new ArrayList<>();
            this.parents = new ArrayList<>();
        }
    }
}

No comments:

Post a Comment