Problem Statement:
We have some clickstream data that we gathered on our client’s website. Using cookies, we collected snippets of users’ anonymized URL histories while they browsed the site. The histories are in chronological order, and no URL was visited more than once per person.
Write a function that takes two users’ browsing histories as input and returns the longest contiguous sequence of URLs that appears in both.
Sample Input:
user0 = ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"] user1 = ["/start", "/pink", "/register", "/orange", "/red", "a"] user2 = ["a", "/one", "/two"] user3 = ["/pink", "/orange", "/yellow", "/plum", "/blue", "/tan", "/red", "/amber", "/HotRodPink", "/CornflowerBlue", "/LightGoldenRodYellow", "/BritishRacingGreen"] user4 = ["/pink", "/orange", "/amber", "/BritishRacingGreen", "/plum", "/blue", "/tan", "/red", "/lavender", "/HotRodPink", "/CornflowerBlue", "/LightGoldenRodYellow"] user5 = ["a"] user6 = ["/pink","/orange","/six","/plum","/seven","/tan","/red", "/amber"]
Sample Output:
findContiguousHistory(user0, user1) => ["/pink", "/register", "/orange"] findContiguousHistory(user0, user2) => [] (empty) findContiguousHistory(user0, user0) => ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"] findContiguousHistory(user2, user1) => ["a"] findContiguousHistory(user5, user2) => ["a"] findContiguousHistory(user3, user4) => ["/plum", "/blue", "/tan", "/red"] findContiguousHistory(user4, user3) => ["/plum", "/blue", "/tan", "/red"] findContiguousHistory(user3, user6) => ["/tan", "/red", "/amber"]
This problem is similar to the usual pattern-matching coding challenge. If you understand the logic, it is easy to implement it with simple for-loop and conditional statements.
Here programming language is not a barrier. If you understand the logic, you can implement and solve this coding question in any programming language of your choice like C/C++, Java, Python, etc.
Here code is self-explanatory.
Prerequisite:
Python code:
# input data
user0 = ["/start", "/green", "/blue", "/pink", "/register", "/orange", "/one/two"]
user1 = ["/start", "/pink", "/register", "/orange", "/red", "a"]
user2 = ["a", "/one", "/two"]
user3 = ["/pink", "/orange", "/yellow", "/plum", "/blue", "/tan", "/red", "/amber", "/HotRodPink", "/CornflowerBlue", "/LightGoldenRodYellow", "/BritishRacingGreen"]
user4 = ["/pink", "/orange", "/amber", "/BritishRacingGreen", "/plum", "/blue", "/tan", "/red", "/lavender", "/HotRodPink", "/CornflowerBlue", "/LightGoldenRodYellow"]
user5 = ["a"]
user6 = ["/pink","/orange","/six","/plum","/seven","/tan","/red", "/amber"]
out = []
def findContiguousHistory(userA, userB, temp=[]):
if not userA or not userB:
if temp:
out.append(temp)
elif userA[0] == userB[0]:
temp.append(userA[0])
findContiguousHistory(userA[1:], userB[1:], temp)
else:
if temp:
out.append(temp)
findContiguousHistory(userA[1:], userB, [])
findContiguousHistory(userA, userB[1:], [])
findContiguousHistory(user0, user1)
result = []
# print longest matching sequence
for i in out:
if len(i) > len(result):
result = i
print(f"{result}")
Output:
['/pink', '/register', '/orange']
This output is only for the input user0 and user1. You can try providing different user data as input to the findContiguousHistory() function.
If the interviewer asked about this coding challenge, you can not use the inbuilt module to solve this. So practice writing code from the scratch.
All the best and keep practicing coding!
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on <b>CSEstack.org</b> portal.