Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 297
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

At a popular bar, each customer has a set of favorite drinks, and will happily accept any drink among this set. For example, in the following situation, customer `0` will be satisfied with drinks `0, 1, 3, or 6`.
```
preferences = {
    0: [0, 1, 3, 6],
    1: [1, 4, 7],
    2: [2, 4, 7, 5],
    3: [3, 2, 5],
    4: [5, 8]
}
```
A lazy bartender working at this bar is trying to reduce his effort by limiting the drink recipes he must memorize. Given a dictionary input such as the one above, return the fewest number of drinks he must learn in order to satisfy all customers.

For the input above, the answer would be `2`, as drinks `1` and `5` will satisfy everyone.

Pull request description:
Day297
Resolves #607.

Patch:
diff --git a/README.md b/README.md
index 2534731..bb4b972 100644
--- a/README.md
+++ b/README.md
@@ -304,3 +304,4 @@ problems from
 * [Day 294](https://github.com/vaskoz/dailycodingproblem-go/issues/600)
 * [Day 295](https://github.com/vaskoz/dailycodingproblem-go/issues/601)
 * [Day 296](https://github.com/vaskoz/dailycodingproblem-go/issues/605)
+* [Day 297](https://github.com/vaskoz/dailycodingproblem-go/issues/607)
diff --git a/day297/problem.go b/day297/problem.go
new file mode 100644
index 0000000..3058543
--- /dev/null
+++ b/day297/problem.go
@@ -0,0 +1,50 @@
+package day297
+
+import "sort"
+
+// Customer is the customer's id.
+type Customer int
+
+// Drink is the drink's id.
+type Drink int
+
+// LazyBartender returns the fewest number of drinks
+// to satisfy all customers.
+func LazyBartender(prefs map[Customer][]Drink) []Drink {
+	var drinks []Drink
+	inverted := make(map[Drink][]Customer)
+	for cust, favorites := range prefs {
+		for _, drink := range favorites {
+			inverted[drink] = append(inverted[drink], cust)
+		}
+	}
+	totalCustomers := len(prefs)
+	served := make(map[Customer]struct{}, totalCustomers)
+	for len(served) < totalCustomers {
+		var largest []Customer
+		var largestDrink Drink
+		var largestIncrease int
+		for drink, custs := range inverted {
+			var newlyServed int
+			for _, cust := range custs {
+				if _, found := served[cust]; !found {
+					newlyServed++
+				}
+			}
+			if newlyServed > largestIncrease {
+				largestIncrease = newlyServed
+				largestDrink = drink
+				largest = custs
+			}
+		}
+		delete(inverted, largestDrink)
+		drinks = append(drinks, largestDrink)
+		for _, cust := range largest {
+			served[cust] = struct{}{}
+		}
+	}
+	sort.Slice(drinks, func(i, j int) bool {
+		return drinks[i] < drinks[j]
+	})
+	return drinks
+}


Test patch:
diff --git a/day297/problem_test.go b/day297/problem_test.go
new file mode 100644
index 0000000..7414810
--- /dev/null
+++ b/day297/problem_test.go
@@ -0,0 +1,40 @@
+package day297
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	prefs           map[Customer][]Drink
+	memorizedDrinks []Drink
+}{
+	{
+		map[Customer][]Drink{
+			0: {0, 1, 3, 6},
+			1: {1, 4, 7},
+			2: {2, 4, 7, 5},
+			3: {3, 2, 5},
+			4: {5, 8},
+		},
+		[]Drink{1, 5},
+	},
+}
+
+func TestLazyBartender(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := LazyBartender(tc.prefs); !reflect.DeepEqual(result, tc.memorizedDrinks) {
+			t.Errorf("Expected %v, got %v", tc.memorizedDrinks, result)
+		}
+	}
+}
+
+func BenchmarkLazyBartender(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LazyBartender(tc.prefs)
+		}
+	}
+}