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 a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.