Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 112
Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. Assume that each node in the tree also has a pointer to its parent.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

Pull request:
Day112
Resolves #235.

Patch:
diff --git a/README.md b/README.md
index 948c7f4..af7c2fc 100644
--- a/README.md
+++ b/README.md
@@ -121,5 +121,6 @@ problems from
 * [Day 109](https://github.com/vaskoz/dailycodingproblem-go/issues/229)
 * [Day 110](https://github.com/vaskoz/dailycodingproblem-go/issues/231)
 * [Day 111](https://github.com/vaskoz/dailycodingproblem-go/issues/232)
+* [Day 112](https://github.com/vaskoz/dailycodingproblem-go/issues/235)
 * [Day 113](https://github.com/vaskoz/dailycodingproblem-go/issues/236)
 * [Day 114](https://github.com/vaskoz/dailycodingproblem-go/issues/237)
diff --git a/day112/problem.go b/day112/problem.go
new file mode 100644
index 0000000..f42e86e
--- /dev/null
+++ b/day112/problem.go
@@ -0,0 +1,33 @@
+package day112
+
+// Node has a pointer to its parent.
+type Node struct {
+	Parent *Node
+}
+
+// LowestCommonAncestor returns the lowest common ancestor.
+// Returns nil if the two nodes don't share a common node.
+// Assumes the graph is a DAG. Any cycles returns nil.
+// Runs in O(N) time and stores 1 path so technically O(N) memory.
+func LowestCommonAncestor(n1, n2 *Node) *Node {
+	path := make(map[*Node]struct{})
+	for n1 != nil {
+		if _, seen := path[n1]; seen {
+			return nil // there is a cycle
+		}
+		path[n1] = struct{}{}
+		n1 = n1.Parent
+	}
+	path2 := make(map[*Node]struct{})
+	for n2 != nil {
+		if _, seen := path2[n2]; seen {
+			return nil // there is a cycle
+		}
+		path2[n2] = struct{}{}
+		if _, found := path[n2]; found {
+			return n2
+		}
+		n2 = n2.Parent
+	}
+	return nil
+}


Test patch:
diff --git a/day112/problem_test.go b/day112/problem_test.go
new file mode 100644
index 0000000..70a0875
--- /dev/null
+++ b/day112/problem_test.go
@@ -0,0 +1,40 @@
+package day112
+
+import "testing"
+
+func TestLowestCommonAncestor(t *testing.T) {
+	t.Parallel()
+	lca := &Node{&Node{&Node{}}}
+	n1 := &Node{lca}
+	n2 := &Node{&Node{&Node{lca}}}
+	if result := LowestCommonAncestor(n1, n2); result != lca {
+		t.Errorf("LCA did not match correctly")
+	}
+	n3 := &Node{&Node{&Node{}}}
+	if result := LowestCommonAncestor(n3, n2); result != nil {
+		t.Errorf("LCA is nil because the nodes are from separate graphs")
+	}
+	cycle := &Node{&Node{}}
+	cycle.Parent.Parent = cycle
+	if result := LowestCommonAncestor(cycle, n2); result != nil {
+		t.Errorf("LCA is nil because there is a cycle in first arg")
+	}
+	if result := LowestCommonAncestor(n2, cycle); result != nil {
+		t.Errorf("LCA is nil because there is a cycle in second arg")
+	}
+}
+
+func BenchmarkLowestCommonAncestor(b *testing.B) {
+	lca := &Node{&Node{&Node{}}}
+	n1 := &Node{lca}
+	n2 := &Node{&Node{&Node{lca}}}
+	n3 := &Node{&Node{&Node{}}}
+	cycle := &Node{&Node{}}
+	cycle.Parent.Parent = cycle
+	for i := 0; i < b.N; i++ {
+		LowestCommonAncestor(n1, n2)
+		LowestCommonAncestor(n3, n2)
+		LowestCommonAncestor(cycle, n2)
+		LowestCommonAncestor(n2, cycle)
+	}
+}