Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Intersection Point
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given two singly linked lists that intersect at some point, find the intersecting node. The lists are non-cyclical.

For example, given A = 3 -> 7 -> 8 -> 10 and B = 99 -> 1 -> 8 -> 10, return the node with value 8.

In this example, assume nodes with the same value are the exact same node objects.

Do this in O(M + N) time (where M and N are the lengths of the lists) and constant space.

Pull request:
Day20
Resolves #49.

Patch:
diff --git a/README.md b/README.md
index 61edbc3..8697aff 100644
--- a/README.md
+++ b/README.md
@@ -33,3 +33,4 @@ problems from
 * [Day 19 N-Queens](https://github.com/vaskoz/dailycodingproblem-go/issues/43)
 * [Day 19 Flight Itinerary](https://github.com/vaskoz/dailycodingproblem-go/issues/45)
 * [Day 19 Sudoku Solver](https://github.com/vaskoz/dailycodingproblem-go/issues/47)
+* [Day 20](https://github.com/vaskoz/dailycodingproblem-go/issues/49)
diff --git a/day20/problem.go b/day20/problem.go
new file mode 100644
index 0000000..7352586
--- /dev/null
+++ b/day20/problem.go
@@ -0,0 +1,40 @@
+package day20
+
+// Node is a singly linked list. NOTE: Doubly-linked list won't work here with shared paths.
+type Node struct {
+	Value interface{}
+	Next  *Node
+}
+
+// FindCommonNode finds the common element in a linked list in O(N+M) time and O(1) space.
+func FindCommonNode(one, two *Node) *Node {
+	var oneLen, twoLen int
+	for e := one; e != nil; e = e.Next {
+		oneLen++
+	}
+	for e := two; e != nil; e = e.Next {
+		twoLen++
+	}
+	var longer, shorter *Node
+	var diff int
+	if oneLen > twoLen {
+		longer = one
+		shorter = two
+		diff = oneLen - twoLen
+	} else {
+		longer = two
+		shorter = one
+		diff = twoLen - oneLen
+	}
+	for i := 0; i < diff; i++ {
+		longer = longer.Next
+	}
+	for longer != nil {
+		if longer == shorter {
+			return longer
+		}
+		longer = longer.Next
+		shorter = shorter.Next
+	}
+	return nil
+}


Test patch:
diff --git a/day20/problem_test.go b/day20/problem_test.go
new file mode 100644
index 0000000..765a75b
--- /dev/null
+++ b/day20/problem_test.go
@@ -0,0 +1,48 @@
+package day20
+
+import (
+	"testing"
+)
+
+func createTwoSharedLists() (*Node, *Node, *Node) {
+	common := &Node{1015, &Node{444, nil}}
+	one := &Node{"abc", &Node{"def", &Node{"ghi", common}}}
+	two := &Node{111, common}
+	return one, two, common
+}
+
+func createTwoIndependentLists() (*Node, *Node, *Node) {
+	one := &Node{"abc", &Node{"def", &Node{"ghi", nil}}}
+	two := &Node{111, nil}
+	return one, two, nil
+}
+
+func TestFindCommonNode(t *testing.T) {
+	t.Parallel()
+	one, two, common := createTwoSharedLists()
+	if result := FindCommonNode(one, two); result != common {
+		t.Error("Expected these two be the same pointer")
+	}
+	one, two = two, one // swap
+	if result := FindCommonNode(one, two); result != common {
+		t.Error("Expected these two be the same pointer")
+	}
+	one, two, common = createTwoIndependentLists()
+	if result := FindCommonNode(one, two); result != common {
+		t.Error("Expected these two be nil")
+	}
+	one, two = two, one // swap
+	if result := FindCommonNode(one, two); result != common {
+		t.Error("Expected these two be nil")
+	}
+}
+
+func BenchmarkFindCommonNode(b *testing.B) {
+	one, two, _ := createTwoSharedLists()
+	onei, twoi, _ := createTwoIndependentLists()
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		FindCommonNode(one, two)
+		FindCommonNode(onei, twoi)
+	}
+}
diff --git a/sudoku/problem_test.go b/sudoku/problem_test.go
index 01ddc9b..ff3067e 100644
--- a/sudoku/problem_test.go
+++ b/sudoku/problem_test.go
@@ -32,6 +32,7 @@ var testcases = []struct {
 }
 
 func TestSolver(t *testing.T) {
+	t.Parallel()
 	for _, tc := range testcases {
 		if result, _ := Solver(tc.board, tc.n); !reflect.DeepEqual(result, tc.expected) {
 			t.Errorf("Expected %v but got %v", tc.expected, result)