找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: PattyZhou
收起左侧

[Google] 狗狗新鲜实习面经

[复制链接]

1206

主题

184

精华

3720

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3720
发表于 2-6-2017 09:49 PM | 显示全部楼层

ChrisK is correct - the question does not mean much. But given a max-heap data structure, where - the request timestamp stays at the max ( most recent request ) could be used to trim the structure anytime anyone wants to.
[ courses.cs.vt.edu/cs2604/spring02/Notes/C07.Heaps.pdf ]

1194

主题

195

精华

3819

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3819
发表于 2-6-2017 09:49 PM | 显示全部楼层

@NoOne: The thing with this problem is, that 99% of the requests will probably be super fast and they aim to cut off the long tail latency (just interpretation). Now with a heap I see two issues:
- How to remove an item from the heap, e.g. how to identify it since the heap is modified, if a response comes back, we have to find that item in the heap to remove it. How do you do this fast?
- O(Lg(N)) on insert and remove might not be such a big thing, since the insert can be optimized to O(1)

1174

主题

170

精华

3587

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3587
发表于 2-6-2017 09:49 PM | 显示全部楼层

@ChrisK - the question says - ignore request more than 1 sec old. That would mean - it is using this whatever as the queuing mechanism for incoming requests. In fact I am not so sure about the response at all. Hence the proposition of a heap to keep most current at the top level - and then one separate thread can peacefully trim the heap...

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表