Roblox karat 電面分享 附上代碼討論

第一題是地裏常見的 domain , freq 問題
第二題是 每個使用者有 網頁訪問紀錄。求任兩使用者、最大連續共同瀏覽紀錄

說起來好繞口
直接舉例：
user0 = ["/start.html", "/green.html", "/blue.html", "/pink.php", "/register.asp&q

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

position 是否為 上一次的position+1.
- 如果不是的話、代表非連續。

下面是我的參考代碼， 空間複雜度O(N), 時間複雜度 O(N) 希望有更佳解

需要大米....給大米不會扣您分數!

1. 
   
2. user0 = ["/start.html", "/green.html", "/blue.html", "/pink.php", "/register.asp", "/orange.html"]
   
3. user1 = ["/start.html", "b.php", "/pink.php", "/register.asp", "/orange.html", "/red.html"]
   
4. 
   
5. user2 = ["/red.html", "/green.html", "/blue.html", "/pink.php", "/register.asp"]
   
6. user3 = ["/blue.html", "/logout.php"]
   
7. 
   
8. 
   
9. def findContiguousHistory(u1, u2):
   
10. u1_map = dict()
    
11. u2_map = dict()
    
12. 
    
13. # Build map: key(url_path), value(position)
    
14. for i, val in enumerate(u1):
    
15. u1_map[val] = i
    
16. for i, val in enumerate(u2):
    
17. u2_map[val] = i
    
18. 
    
19. longest_consecutive_common_records = []
    
20. curr_records = []
    
21. 
    
22. for i, curr_item in enumerate(u1):
    
23. curr_item = u1[i]
    
24. if len(curr_records) > len(longest_consecutive_common_records):
    
25. longest_consecutive_common_records = curr_records[:]
    
26. 
    
27. if curr_item in u2_map:
    
28. if len(curr_records) == 0:
    
29. curr_records.append(curr_item)
    
30. elif curr_records and u2_ptr + 1 == u2_map[curr_item]:
    
31. curr_records.append(curr_item)
    
32. else:
    
33. curr_records = [curr_item]
    
34. u2_ptr = u2_map[curr_item]
    
35. continue
    
36. # reset
    
37. curr_records = []
    
38. u2_ptr = -1
    
39. return longest_consecutive_common_records
    
40. 
    
41. 
    
42. print(findContiguousHistory(user0, user1))
    
43. # ['/pink.php', '/register.asp', '/orange.html']
    
44. print(findContiguousHistory(user0, user0))
    

复制代码

上周周五我面的也是这道题，看来他们真的题库有限。

这题感觉标准应该是dp O(mn), hashmap要保证浏览记录里没有重复页面吧, LZ有确认这点么？
已加米~

Does LouZhu have onsite and have the offer??

剛跟Roblox電面聊完,來這學習準備Karat的OA,感謝分享