Git Version
给一个commit（node），BFS输出所有commits (nodes)。followup :两个commits （nodes），找到他们的最近的公共parent，
思路： 就是先BFS一个，然后用map记录下其各个parent到这个commit(node)的距离，然后BFS第二个commit(node)， 碰到在map里的node，就算一个总距离，然后更新最短距离和的点， 最后最短距离和的点就是结果了，写完面试官也表示很满意。这个注意解释下BFS的复杂度为什么是O（V+E），他会问为什么不是O(V)之类的。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
public class GitVersion {
public static List<Integer> findCommits1(GitNode root) {
List<Integer> result = new ArrayList<>();
Set<GitNode> visited = new HashSet<>();
Queue<GitNode> queue = new LinkedList<>();
if (root == null) {
return result;
}
queue.offer(root);
visited.add(root);
while (!queue.isEmpty()) {
GitNode curr = queue.poll();
result.add(curr.val);
for (GitNode neighbor : curr.neighbors) {
if(!visited.contains(neighbor)){
queue.offer(neighbor);
visited.add(neighbor);
}
}
}
return result;
}
//back up for first step
public List<Integer> findCommits(GitNode root) {
List<Integer> result = new ArrayList<>();
Set<GitNode> visited = new HashSet<>();
Queue<GitNode> queue = new LinkedList<>();
findCommitsHelper(root, visited, queue, result);
return result;
}
private void findCommitsHelper(GitNode root, Set<GitNode> visited,
Queue<GitNode> queue, List<Integer> result) {
if (root == null) {
return;
}
queue.offer(root);
while (!queue.isEmpty()) {
GitNode curr = queue.poll();
if (!visited.contains(curr)) {
visited.add(curr);
result.add(curr.val);
for (GitNode neighbor : curr.neighbors) {
queue.offer(neighbor);
}
}
}
}
public int findLCA(GitNode node1, GitNode 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 );
}
public int findLCALate(GitNode node1, GitNode node2) {
if (node1 == null || node2 == null) {
throw new NullPointerException();
}
List<Integer> result1 = new ArrayList<>();
bfs(node1, result1);
Set<GitNode> visited = new HashSet<>();
Queue<GitNode> queue = new LinkedList<>();
queue.offer(node2);
while (!queue.isEmpty()) {
GitNode curr = queue.poll();
if(result1.contains(curr.val)) return curr.val;
if (!visited.contains(curr)) {
visited.add(curr);
for (GitNode parent : curr.parents) {
queue.offer(parent);
}
}
}
return 0;
}
public int findLCAOffer(GitNode node1, GitNode node2) {
if (node1 == null || node2 == null) {
throw new NullPointerException();
}
List<Integer> result1 = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
bfs1(node1, result1, map);
Set<GitNode> visited = new HashSet<>();
Queue<GitNode> queue = new LinkedList<>();
queue.offer(node2);
visited.add(node2);
int count = 0;
int min = -1;
int res = Integer.MAX_VALUE;
while (!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++){
GitNode curr = queue.poll();
if(result1.contains(curr.val)){
if(min == -1 || map.get(curr.val) + count < min){
res = curr.val;
min = map.get(curr.val) + count ;
}
}
for (GitNode parent : curr.parents) {
if (!visited.contains(parent)) {
queue.offer(parent);
visited.add(parent);
}
}
}
count++;
}
return res;
}
private void bfs(GitNode root, List<Integer> result) {
if (root == null) {
return;
}
Set<GitNode> visited = new HashSet<>();
Queue<GitNode> queue = new LinkedList<>();
queue.offer(root);
visited.add(root);
while (!queue.isEmpty()) {
GitNode curr = queue.poll();
result.add(curr.val);
for (GitNode parent : curr.parents) {
if (!visited.contains(curr)) {
visited.add(curr);
queue.offer(parent);
}
}
}
}
private void bfs1(GitNode root, List<Integer> result, Map<Integer, Integer> map) {
if (root == null) {
return;
}
Set<GitNode> visited = new HashSet<>();
Queue<GitNode> queue = new LinkedList<>();
queue.offer(root);
visited.add(root);
int count = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++){
GitNode curr = queue.poll();
result.add(curr.val);
map.put(curr.val, count);
for (GitNode parent : curr.parents) {
if (!visited.contains(parent)) {
queue.offer(parent);
visited.add(parent);
}
}
}
count++;
}
}
public static void main(String[] args) {
GitVersion sol = new GitVersion();
int[][] commits = new int[][]{{0, 1}, {0, 2},{1, 3}, {3, 5}, {2, 4}, {1, 4},{1,3},{3,7},{7,6},{6,4}};
GitNode node1 = null;
GitNode node2 = null;
// step 1: constrcut the graph
Map<Integer, GitNode> map = new HashMap<>();
for (int[] commit : commits) {
int from = commit[0];
int to = commit[1];
GitNode fromNode = null;
GitNode toNode = null;
if (map.containsKey(from)) {
fromNode = map.get(from);
} else {
fromNode = new GitNode(from);
}
if (map.containsKey(to)) {
toNode = map.get(to);
fromNode.neighbors.add(toNode);
} else {
toNode = new GitNode(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
GitNode root = null;
Map<GitNode, Integer> inDegree = new HashMap<>();
for (GitNode node : map.values()) {
if (!inDegree.containsKey(node)) {
inDegree.put(node, 0);
}
for (GitNode neighbor : node.neighbors) {
if (inDegree.containsKey(neighbor)) {
int degree = inDegree.get(neighbor);
inDegree.put(neighbor, degree + 1);
} else {
inDegree.put(neighbor, 1);
}
}
}
for (GitNode node : inDegree.keySet()) {
if (inDegree.get(node) == 0) {
root = node;
break;
}
}
System.out.println("Root is " + root.val);
node1 = map.get(4);
node2 = map.get(5);
List<Integer> result = sol.findCommits(root);
List<Integer> result2 = sol.findCommits1(root);
System.out.println(result);
System.out.println(result2);
int lca =1;
//int lca = sol.findLCA(node1, node2);
// System.out.println("LCA is " + lca);
lca = sol.findLCAOffer(node1, node2);
System.out.println("LCA offer is " + lca);
lca = sol.findLCALate(node1, node2);
System.out.println("LCA late is " + lca);
for (Integer elem : result) {
System.out.println(elem);
}
}
static class GitNode {
int val;
List<GitNode> neighbors;
List<GitNode> parents;
public GitNode(int val) {
this.val = val;
this.neighbors = new ArrayList<>();
this.parents = new ArrayList<>();
}
}
}