CareerCup

LCA(String a, String b, String[] input) {
	HashMap<String, Node> map = new HashMap();
	Node root = nul;;
	for (String line : input) {
		String p = line.substring( 0, line.indexOf(" ") );
		String c = line.substring(line.indexOf(" ") + 1, line.length());
		Node parent, child;

		if ( map.containsKey(p) ) {
			parent = map.get(p);
			if (root == null) {
				root = parent;
			}
		} else {
			parent = new Node();
			map.put(p, parent)
		}

		if ( map.containsKey(c) ) {
			child = map.get(c);
		} else {
			p = new Node();
			map.put(c, child)
		}

		parent.children.add(child);
		child.parent = parent;
	}

	dfs(root, 1);
	Node na = ma.get(a);
	Node nb = ma.get(b);

	if ( na.level > nb.level ) {
		na = align(nb.level, na);
	} else {
		nb = align(na.level, nb);
	}
	while (na != nb) {
		for (int i = na.parents.size() - 1; i >= 0; i --) {
			if (na.parents.get(i) != nb.parents.get(i)) {
				na = na.parents.get(i);
				nb = nb.parents.get(i);
				break;
			}
		}
		na = na.parent;
		nb = nb.parent;
	}
	return na;
}


Node align(int level, Node node) {
	if (node.level == level) {
		return node;
	}
	for ( int i = node.parents.size() - 1; i >= 0; i-- ) {
		if ( node.parents.get(i).level >= level ) {
			return align(node.parents.get(i));
		}
	}
}

void dfs(Node root, int level) {
	root.level = level;
	if ( root.parent != null ) {
		Node cur = root.parent;
		int index = 0;
		while ( true) {
			root.parents.add(cur);
			if (cur.parents.size() > index) {
				cur = cur.parents.get(index);
				index++;
			} else {
				break;
			}
		}
	}

	for (Node child : root.children) {
		dfs(child, level + 1);
	}
}

You just need to construct the tree. No need to do an LCA.

Use an adjacency list as shown in anon's code and build a binary tree or adjacency map to represent the relationships. Former is preferred since the graph is very sparse (max three edges per node - 2 for child, 1 for parent).

You could also use an array representation to represent the tree such that 2*i and 2*i+1 are children of i item. However, it would waste space when the graph is linear like a list.

Create a binary tree with information given and then a simple BFS would give the LCA (Least Common Ancestor). Of course, we need to keep a stack to keep track the latest ancestor being explored.