吴波二面挂经

感恩节前的面试，面试官人很好，就是上来出了个不是蠡口和面筋的题然后我就有点懵。recordEvent(int timestamp);   getRecentEvent(int timestam

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

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

-25 01:18):
还想请问一下大家，是不是挂掉之后春招就不能投他家了呢

这题没必要用bst吧，我觉得哈，就直接用哥list，存下来，然后找中间的element
如果很大的话，多用几台机器，然后用 timestamp % n存timestamp下的数据，n是机器数，每台机器的数据可以一部分写在memory放不下的存到disk当中，然后每次去取数据的话，去每台机器上找，最后合并一下

1. def getRecentEvent(target)
   
2.   events = [3, 5, 7, 9, 13, 20]
   
3. 
   
4.   if target <= events[0]
   
5.     return events[0]
   
6.   elsif target >= events[-1]
   
7.     return events[-1]
   
8.   end
   
9. 
   
10.   left = 0
    
11.   right = events.size - 1
    
12. 
    
13.   while left <= right
    
14.     mid = left + (right - left) / 2
    
15. 
    
16.     if events[mid] == target
    
17.       return target
    
18.     elsif events[mid] < target
    
19.       if events[mid + 1] > target
    
20.         return events[mid]
    
21.       else
    
22.         left = mid + 1
    
23.       end
    
24.     else
    
25.       if events[mid - 1] < target
    
26.         return events[mid - 1]
    
27.       else
    
28.         right = mid - 1
    
29.       end
    
30.     end  
    
31.   end
    
32. end
    
33. 
    
34. p getRecentEvent 12 # 9

复制代码

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

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

这道题用tree啊，不算难吧
存在bst 有个variable一直update这最近的target

至于你说的followup真的不知道了
数据太大怎么办 存在disk里嘛难道 这算属于os类的问题吧

katiechen94 发表于 2018-11-25 02:55
这道题用tree啊，不算难吧
存在bst 有个variable一直update这最近的target

面试官的意思大概是过了一段时间就把前面太久远的删掉吧，大概用queue存吧， pop掉前面的

请问为什么getRecentEvent(12), 返回 9?

用二分做？

clezhong 发表于 2018-11-25 14:44
请问为什么getRecentEvent(12), 返回 9?

返回最近的一个时间

alice12 发表于 2018/11/25 03:06:40


面试官的意思大概是过了一段时间就把前面太久远的删掉吧，大概用queue存吧， pop掉前面的

这样啊 那还挺麻烦的感觉 那怎么确保取最近的呢如果用queue 难道还一个个pop出来哪个最大？

katiechen94 发表于 2018-11-26 03:16
这样啊 那还挺麻烦的感觉 那怎么确保取最近的呢如果用queue 难道还一个个pop出来哪个最大？

我是将queue中超时的pop掉，然后存到数组里用二分。不知道应该怎么样，这个方法也不怎么好

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

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