cslittleye
BAN USER1) Brute force method: O(n^2), n is the number of nodes. Take each node as root, we find the longest path starting from it. This can be done in O(n) using DFS or BFS. Then, we take the longest one of the longest paths starting from each node.
2) Dynamic Programming: O(n). The idea metioned above is extended to a general tree and more details are added. Take a random node as root (e.g., 0), the longest path either passes this node or not. If the longest path does not pass this node, then it must come from one of the subtrees (can be more than two). Otherwise, the longest path must pass the root and it can be divided into three parts, i.e., path from a subtree root to leave, root, path from another subtree root to leave. Then, the length of the longest path should be length(longestSubrootToLeavePath) + 1 + length(secondLongestSubrootToLeavePath) + 1.
The root to leave path is deinfed as the path from the root to the leave. Subroot is the root of one of the subtrees. Therefore, we need to find three paths for a tree, the longest path, longest path from a subtree root to a leave, the second longest path from a sub tree root a leave. Two subtrees are different otherwise the composed path from them will not pass the root. Then longest path with a tree = max(longest path passing root, longest paths in subtrees).
3) Take a random node (a), find the farthest node (b) from the node a. Then find the farthest node (c) from the node (b). Why is it correct? Think node a as the root, the node b must a leave (otherwise the leaves in this subtree must have longer paths). If the longest path passes the root, then the longest path can be divided into three parts, path1 + root + path2. It is easy to understand that path1 or path2 has to starts with node b and path2 should be the second longest path from the root. At the same time, the other end of the second longest path is the farthest node from node b. If the longest path does not pass the root, then the longest path in the subtree T (root d) of a where node b resdies. More importantly, b is still the farthest node from the root d. Therefore, we can proceed the same reasoning as above.
import java.util.*;
public class LongestPathInTree {
//tree is represented as an adjacent list
private List<List<Integer>> adjacentList;
private Path longestPath;
//is a node visited?
private boolean[] visited;
public LongestPathInTree (List<List<Integer>> adjacentList) {
this.adjacentList = adjacentList;
this.visited = new boolean[adjacentList.size()];
}
public Path getLongestPath() {
return longestPath;
}
//traverse paths between every pair of nodes
public void bruteForceMethod() {
//default path is shortest
longestPath = new Path();
for(int i = 0; i < adjacentList.size(); i++) {
Arrays.fill(visited,false);
depthFirstSearchPath(i,i,0);
}
}
public void depthFirstSearchPath(int treeRoot, int subTreeRoot, int pathLength) {
List<Integer> neighbors = adjacentList.get(subTreeRoot);
//in fact, only leave nodes need checking but it does not harm to check every node
if(pathLength > longestPath.getLength()) {
longestPath.setStart(treeRoot);
longestPath.setEnd(subTreeRoot);
longestPath.setLength(pathLength);
}
for(int u : neighbors) {
if(!visited[u]) {
visited[u] = true;
depthFirstSearchPath(treeRoot, u, pathLength+1);
}
}
}
public void dpMethod() {
Arrays.fill(visited,false);
int root = 0;
longestPath = findLongestPath(root)[0];
}
public Path[] findLongestPath(int root) {
visited[root] = true;
//longest path in subtrees (don't have to pass the subtree root)
Path longestPathInSubtrees = null;
//longest path from a subtree root to a leave
Path longestPathFromSubrootToSubLeave = null;
//second longest path from another subtree root to a leave
//the two subtrees must be different
Path secondLongestPathFromSubrootToSubLeave = null;
List<Integer> neighbors = adjacentList.get(root);
//System.out.println(neighbors);
for(int u : neighbors) {
if(!visited[u]) {
//path[0] is the longest path in a subtree
//path[1] is the longest path from the subtree root to a leave
Path[] paths = findLongestPath(u);
if(longestPathInSubtrees == null
|| longestPathInSubtrees.getLength() < paths[0].getLength()) {
longestPathInSubtrees = paths[0];
}
if(longestPathFromSubrootToSubLeave == null
|| longestPathFromSubrootToSubLeave.getLength() < paths[1].getLength()) {
secondLongestPathFromSubrootToSubLeave = longestPathFromSubrootToSubLeave;
longestPathFromSubrootToSubLeave = paths[1];
} else if(secondLongestPathFromSubrootToSubLeave == null
|| secondLongestPathFromSubrootToSubLeave.getLength() < paths[0].getLength() ) {
secondLongestPathFromSubrootToSubLeave = paths[1];
}
}
}
//System.out.println("Root: " + root);
//System.out.println(longestPathFromSubrootToSubLeave);
//System.out.println(secondLongestPathFromSubrootToSubLeave);
if (longestPathFromSubrootToSubLeave == null
&& secondLongestPathFromSubrootToSubLeave == null) {
//leave
return new Path[] {new Path(root, root, 0), new Path(root, root, 0)};
}else {
//the potential longest path passing root
Path path = null;
//this node might only have one subtree
if(secondLongestPathFromSubrootToSubLeave == null) {
path = new Path(longestPathFromSubrootToSubLeave.getEnd(),
root, longestPathFromSubrootToSubLeave.getLength()+1);
}else {
path = new Path(longestPathFromSubrootToSubLeave.getEnd(),
secondLongestPathFromSubrootToSubLeave.getEnd(),
longestPathFromSubrootToSubLeave.getLength() + 1
+ secondLongestPathFromSubrootToSubLeave.getLength() + 1);
}
Path[] paths = new Path[2];
//the longest path in the tree
paths[0] = path.getLength() > longestPathInSubtrees.getLength() ? path : longestPathInSubtrees;
//the longest path from the root to a leave
paths[1] = new Path(root, longestPathFromSubrootToSubLeave.getEnd(),
longestPathFromSubrootToSubLeave.getLength()+1);
return paths;
}
}
public void farthestFarthestMethod() {
longestPath = new Path();
int root = 0;
Arrays.fill(visited,false);
depthFirstSearchPath(root, root, 0);
Arrays.fill(visited,false);
root = longestPath.getEnd();
Arrays.fill(visited, false);
depthFirstSearchPath(root, root, 0);
}
public static void main(String[] args) {
List<List<Integer>> tree = new ArrayList<List<Integer>>();
List<Integer> ls0 = new ArrayList<Integer>();
ls0.add(1);
ls0.add(2);
ls0.add(3);
tree.add(ls0);
List<Integer> ls1 = new ArrayList<Integer>();
ls1.add(0);
ls1.add(4);
ls1.add(5);
tree.add(ls1);
List<Integer> ls2 = new ArrayList<Integer>();
ls2.add(0);
ls2.add(6);
tree.add(ls2);
List<Integer> ls3 = new ArrayList<Integer>();
ls3.add(0);
tree.add(ls3);
List<Integer> ls4 = new ArrayList<Integer>();
ls4.add(1);
ls4.add(7);
tree.add(ls4);
List<Integer> ls5 = new ArrayList<Integer>();
ls5.add(1);
ls5.add(9);
tree.add(ls5);
List<Integer> ls6 = new ArrayList<Integer>();
ls6.add(2);
ls6.add(8);
tree.add(ls6);
List<Integer> ls7 = new ArrayList<Integer>();
ls7.add(4);
ls7.add(13);
tree.add(ls7);
List<Integer> ls8 = new ArrayList<Integer>();
ls8.add(6);
tree.add(ls8);
List<Integer> ls9 = new ArrayList<Integer>();
ls9.add(5);
ls9.add(10);
tree.add(ls9);
List<Integer> ls10 = new ArrayList<Integer>();
ls10.add(9);
ls10.add(11);
tree.add(ls10);
List<Integer> ls11 = new ArrayList<Integer>();
ls11.add(10);
ls11.add(12);
tree.add(ls11);
List<Integer> ls12 = new ArrayList<Integer>();
ls12.add(11);
tree.add(ls12);
List<Integer> ls13 = new ArrayList<Integer>();
ls13.add(7);
ls13.add(14);
tree.add(ls13);
List<Integer> ls14 = new ArrayList<Integer>();
ls14.add(13);
ls14.add(15);
tree.add(ls14);
List<Integer> ls15 = new ArrayList<Integer>();
ls15.add(14);
tree.add(ls15);
LongestPathInTree finder = new LongestPathInTree(tree);
finder.bruteForceMethod();
System.out.println(finder.getLongestPath());
finder.dpMethod();
System.out.println(finder.getLongestPath());
finder.farthestFarthestMethod();
System.out.println(finder.getLongestPath());
}
}
class Path {
private int start;
private int end;
private int length;
public Path() {
this.start = Integer.MIN_VALUE;
this.end = Integer.MIN_VALUE;
this.length = Integer.MIN_VALUE;
}
public Path(int start, int end, int length) {
this.start = start;
this.end = end;
this.length = length;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
public int getLength() {
return length;
}
public void setStart(int start) {
this.start = start;
}
public void setEnd(int end) {
this.end = end;
}
public void setLength(int length) {
this.length = length;
}
public String toString() {
return "start: " + start + " end: " + end + " length: " + length;
}
}
You can do sort and comparison as suggested above although you don't have to remove the duplicates. After sort, set indexa and indexb to 0, compare the character at indexa and indexb, if different, return false. Otherwise, move indexa and indexb to next different character and repeat.
- cslittleye October 12, 2012In this case, a HashMap of b with frequencies of characters should be built. Then, we check whether a character from a exists in HashMap, if not, return false. If it is in the map, check whether it's frequency is zero. If yes, return false. Otherwise, decrease the frequency by one. Proceed with next character in a.
- cslittleye October 12, 20121) brute force: O (mn), m is the length of a and n is the length of b
public static boolean allExists(String a, String b) {
for(int i = 0; i < a.length(); i++) {
boolean exist = false;
for(int j = 0; j < b.length; j++) {
if(a.chartAt(i) == b.charAt(j)) {
exist = true;
break;
}
}
if(!exist) return false;
}
return true;
}
2) HashSet --> build a hash set of b, O(m) + O(n)
public static boolean allExist(String a, String b) {
Set<Character> set = new HashSet<Character>();
for(int i = 0; i < b.length(); i++) {
set.add(b.charAt(i));
}
for(int i = 0; i < a.length; i++) {
if(!set.contains(a.charAt(i))) {
return false;
}
}
return true;
}
1) only query the number of users online once O(n): We can compare the each user's login time and logout time to the given time. If the login time is less than or equal to the given time and the logout time is greater than the given time, then then user is online.
2) Query m times the number of users online, where is m is large(O(mlogn + nlogn) instead of O(m*n)): we can precompute the number of users at certain times (times in the login and logout). Then we sort the times. Given a query time, we use binary search to find the largest time less than or equal to the given time and return the number of users online for this time.
- cslittleye October 14, 2012