Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 160
Good morning! Here's your coding interview problem for today.

This problem was asked by Uber.

Given a tree where each edge has a weight, compute the length of the longest path in the tree.

For example, given the following tree:
```
   a
  /|\
 b c d
    / \
   e   f
  / \
 g   h
```
and the weights: a-b: 3, a-c: 5, a-d: 8, d-e: 2, d-f: 4, e-g: 1, e-h: 1, the longest path would be c -> a -> d -> f, with a length of 17.

The path does not have to pass through the root, and each node can have any amount of children.

Pull request:
Day160
Resolves #333.

Patch:
diff --git a/README.md b/README.md
index 816f4f6..aa3640a 100644
--- a/README.md
+++ b/README.md
@@ -170,6 +170,7 @@ problems from
 * [Day 157](https://github.com/vaskoz/dailycodingproblem-go/issues/327)
 * [Day 158](https://github.com/vaskoz/dailycodingproblem-go/issues/329)
 * [Day 159](https://github.com/vaskoz/dailycodingproblem-go/issues/331)
+* [Day 160](https://github.com/vaskoz/dailycodingproblem-go/issues/333)
 * [Day 161](https://github.com/vaskoz/dailycodingproblem-go/issues/334)
 * [Day 162](https://github.com/vaskoz/dailycodingproblem-go/issues/335)
 * [Day 163](https://github.com/vaskoz/dailycodingproblem-go/issues/336)
diff --git a/day160/problem.go b/day160/problem.go
new file mode 100644
index 0000000..d3d1b93
--- /dev/null
+++ b/day160/problem.go
@@ -0,0 +1,71 @@
+package day160
+
+// WeightedEdges is the weight of an undirected edge.
+type WeightedEdges struct {
+	start, end string
+	weight     int
+}
+
+// Graph is an undirected weighted graph.
+type Graph map[string]map[string]int
+
+// LongestPath returns the weight of the longest path
+// in an undirected tree.
+func LongestPath(weights []WeightedEdges) int {
+	g, start := buildAdjacencyMatrix(weights)
+	if len(g) == 0 {
+		return 0
+	}
+	for n := range g {
+		start = n
+		break
+	}
+	newStart, _ := farthestNode(start, g)
+	_, dist := farthestNode(newStart, g)
+	return dist
+}
+
+func farthestNode(start string, g Graph) (string, int) {
+	var farthest string
+	var dist int
+	visited := make(map[string]int)
+	visited[start] = 0
+	n := len(g)
+	queue := make([]string, 0, n)
+	queue = append(queue, start)
+	for len(queue) != 0 {
+		nextQ := make([]string, 0, n)
+		for _, curr := range queue {
+			for node, d := range g[curr] {
+				if _, seen := visited[node]; !seen {
+					visited[node] = visited[curr] + d
+					if visited[node] > dist {
+						farthest = node
+						dist = visited[node]
+					}
+					nextQ = append(nextQ, node)
+				}
+			}
+		}
+		queue = nextQ
+	}
+	return farthest, dist
+}
+
+func buildAdjacencyMatrix(weights []WeightedEdges) (Graph, string) {
+	if len(weights) == 0 {
+		return nil, ""
+	}
+	g := make(Graph)
+	for _, w := range weights {
+		if g[w.start] == nil {
+			g[w.start] = make(map[string]int)
+		}
+		if g[w.end] == nil {
+			g[w.end] = make(map[string]int)
+		}
+		g[w.start][w.end] = w.weight
+		g[w.end][w.start] = w.weight
+	}
+	return g, weights[0].start
+}


Test patch:
diff --git a/day160/problem_test.go b/day160/problem_test.go
new file mode 100644
index 0000000..7ac934e
--- /dev/null
+++ b/day160/problem_test.go
@@ -0,0 +1,37 @@
+package day160
+
+import "testing"
+
+var testcases = []struct {
+	weights     []WeightedEdges
+	longestPath int
+}{
+	{[]WeightedEdges{
+		{"a", "b", 3},
+		{"a", "c", 5},
+		{"a", "d", 8},
+		{"d", "e", 2},
+		{"d", "f", 4},
+		{"e", "g", 1},
+		{"e", "h", 1},
+	}, 17},
+	{[]WeightedEdges{}, 0},
+	{nil, 0},
+}
+
+func TestLongestPath(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if path := LongestPath(tc.weights); path != tc.longestPath {
+			t.Errorf("Expected %v got %v", tc.longestPath, path)
+		}
+	}
+}
+
+func BenchmarkLongestPath(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LongestPath(tc.weights)
+		}
+	}
+}