Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 207
Good morning! Here's your coding interview problem for today.

This problem was asked by Dropbox.

Given an undirected graph G, check whether it is bipartite. Recall that a graph is bipartite if its vertices can be divided into two independent sets, U and V, such that no edge connects vertices of the same set.

Pull request description:
Day207
Resolves #426.

Patch:
diff --git a/README.md b/README.md
index 1fc5241..45be3b1 100644
--- a/README.md
+++ b/README.md
@@ -216,4 +216,5 @@ problems from
 * [Day 203](https://github.com/vaskoz/dailycodingproblem-go/issues/419)
 * [Day 204](https://github.com/vaskoz/dailycodingproblem-go/issues/421)
 * [Day 206](https://github.com/vaskoz/dailycodingproblem-go/issues/424)
+* [Day 207](https://github.com/vaskoz/dailycodingproblem-go/issues/426)
 * [Day 208](https://github.com/vaskoz/dailycodingproblem-go/issues/427)
diff --git a/day207/problem.go b/day207/problem.go
new file mode 100644
index 0000000..1b16e26
--- /dev/null
+++ b/day207/problem.go
@@ -0,0 +1,48 @@
+package day207
+
+type color int
+
+const (
+	blue color = iota
+	green
+)
+
+// Node is a node in the graph.
+type Node string
+
+// UndirectedGraph has an edge going in each direction.
+type UndirectedGraph map[Node]map[Node]struct{}
+
+// IsBipartiteGraph answer if an UndirectedGraph
+// is actually bipartite.
+func IsBipartiteGraph(g UndirectedGraph) bool {
+	colors := make(map[Node]color, len(g))
+	var n Node
+	for n1 := range g {
+		n = n1
+		break
+	}
+	result := isBipartiteGraph(g, n, colors)
+	return result && len(colors) == len(g)
+}
+
+func isBipartiteGraph(g UndirectedGraph, n Node, colors map[Node]color) bool {
+	if len(g) == len(colors) {
+		return true
+	}
+	nextColor := blue
+	if colors[n] == blue {
+		nextColor = green
+	}
+	for node := range g[n] {
+		if c, found := colors[node]; !found {
+			colors[node] = nextColor
+			if !isBipartiteGraph(g, node, colors) {
+				return false
+			}
+		} else if c != nextColor {
+			return false
+		}
+	}
+	return true
+}


Test patch:
diff --git a/day207/problem_test.go b/day207/problem_test.go
new file mode 100644
index 0000000..8c9929c
--- /dev/null
+++ b/day207/problem_test.go
@@ -0,0 +1,58 @@
+package day207
+
+import "testing"
+
+var testcases = []struct {
+	g         UndirectedGraph
+	isPartite bool
+}{
+	{UndirectedGraph{
+		"A": {
+			"B": {},
+			"D": {},
+		},
+		"B": {
+			"A": {},
+			"C": {},
+		},
+		"C": {
+			"B": {},
+			"D": {},
+		},
+		"D": {
+			"A": {},
+			"C": {},
+		},
+	}, true},
+	{UndirectedGraph{
+		"A": {
+			"B": {},
+			"C": {},
+		},
+		"B": {
+			"A": {},
+			"C": {},
+		},
+		"C": {
+			"A": {},
+			"B": {},
+		},
+	}, false},
+}
+
+func TestIsBipartiteGraph(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if isPartite := IsBipartiteGraph(tc.g); isPartite != tc.isPartite {
+			t.Errorf("Expected %v, got %v", tc.isPartite, isPartite)
+		}
+	}
+}
+
+func BenchmarkIsBipartiteGraph(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IsBipartiteGraph(tc.g)
+		}
+	}
+}