Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 279
Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

A classroom consists of N students, whose friendships can be represented in an adjacency list. For example, the following descibes a situation where 0 is friends with 1 and 2, 3 is friends with 6, and so on.
```
{0: [1, 2],
 1: [0, 5],
 2: [0],
 3: [6],
 4: [],
 5: [1],
 6: [3]} 
```
Each student can be placed in a friend group, which can be defined as the transitive closure of that student's friendship relations. In other words, this is the smallest set such that no student in the group has any friends outside this group. For the example above, the friend groups would be `{0, 1, 2, 5}, {3, 6}, {4}`.

Given a friendship list such as the one above, determine the number of friend groups in the class.

Pull request:
Day279
Resolves #566.

Patch:
diff --git a/README.md b/README.md
index 5df437d..fa1c197 100644
--- a/README.md
+++ b/README.md
@@ -282,3 +282,4 @@ problems from
 * [Day 272](https://github.com/vaskoz/dailycodingproblem-go/issues/555)
 * [Day 273](https://github.com/vaskoz/dailycodingproblem-go/issues/556)
 * [Day 277](https://github.com/vaskoz/dailycodingproblem-go/issues/563)
+* [Day 279](https://github.com/vaskoz/dailycodingproblem-go/issues/566)
diff --git a/day279/problem.go b/day279/problem.go
new file mode 100644
index 0000000..200d023
--- /dev/null
+++ b/day279/problem.go
@@ -0,0 +1,31 @@
+package day279
+
+// FriendGraph is an adjacency list of friendships using
+// integer IDs for friends.
+type FriendGraph map[int]map[int]struct{}
+
+// NumberOfFriendGroups returns the number of disconnected
+// friend groups.
+// Runs DFS for each separate group and counts the number of
+// times DFS had to be run.
+// Runs in O(V+E) time and O(V) space just like DFS.
+func NumberOfFriendGroups(friends FriendGraph) int {
+	visits := make([]bool, len(friends))
+	friendGroups := 0
+	for id, visited := range visits {
+		if !visited {
+			dfs(friends, id, visits)
+			friendGroups++
+		}
+	}
+	return friendGroups
+}
+
+func dfs(g FriendGraph, start int, visits []bool) {
+	for friendID := range g[start] {
+		if visited := visits[friendID]; !visited {
+			visits[friendID] = true
+			dfs(g, friendID, visits)
+		}
+	}
+}


Test patch:
diff --git a/day279/problem_test.go b/day279/problem_test.go
new file mode 100644
index 0000000..6484358
--- /dev/null
+++ b/day279/problem_test.go
@@ -0,0 +1,39 @@
+package day279
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	friends        FriendGraph
+	distinctGroups int
+}{
+	{
+		FriendGraph{
+			0: {1: struct{}{}, 2: struct{}{}},
+			1: {0: struct{}{}, 5: struct{}{}},
+			2: {0: struct{}{}},
+			3: {6: struct{}{}},
+			4: {},
+			5: {1: struct{}{}},
+			6: {3: struct{}{}},
+		},
+		3,
+	},
+}
+
+func TestNumberOfFriendGroups(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := NumberOfFriendGroups(tc.friends); result != tc.distinctGroups {
+			t.Errorf("Expected %v, got %v", tc.distinctGroups, result)
+		}
+	}
+}
+
+func BenchmarkNumberOfFriendGroups(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			NumberOfFriendGroups(tc.friends)
+		}
+	}
+}