Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 287
Good morning! Here's your coding interview problem for today.

This problem was asked by Quora.

You are given a list of `(website, user)` pairs that represent users visiting websites. Come up with a program that identifies the top k pairs of websites with the greatest similarity.

For example, suppose `k = 1`, and the list of tuples is:
```
[('a', 1), ('a', 3), ('a', 5),
 ('b', 2), ('b', 6),
 ('c', 1), ('c', 2), ('c', 3), ('c', 4), ('c', 5)
 ('d', 4), ('d', 5), ('d', 6), ('d', 7),
 ('e', 1), ('e', 3), ('e': 5), ('e', 6)]
```
Then a reasonable similarity metric would most likely conclude that a and e are the most similar, so your program should return `[('a', 'e')]`.

Pull request:
Day287
Resolves #587.

Patch:
diff --git a/README.md b/README.md
index cf06cc0..1f6b4f7 100644
--- a/README.md
+++ b/README.md
@@ -296,3 +296,4 @@ problems from
 * [Day 284](https://github.com/vaskoz/dailycodingproblem-go/issues/578)
 * [Day 285](https://github.com/vaskoz/dailycodingproblem-go/issues/583)
 * [Day 286](https://github.com/vaskoz/dailycodingproblem-go/issues/585)
+* [Day 287](https://github.com/vaskoz/dailycodingproblem-go/issues/587)
diff --git a/day287/problem.go b/day287/problem.go
new file mode 100644
index 0000000..bca5350
--- /dev/null
+++ b/day287/problem.go
@@ -0,0 +1,95 @@
+package day287
+
+import "container/heap"
+
+// WebsiteVisitor represents a user visiting a website.
+type WebsiteVisitor struct {
+	Website string
+	UserID  int
+}
+
+// WebsitePair represents a tuple of websites.
+// Also contains a Similarity score based on Jaccard index.
+// High similarity score is better.
+type WebsitePair struct {
+	A, B       string
+	Similarity float64
+}
+
+type priorityQueue []WebsitePair
+
+func (pq priorityQueue) Len() int { return len(pq) }
+
+func (pq priorityQueue) Less(i, j int) bool {
+	return pq[i].Similarity < pq[j].Similarity
+}
+
+func (pq priorityQueue) Swap(i, j int) {
+	pq[i], pq[j] = pq[j], pq[i]
+}
+
+func (pq *priorityQueue) Push(x interface{}) {
+	pair := x.(WebsitePair)
+	*pq = append(*pq, pair)
+}
+
+func (pq *priorityQueue) Pop() interface{} {
+	old := *pq
+	n := len(old)
+	pair := old[n-1]
+	*pq = old[0 : n-1]
+	return pair
+}
+
+// TopKMostSimilarPairs returns k WebsitePairs.
+// Runs in O(N^2) because it compares all pairs for similarity.
+func TopKMostSimilarPairs(visits []WebsiteVisitor, k int) []WebsitePair {
+	if k < 1 || len(visits) < 2 {
+		return nil
+	}
+	sites := make(map[string][]int)
+	for _, site := range visits {
+		sites[site.Website] = append(sites[site.Website], site.UserID)
+	}
+	pq := make(priorityQueue, 0, k)
+	heap.Init(&pq)
+	for site1, ids1 := range sites {
+		for site2, ids2 := range sites {
+			if site1 >= site2 {
+				continue
+			}
+			score := similarityScore(ids1, ids2)
+			record := WebsitePair{site1, site2, score}
+			if pq.Len() < k {
+				heap.Push(&pq, record)
+			} else {
+				lowest := heap.Pop(&pq).(WebsitePair)
+				if lowest.Similarity < record.Similarity {
+					heap.Push(&pq, record)
+				} else {
+					heap.Push(&pq, lowest)
+				}
+			}
+		}
+	}
+	topK := make([]WebsitePair, k)
+	for i := range topK {
+		topK[i] = heap.Pop(&pq).(WebsitePair)
+	}
+	return topK
+}
+
+func similarityScore(ids1, ids2 []int) float64 {
+	seen := make(map[int]struct{}, len(ids1))
+	for _, id := range ids1 {
+		seen[id] = struct{}{}
+	}
+	var intersectionCount float64
+	for _, id := range ids2 {
+		if _, found := seen[id]; found {
+			intersectionCount++
+		}
+	}
+	unionCount := float64(len(ids1)+len(ids2)) - intersectionCount
+	return intersectionCount / unionCount
+}


Test patch:
diff --git a/day287/problem_test.go b/day287/problem_test.go
new file mode 100644
index 0000000..53af0fc
--- /dev/null
+++ b/day287/problem_test.go
@@ -0,0 +1,60 @@
+package day287
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	visits   []WebsiteVisitor
+	k        int
+	expected []WebsitePair
+}{
+	{[]WebsiteVisitor{
+		{"a", 1}, {"a", 3}, {"a", 5},
+		{"b", 2}, {"b", 6},
+		{"c", 1}, {"c", 2}, {"c", 3}, {"c", 4}, {"c", 5},
+		{"d", 4}, {"d", 5}, {"d", 6}, {"d", 7},
+		{"e", 1}, {"e", 3}, {"e", 5}, {"e", 6},
+	},
+		1,
+		[]WebsitePair{
+			{"a", "e", 0.75},
+		},
+	},
+	{
+		[]WebsiteVisitor{{"a", 1}},
+		1,
+		nil,
+	},
+	{[]WebsiteVisitor{
+		{"a", 1}, {"a", 3}, {"a", 5},
+		{"b", 2}, {"b", 6},
+		{"c", 1}, {"c", 2}, {"c", 3}, {"c", 4}, {"c", 5},
+		{"d", 4}, {"d", 5}, {"d", 6}, {"d", 7},
+		{"e", 1}, {"e", 3}, {"e", 5}, {"e", 6},
+	},
+		3,
+		[]WebsitePair{
+			{"c", "e", 0.5}, {"a", "c", 0.6}, {"a", "e", 0.75},
+		},
+	},
+}
+
+func TestTopKMostSimilarPairs(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := TopKMostSimilarPairs(tc.visits, tc.k); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkTopKMostSimilarPairs(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			TopKMostSimilarPairs(tc.visits, tc.k)
+		}
+	}
+}