Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 344
Good morning! Here's your coding interview problem for today.

This problem was asked by Adobe.

You are given a tree with an even number of nodes. Consider each connection between a parent and child node to be an "edge". You would like to remove some of these edges, such that the disconnected subtrees that remain each have an even number of nodes.

For example, suppose your input was the following tree:
```
   1
  / \ 
 2   3
    / \ 
   4   5
 / | \
6  7  8
```
In this case, removing the edge `(3, 4)` satisfies our requirement.

Write a function that returns the _maximum_ number of edges you can remove while still satisfying this requirement.

Pull request:
Day344
Resolves #686.

Patch:
diff --git a/README.md b/README.md
index a2e6518..dc77d6b 100644
--- a/README.md
+++ b/README.md
@@ -337,6 +337,7 @@ problems from
 * [Day 340](https://github.com/vaskoz/dailycodingproblem-go/issues/679)
 * [Day 342](https://github.com/vaskoz/dailycodingproblem-go/issues/682)
 * [Day 343](https://github.com/vaskoz/dailycodingproblem-go/issues/685)
+* [Day 344](https://github.com/vaskoz/dailycodingproblem-go/issues/686)
 * [Day 345](https://github.com/vaskoz/dailycodingproblem-go/issues/687)
 * [Day 346](https://github.com/vaskoz/dailycodingproblem-go/issues/688)
 * [Day 347](https://github.com/vaskoz/dailycodingproblem-go/issues/689)
diff --git a/day344/problem.go b/day344/problem.go
new file mode 100644
index 0000000..ad7f160
--- /dev/null
+++ b/day344/problem.go
@@ -0,0 +1,53 @@
+package day344
+
+// Tree is an undirected tree.
+type Tree map[int]map[int]struct{}
+
+// MaxRemovedEdgesEvenSubtrees returns the maximum number of edges
+// that can be removed to result in subtrees that all have even
+// number of nodes.
+func MaxRemovedEdgesEvenSubtrees(t Tree) int {
+	nt := make(Tree)
+
+	var firstStart int
+	for start, toMap := range t {
+		firstStart = start
+
+		if _, exists := nt[start]; !exists {
+			nt[start] = make(map[int]struct{})
+		}
+
+		for to := range toMap {
+			if _, exists := nt[to]; !exists {
+				nt[to] = make(map[int]struct{})
+			}
+
+			nt[start][to] = struct{}{}
+			nt[to][start] = struct{}{}
+		}
+	}
+
+	visited := make(map[int]struct{}, len(nt)+1)
+	_, result := dfs(nt, firstStart, visited, 0)
+
+	return result
+}
+
+func dfs(t Tree, start int, visited map[int]struct{}, result int) (int, int) {
+	var nodes, subtreeCount int
+
+	visited[start] = struct{}{}
+
+	for to := range t[start] {
+		if _, seen := visited[to]; !seen {
+			subtreeCount, result = dfs(t, to, visited, result)
+			if subtreeCount%2 == 0 {
+				result++
+			} else {
+				nodes += subtreeCount
+			}
+		}
+	}
+
+	return nodes + 1, result
+}


Test patch:
diff --git a/day344/problem_test.go b/day344/problem_test.go
new file mode 100644
index 0000000..a062ccf
--- /dev/null
+++ b/day344/problem_test.go
@@ -0,0 +1,66 @@
+package day344
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	tree     Tree
+	expected int
+}{
+	{
+		Tree{
+			1: map[int]struct{}{
+				2: struct{}{},
+				3: struct{}{},
+			},
+			3: map[int]struct{}{
+				4: struct{}{},
+				5: struct{}{},
+			},
+			4: map[int]struct{}{
+				6: struct{}{},
+				7: struct{}{},
+				8: struct{}{},
+			},
+		},
+		2,
+	},
+	{
+		Tree{
+			0: map[int]struct{}{
+				2: struct{}{},
+				4: struct{}{},
+				1: struct{}{},
+			},
+			2: map[int]struct{}{
+				3: struct{}{},
+			},
+			4: map[int]struct{}{
+				5: struct{}{},
+			},
+			5: map[int]struct{}{
+				6: struct{}{},
+				7: struct{}{},
+			},
+		},
+		2,
+	},
+}
+
+func TestMaxRemovedEdgesEvenSubtrees(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if result := MaxRemovedEdgesEvenSubtrees(tc.tree); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMaxRemovedEdgesEvenSubtrees(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxRemovedEdgesEvenSubtrees(tc.tree)
+		}
+	}
+}