Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 333
Good morning! Here's your coding interview problem for today.

This problem was asked by Pinterest.

At a party, there is a single person who everyone knows, but who does not know anyone in return (the "celebrity"). To help figure out who this is, you have access to an `O(1)` method called `knows(a, b)`, which returns `True` if person `a` knows person `b`, else `False`.

Given a list of `N` people and the above operation, find a way to identify the celebrity in `O(N)` time.

Pull request description:
Day333
Resolves #668.

Patch:
diff --git a/README.md b/README.md
index 6117477..71df4e1 100644
--- a/README.md
+++ b/README.md
@@ -329,6 +329,7 @@ problems from
 * [Day 323](https://github.com/vaskoz/dailycodingproblem-go/issues/656)
 * [Day 324](https://github.com/vaskoz/dailycodingproblem-go/issues/658)
 * [Day 325](https://github.com/vaskoz/dailycodingproblem-go/issues/660)
+* [Day 333](https://github.com/vaskoz/dailycodingproblem-go/issues/668)
 * [Day 337](https://github.com/vaskoz/dailycodingproblem-go/issues/674)
 * [Day 338](https://github.com/vaskoz/dailycodingproblem-go/issues/675)
 * [Day 339](https://github.com/vaskoz/dailycodingproblem-go/issues/676)
diff --git a/day333/problem.go b/day333/problem.go
new file mode 100644
index 0000000..c323255
--- /dev/null
+++ b/day333/problem.go
@@ -0,0 +1,37 @@
+package day333
+
+// Knowing represents a personId knowing another personId.
+// Return true of first person knows the second person.
+// NOTE: This is not bidirectional.
+type Knowing map[int]map[int]bool
+
+func (k *Knowing) Knows(a, b int) bool {
+	if known, exists := (*k)[a]; exists {
+		return known[b]
+	}
+
+	return false
+}
+
+// FindCelebrity returns the ID of the celebrity.
+// Runs in O(N) time and O(1) space.
+func FindCelebrity(knows *Knowing, numPeople int) int {
+	a := 0
+	b := numPeople - 1
+
+	for a < b {
+		if knows.Knows(a, b) {
+			a++
+		} else {
+			b--
+		}
+	}
+
+	for i := 0; i < numPeople; i++ {
+		if i != a && (knows.Knows(a, i) || !knows.Knows(i, a)) {
+			return -1
+		}
+	}
+
+	return a
+}


Test patch:
diff --git a/day333/problem_test.go b/day333/problem_test.go
new file mode 100644
index 0000000..54bbf33
--- /dev/null
+++ b/day333/problem_test.go
@@ -0,0 +1,65 @@
+package day333
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	knows     *Knowing
+	numPeople int
+	celeb     int
+}{
+	{
+		&Knowing{
+			0: {
+				1: true,
+			},
+			2: {
+				1: true,
+			},
+			3: {
+				1: true,
+			},
+			4: {
+				1: true,
+			},
+		},
+		5,
+		1,
+	},
+	{
+		&Knowing{
+			0: {
+				1: true,
+			},
+			1: {
+				2: true,
+			},
+			2: {
+				3: true,
+			},
+			3: {
+				4: true,
+			},
+		},
+		5,
+		-1,
+	},
+}
+
+func TestFindCelebrity(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if celeb := FindCelebrity(tc.knows, tc.numPeople); celeb != tc.celeb {
+			t.Errorf("Expected %v, got %v", tc.celeb, celeb)
+		}
+	}
+}
+
+func BenchmarkFindCelebrity(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FindCelebrity(tc.knows, tc.numPeople)
+		}
+	}
+}