Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 391
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

We have some historical clickstream data gathered from our site anonymously using cookies. The histories contain URLs that users have visited in chronological order.

Write a function that takes two users' browsing histories as input and returns the longest contiguous sequence of URLs that appear in both.

For example, given the following two users' histories:
```
user1 = ['/home', '/register', '/login', '/user', '/one', '/two']
user2 = ['/home', '/red', '/login', '/user', '/one', '/pink']
```
You should return the following:

`['/login', '/user', '/one']`

Pull request description:
Day391
Resolves #785.

Patch:
diff --git a/README.md b/README.md
index 4909e5f..7644b94 100644
--- a/README.md
+++ b/README.md
@@ -383,4 +383,5 @@ problems from
 * [Day 385](https://github.com/vaskoz/dailycodingproblem-go/issues/774)
 * [Day 386](https://github.com/vaskoz/dailycodingproblem-go/issues/778)
 * [Day 390](https://github.com/vaskoz/dailycodingproblem-go/issues/783)
+* [Day 391](https://github.com/vaskoz/dailycodingproblem-go/issues/785)
 
diff --git a/day391/problem.go b/day391/problem.go
new file mode 100644
index 0000000..63b891d
--- /dev/null
+++ b/day391/problem.go
@@ -0,0 +1,45 @@
+package day391
+
+// LongestContiguousBrowsingHistory returns the longest contiguous
+// common search history.
+// Runs in O(N*k) time where K is the length of the answer.
+func LongestContiguousBrowsingHistory(user1, user2 []string) []string {
+	first := make(map[string]struct{})
+	mutual := make(map[string]struct{})
+
+	for _, path := range user1 {
+		first[path] = struct{}{}
+	}
+
+	for _, path := range user2 {
+		if _, found := first[path]; found {
+			mutual[path] = struct{}{}
+		}
+	}
+
+	var longest []string
+
+	for i, path1 := range user1 {
+		if _, common := mutual[path1]; !common {
+			continue
+		}
+
+		for j, path2 := range user2 {
+			if path2 == path1 {
+				ptrI := i
+				ptrJ := j
+
+				for ptrI < len(user1) && ptrJ < len(user2) && user1[ptrI] == user2[ptrJ] {
+					ptrI++
+					ptrJ++
+				}
+
+				if ptrI-i > len(longest) {
+					longest = user1[i:ptrI]
+				}
+			}
+		}
+	}
+
+	return longest
+}


Test patch:
diff --git a/day391/problem_test.go b/day391/problem_test.go
new file mode 100644
index 0000000..26706c5
--- /dev/null
+++ b/day391/problem_test.go
@@ -0,0 +1,41 @@
+package day391
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	user1, user2 []string
+	expected     []string
+}{
+	{
+		[]string{"/home", "/register", "/login", "/user", "/one", "/two"},
+		[]string{"/home", "/red", "/login", "/user", "/one", "/pink"},
+		[]string{"/login", "/user", "/one"},
+	},
+	{
+		[]string{"/a", "/b", "/a", "/b", "/c", "/d"},
+		[]string{"/e", "/a", "/b", "/c", "/d", "/e"},
+		[]string{"/a", "/b", "/c", "/d"},
+	},
+}
+
+func TestLongestContiguousBrowsingHistory(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if res := LongestContiguousBrowsingHistory(tc.user1, tc.user2); !reflect.DeepEqual(res, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, res)
+		}
+	}
+}
+
+func BenchmarkLongestContiguousBrowsingHistory(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LongestContiguousBrowsingHistory(tc.user1, tc.user2)
+		}
+	}
+}