[转让]/[交换]5 off similac 胖子# PennySaver - 省钱一族
i*6
1 楼
你是让她长大找一个天天在你家打咯放屁，饭桌上剔牙时时显示自己真实本色，但是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
摸着自己的胸口 说， 说假话的遭雷劈.
摸着自己的胸口 说， 说假话的遭雷劈.
c*a
2 楼
室友早上G店面被问了这个
http://www.careercup.com/question?id=6005446611566592
我下午F被问了同个问题
http://www.careercup.com/question?id=14974850
我俩吵到现在还谁都没说服谁。。。
http://www.careercup.com/question?id=6005446611566592
我下午F被问了同个问题
http://www.careercup.com/question?id=14974850
我俩吵到现在还谁都没说服谁。。。
a*u
3 楼
不建议交易打印胖子；胖子是免费的，收费的是服务:
出售/交换物品的名称:
5 off similac 胖子
物品类别（coupon：mfc等；血糖仪等）:
coupon
物品来源（报纸夹页，厂家邮寄等）:
厂家邮寄
可接受的价格（必须明码标价，必填）:
$2 each
邮寄损失方式哪方承担（若需邮寄，必填）:
buyer
付款方式说明:
paypal
本贴有效期（必填）:
卖完为止
联系方式（例： 站内）:
站内
出售/交换物品的名称:
5 off similac 胖子
物品类别（coupon：mfc等；血糖仪等）:
coupon
物品来源（报纸夹页，厂家邮寄等）:
厂家邮寄
可接受的价格（必须明码标价，必填）:
$2 each
邮寄损失方式哪方承担（若需邮寄，必填）:
buyer
付款方式说明:
paypal
本贴有效期（必填）:
卖完为止
联系方式（例： 站内）:
站内
d*0
4 楼
打倒包办婚姻的想法！！！你这是落后愚昧阻碍下一代的典型家长制问题！！
和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 你是让她长大找一个天天在你家打咯放屁，饭桌上剔牙时时显示自己真实本色，但是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
: 摸着自己的胸口 说， 说假话的遭雷劈.
和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 你是让她长大找一个天天在你家打咯放屁，饭桌上剔牙时时显示自己真实本色，但是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
: 摸着自己的胸口 说， 说假话的遭雷劈.
h*n
5 楼
Interval tree
L*h
6 楼
Coupon or Check?
If it is Check, the price is so good :)
If it is Coupon, the price is so bad :(
【在 a********u 的大作中提到】
: 不建议交易打印胖子；胖子是免费的，收费的是服务:
: 出售/交换物品的名称:
: 5 off similac 胖子
: 物品类别（coupon：mfc等；血糖仪等）:
: coupon
: 物品来源（报纸夹页，厂家邮寄等）:
: 厂家邮寄
: 可接受的价格（必须明码标价，必填）:
: $2 each
: 邮寄损失方式哪方承担（若需邮寄，必填）:
If it is Check, the price is so good :)
If it is Coupon, the price is so bad :(
【在 a********u 的大作中提到】
: 不建议交易打印胖子；胖子是免费的，收费的是服务:
: 出售/交换物品的名称:
: 5 off similac 胖子
: 物品类别（coupon：mfc等；血糖仪等）:
: coupon
: 物品来源（报纸夹页，厂家邮寄等）:
: 厂家邮寄
: 可接受的价格（必须明码标价，必填）:
: $2 each
: 邮寄损失方式哪方承担（若需邮寄，必填）:
A*k
7 楼
同种也就罢了，同文可不见得，如果孩子生在美国长在美国，你觉得她更认同哪种文化？
天天打嗝放屁剔牙的女婿，不论国男白男黑男都不要。
天天打嗝放屁剔牙的女婿，不论国男白男黑男都不要。
p*2
8 楼
这个用个循环数组可以吗
i*6
9 楼
我问一句，你想让你孩子上哈佛还是耶鲁，没有错吧？
【在 d******0 的大作中提到】
: 打倒包办婚姻的想法！！！你这是落后愚昧阻碍下一代的典型家长制问题！！
:
:
: 和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 d******0 的大作中提到】
: 打倒包办婚姻的想法！！！你这是落后愚昧阻碍下一代的典型家长制问题！！
:
:
: 和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
x*w
10 楼
order statistic tree
每个node按时间顺序排序，每个node保存子树个数和代表event的时间戳，一个node获
取需要lgn的复杂度。每当一个event arrive, 很快可以知道时间范围。
问题是怎么有效的清除过期节点并保持statistic tree的平衡
每个node按时间顺序排序，每个node保存子树个数和代表event的时间戳，一个node获
取需要lgn的复杂度。每当一个event arrive, 很快可以知道时间范围。
问题是怎么有效的清除过期节点并保持statistic tree的平衡
p*s
11 楼
不能找个有修养的中国人吗？还是非常多的。
我看到人饭后剔牙就恶心，即使装腔作势用手挡着，你要是牙缝大容易卡东西，去洗手
间漱下口有多麻烦？当人面剔牙？简直跟当众小便没多大区别。
我看到人饭后剔牙就恶心，即使装腔作势用手挡着，你要是牙缝大容易卡东西，去洗手
间漱下口有多麻烦？当人面剔牙？简直跟当众小便没多大区别。
h*a
12 楼
基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
，任何超过常数时间的算法都是不可行的。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
，任何超过常数时间的算法都是不可行的。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
i*6
13 楼
Agree
【在 p*******s 的大作中提到】
: 不能找个有修养的中国人吗？还是非常多的。
: 我看到人饭后剔牙就恶心，即使装腔作势用手挡着，你要是牙缝大容易卡东西，去洗手
: 间漱下口有多麻烦？当人面剔牙？简直跟当众小便没多大区别。
【在 p*******s 的大作中提到】
: 不能找个有修养的中国人吗？还是非常多的。
: 我看到人饭后剔牙就恶心，即使装腔作势用手挡着，你要是牙缝大容易卡东西，去洗手
: 间漱下口有多麻烦？当人面剔牙？简直跟当众小便没多大区别。
p*2
14 楼
多谢大牛confirm，循环数组O(1)就可以了。
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
g*r
15 楼
麻烦你告知一下你爹娘当时怎么想的，说假话的遭雷劈
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: Agree
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: Agree
r*h
16 楼
请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
top5呢？
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
top5呢？
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
d*0
17 楼
没这想法。
【在 i**********6 的大作中提到】
: 我问一句，你想让你孩子上哈佛还是耶鲁，没有错吧？
【在 i**********6 的大作中提到】
: 我问一句，你想让你孩子上哈佛还是耶鲁，没有错吧？
r*h
18 楼
二爷能展开说说吗？如何做到O(1)找到当前top5呢
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
i*6
19 楼
我爹娘梦想着我娶一白妞.
【在 g***r 的大作中提到】
: 麻烦你告知一下你爹娘当时怎么想的，说假话的遭雷劈
:
: 是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 g***r 的大作中提到】
: 麻烦你告知一下你爹娘当时怎么想的，说假话的遭雷劈
:
: 是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
h*a
20 楼
ft，你有什么更好的idea可以分享一下啊，这道是高频题
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
w*9
21 楼
改一下你的问题。
问题：你是想让她长大找和自己同文同种的中产阶级Chinese，还是一个中产阶级白人
男?
摸着自己的胸口说，这个问题不公平吗？
问题：你是想让她长大找和自己同文同种的中产阶级Chinese，还是一个中产阶级白人
男?
摸着自己的胸口说，这个问题不公平吗？
p*2
22 楼
有说找top5吗？
【在 r**h 的大作中提到】
: 二爷能展开说说吗？如何做到O(1)找到当前top5呢
d*0
23 楼
我爹娘从高中后，就对偶没啥梦想。
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
h*a
24 楼
这道题问的是request的count，不需要保存数据啊。没有什么top 5啊.
【在 r**h 的大作中提到】
: 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
: 那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
: 是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
: top5呢？
【在 r**h 的大作中提到】
: 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
: 那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
: 是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
: top5呢？
d*0
25 楼
剔牙伤牙龈啊。要用牙线，厕所不光是给瘾君子cook用的。
【在 p*******s 的大作中提到】
: 不能找个有修养的中国人吗？还是非常多的。
: 我看到人饭后剔牙就恶心，即使装腔作势用手挡着，你要是牙缝大容易卡东西，去洗手
: 间漱下口有多麻烦？当人面剔牙？简直跟当众小便没多大区别。
【在 p*******s 的大作中提到】
: 不能找个有修养的中国人吗？还是非常多的。
: 我看到人饭后剔牙就恶心，即使装腔作势用手挡着，你要是牙缝大容易卡东西，去洗手
: 间漱下口有多麻烦？当人面剔牙？简直跟当众小便没多大区别。
r*h
26 楼
哦，我和那一题找5分钟、1小时、24小时内的query搞混了。。不好意思啊
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
d*0
27 楼
为啥只能找中产阶级打工仔啊？
【在 w********9 的大作中提到】
: 改一下你的问题。
: 问题：你是想让她长大找和自己同文同种的中产阶级Chinese，还是一个中产阶级白人
: 男?
: 摸着自己的胸口说，这个问题不公平吗？
【在 w********9 的大作中提到】
: 改一下你的问题。
: 问题：你是想让她长大找和自己同文同种的中产阶级Chinese，还是一个中产阶级白人
: 男?
: 摸着自己的胸口说，这个问题不公平吗？
h*a
28 楼
用循环数组也有tricky的地方，你写写 code试试。
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
w*9
29 楼
那倒是。不过，结婚的时候，比较普遍的还是中产吧？更确切地说，是中等收入。
【在 d******0 的大作中提到】
: 为啥只能找中产阶级打工仔啊？
p*2
30 楼
是。我能想到一些cases。一段时间没有request的话，需要把中间的都清零。
【在 h*****a 的大作中提到】
: 用循环数组也有tricky的地方，你写写 code试试。
n*7
31 楼
打嗝放屁自己控制不了，没必要鄙视吧
p*2
32 楼
我觉得高频题太多了，搞不过来呀。
【在 h*****a 的大作中提到】
: ft，你有什么更好的idea可以分享一下啊，这道是高频题
a*u
33 楼
傻逼。这个“同文同种的 Chinese PHD”品德高尚，挣钱大大地多；而这个“中产阶级
出来 的白人男”满身狐臭，还要玩3p,大骂你老母干涉他隐私，很多很多。
所以说你提这么一个前提来判断，本身就是个二。
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
出来 的白人男”满身狐臭，还要玩3p,大骂你老母干涉他隐私，很多很多。
所以说你提这么一个前提来判断，本身就是个二。
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
c*a
34 楼
感动得暴出了泪花。当时狗急跳墙用的就是一个数组去循环，没想到给我蒙对了！！！
不过wrap around很难写bug free，我时间到了连brutal force都没写完，唉。。。。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
不过wrap around很难写bug free，我时间到了连brutal force都没写完，唉。。。。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
m*n
35 楼
如果“同文同种”的chinese PHD就表示在饭桌上剔牙，天天在丈母娘家里打嗝放屁，
那么说明这个女儿也是喜欢在饭桌上剔牙，在公婆家打嗝放屁的，不然怎么叫同文同种？
如果你女儿也这个鸟样，传说中的有教养中产阶级白人男肯定内牛满面阿
你们都没学过逻辑推理怎么地？我真是看不下去了
那么说明这个女儿也是喜欢在饭桌上剔牙，在公婆家打嗝放屁的，不然怎么叫同文同种？
如果你女儿也这个鸟样，传说中的有教养中产阶级白人男肯定内牛满面阿
你们都没学过逻辑推理怎么地？我真是看不下去了
c*a
36 楼
频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
然后就是2011年一次。
恰好跟室友撞了而已。
【在 p*****2 的大作中提到】
:
: 我觉得高频题太多了，搞不过来呀。
然后就是2011年一次。
恰好跟室友撞了而已。
【在 p*****2 的大作中提到】
:
: 我觉得高频题太多了，搞不过来呀。
y*n
37 楼
不能找大陆的农村猥琐男。
要看家里出身。
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
要看家里出身。
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
p*2
38 楼
你室友怎么做的？这题在板上以前确实看到过几次。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
w*j
39 楼
为啥不能找一个和自己同文同种的中产阶级出来的中国人？
你这个问题就好像，你要吃一个狗屎味道的面包，还是吃一坨面包味道的狗屎一样。你
难道就不能找个
面包味道的面包吃？
是和自己同文同
种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
你这个问题就好像，你要吃一个狗屎味道的面包，还是吃一坨面包味道的狗屎一样。你
难道就不能找个
面包味道的面包吃？
是和自己同文同
种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
h*a
40 楼
这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
系统，都有类似的需求。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
系统，都有类似的需求。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
h*1
41 楼
你在哪里找到这么极品的男人？听到就恶心。。。
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
z*8
42 楼
二爷能具体讲讲吗？
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
w*j
43 楼
嗯，还可以问是找一个饭桌上放屁剔牙的chinese phd，还是找一个高尚，文雅，但是
有std的中产白
男？
【在 a**********u 的大作中提到】
: 傻逼。这个“同文同种的 Chinese PHD”品德高尚，挣钱大大地多；而这个“中产阶级
: 出来 的白人男”满身狐臭，还要玩3p,大骂你老母干涉他隐私，很多很多。
: 所以说你提这么一个前提来判断，本身就是个二。
:
: 是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
有std的中产白
男？
【在 a**********u 的大作中提到】
: 傻逼。这个“同文同种的 Chinese PHD”品德高尚，挣钱大大地多；而这个“中产阶级
: 出来 的白人男”满身狐臭，还要玩3p,大骂你老母干涉他隐私，很多很多。
: 所以说你提这么一个前提来判断，本身就是个二。
:
: 是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
p*2
44 楼
瞎写了一个。
final int SIZE=60*60; //seconds in one hour
int[] arr=new int[SIZE];
int hour=0;
int minute=0;
long last=0;
long currSecond(){
return System.currentTimeMillis()/1000;
}
long clear(){
long curr=currSecond();
if(curr>last){
if(curr-last>=SIZE){
hour=0;
minute=0;
Arrays.fill(arr,0);
}
else{
if(curr-last>=60){
minute=0;
}
else{
for(long i=last-60+1;i<=curr-60;i++){
minute-=arr[(int)(i%SIZE)];
}
}
for(long i=last+1;i<=curr;i++){
int p=(int)(i%SIZE);
hour-=arr[p];
arr[p]=0;
}
}
last=curr;
}
return curr;
}
void request(){
long curr=clear();
arr[(int)(curr%SIZE)]++;
hour++;
minute++;
}
int lastSecond(){
long curr=clear();
return arr[(int)(curr%SIZE)];
}
int lastMinute(){
clear();
return minute;
}
int lastHour(){
clear();
return hour;
}
【在 z*********8 的大作中提到】
: 二爷能具体讲讲吗？
Q*7
45 楼
只要是人就会打屁打嗝。只要不在公众场合做不文雅的事就行。
r*e
46 楼
膜拜
【在 p*****2 的大作中提到】
:
: 瞎写了一个。
: final int SIZE=60*60; //seconds in one hour
: int[] arr=new int[SIZE];
: int hour=0;
: int minute=0;
: long last=0;
:
: long currSecond(){
: return System.currentTimeMillis()/1000;
【在 p*****2 的大作中提到】
:
: 瞎写了一个。
: final int SIZE=60*60; //seconds in one hour
: int[] arr=new int[SIZE];
: int hour=0;
: int minute=0;
: long last=0;
:
: long currSecond(){
: return System.currentTimeMillis()/1000;
w*p
47 楼
不好意思，chinese phd ，如我老公，也一样会打咯放屁，饭桌上剔牙。顶多有外人在
的时候，稍微掩饰一下。
所以，俺们不要求未来女婿在我们面前装的多绅士
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
的时候，稍微掩饰一下。
所以，俺们不要求未来女婿在我们面前装的多绅士
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
a*r
48 楼
Only need 2 60 element array. Just record request count for last 60 seconds
and counts for last 60 mins. Update them accordingly based on the count for
each new seconds.
and counts for last 60 mins. Update them accordingly based on the count for
each new seconds.
F*P
49 楼
你这是假设中国phd都打咯放屁，饭桌上剔牙，美国白人都没有任何诸如此类的毛病。
这假设成立么？如果属实，那另说。
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
这假设成立么？如果属实，那另说。
是和自己同文同种的 Chinese PHD，还是一个这里中产阶级出来 的白人男?
【在 i**********6 的大作中提到】
: 我爹娘梦想着我娶一白妞.
r*e
50 楼
你这个得不到严格意义上的last hour count
因为minite array里的数据都是对齐在整minite边界上的
而查询的时候不一定是在整minite上
当然对于近似的查询没问题
seconds
for
【在 a*******r 的大作中提到】
: Only need 2 60 element array. Just record request count for last 60 seconds
: and counts for last 60 mins. Update them accordingly based on the count for
: each new seconds.
因为minite array里的数据都是对齐在整minite边界上的
而查询的时候不一定是在整minite上
当然对于近似的查询没问题
seconds
for
【在 a*******r 的大作中提到】
: Only need 2 60 element array. Just record request count for last 60 seconds
: and counts for last 60 mins. Update them accordingly based on the count for
: each new seconds.
c*a
51 楼
丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
【在 p*****2 的大作中提到】
:
: 瞎写了一个。
: final int SIZE=60*60; //seconds in one hour
: int[] arr=new int[SIZE];
: int hour=0;
: int minute=0;
: long last=0;
:
: long currSecond(){
: return System.currentTimeMillis()/1000;
【在 p*****2 的大作中提到】
:
: 瞎写了一个。
: final int SIZE=60*60; //seconds in one hour
: int[] arr=new int[SIZE];
: int hour=0;
: int minute=0;
: long last=0;
:
: long currSecond(){
: return System.currentTimeMillis()/1000;
r*e
52 楼
circular buckets是正道，B+是走入歧途了
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
p*2
53 楼
感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
吧？我感觉面试没有必要上来就想搞最优解。
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
h*a
54 楼
一个扩展问题是要thread safe.
【在 p*****2 的大作中提到】
:
: 感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
: solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
: 吧？我感觉面试没有必要上来就想搞最优解。
【在 p*****2 的大作中提到】
:
: 感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
: solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
: 吧？我感觉面试没有必要上来就想搞最优解。
p*2
55 楼
如果只是要求thread safe的话，加上synchronized keyword就可以了。
【在 h*****a 的大作中提到】
: 一个扩展问题是要thread safe.
g*e
56 楼
这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
时候可以做sampling然后predict
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
时候可以做sampling然后predict
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
h*a
57 楼
如果request 非常频繁的话，明显效率不高啊
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
g*e
58 楼
赞，这才是这个题真正的目的
metrics
【在 h*****a 的大作中提到】
: 这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
: 系统，都有类似的需求。
metrics
【在 h*****a 的大作中提到】
: 这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
: 系统，都有类似的需求。
h*a
59 楼
难道这不是metrics/monitoring系统必须解决的实际问题么？
【在 g**e 的大作中提到】
: 这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
: 时候可以做sampling然后predict
【在 g**e 的大作中提到】
: 这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
: 时候可以做sampling然后predict
g*e
60 楼
是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
大的
【在 h*****a 的大作中提到】
: 难道这不是metrics/monitoring系统必须解决的实际问题么？
大的
【在 h*****a 的大作中提到】
: 难道这不是metrics/monitoring系统必须解决的实际问题么？
h*a
61 楼
你说的有道理。绝对精确确实不需要，但基本精确还是要保证的，尤其是用于
monitoring的时候。
【在 g**e 的大作中提到】
: 是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
:
: 大的
monitoring的时候。
【在 g**e 的大作中提到】
: 是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
:
: 大的
p*2
62 楼
所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
【在 h*****a 的大作中提到】
: 如果request 非常频繁的话，明显效率不高啊
h*a
63 楼
hehe, 如果问你这道题的interviewer让你实现thread safe，你说你是应该主动问他是
不是我应该考虑高并发，然后给他一个支持高并发的solution，还是应该直接用
synchronized呢？虽然问题比较模糊，但事实上我觉得既然这是一个比较实际的问题，
而且用circular array的一个前提就是request比较频繁（否则完全可以用double
linked list），那高并发是理所应当的啊。
【在 p*****2 的大作中提到】
:
: 所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
不是我应该考虑高并发，然后给他一个支持高并发的solution，还是应该直接用
synchronized呢？虽然问题比较模糊，但事实上我觉得既然这是一个比较实际的问题，
而且用circular array的一个前提就是request比较频繁（否则完全可以用double
linked list），那高并发是理所应当的啊。
【在 p*****2 的大作中提到】
:
: 所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
p*2
64 楼
对。所以我会跟面试官说如果只是考虑thread safe的话我可以用synchronized. 这个
时候面试官应该就会提示也需要考虑高并发了吧？
按照java的library看，thread safe和concurrent貌似是分开的，并没有混在一起。
double linked list我也没考虑过。实现起来比array容易吗？
具体来说高并发，可不可以这样。
如果curr==last的话，就可以直接返回结果，但是结果不是精确的，可能是近似的
如果curr!=last, 就wait
另外一个线程专门处理request, 如果curr>last, 最后last=curr以后notifiyAll
这个行吗？
【在 h*****a 的大作中提到】
: hehe, 如果问你这道题的interviewer让你实现thread safe，你说你是应该主动问他是
: 不是我应该考虑高并发，然后给他一个支持高并发的solution，还是应该直接用
: synchronized呢？虽然问题比较模糊，但事实上我觉得既然这是一个比较实际的问题，
: 而且用circular array的一个前提就是request比较频繁（否则完全可以用double
: linked list），那高并发是理所应当的啊。
h*a
65 楼
用array的实现来了一个新的request，有可能要去最多check数组里所有的3600个元素
，如果request非常少的话，这个额外开销是不小的。
用double linked list 保存每一个request的timestamp，在list size 确定不会太大
的情况下是可行的。实现也并不复杂。
concurrency我的想法是对每一个array的cell加锁，而不是对整个数组或者object加锁
，不过还没具体写过。
【在 p*****2 的大作中提到】
:
: 对。所以我会跟面试官说如果只是考虑thread safe的话我可以用synchronized. 这个
: 时候面试官应该就会提示也需要考虑高并发了吧？
: 按照java的library看，thread safe和concurrent貌似是分开的，并没有混在一起。
: double linked list我也没考虑过。实现起来比array容易吗？
: 具体来说高并发，可不可以这样。
: 如果curr==last的话，就可以直接返回结果，但是结果不是精确的，可能是近似的
: 如果curr!=last, 就wait
: 另外一个线程专门处理request, 如果curr>last, 最后last=curr以后notifiyAll
: 这个行吗？
，如果request非常少的话，这个额外开销是不小的。
用double linked list 保存每一个request的timestamp，在list size 确定不会太大
的情况下是可行的。实现也并不复杂。
concurrency我的想法是对每一个array的cell加锁，而不是对整个数组或者object加锁
，不过还没具体写过。
【在 p*****2 的大作中提到】
:
: 对。所以我会跟面试官说如果只是考虑thread safe的话我可以用synchronized. 这个
: 时候面试官应该就会提示也需要考虑高并发了吧？
: 按照java的library看，thread safe和concurrent貌似是分开的，并没有混在一起。
: double linked list我也没考虑过。实现起来比array容易吗？
: 具体来说高并发，可不可以这样。
: 如果curr==last的话，就可以直接返回结果，但是结果不是精确的，可能是近似的
: 如果curr!=last, 就wait
: 另外一个线程专门处理request, 如果curr>last, 最后last=curr以后notifiyAll
: 这个行吗？
p*2
66 楼
刚才想了一下，linkedlist用singly就可以了吧？貌似实现起来比array还简化了很多。
对没一个cell加lock的话，貌似对我的implementation作用不大呀。因为我一次性可能
清很多个cell。这个应该由一个thread来完成，貌似不能并行呀。
【在 h*****a 的大作中提到】
: 用array的实现来了一个新的request，有可能要去最多check数组里所有的3600个元素
: ，如果request非常少的话，这个额外开销是不小的。
: 用double linked list 保存每一个request的timestamp，在list size 确定不会太大
: 的情况下是可行的。实现也并不复杂。
: concurrency我的想法是对每一个array的cell加锁，而不是对整个数组或者object加锁
: ，不过还没具体写过。
h*a
67 楼
是，好像linked list就可以了。只要从头上开始清old record就好了。
如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
，而不是用一个last。
多。
【在 p*****2 的大作中提到】
:
: 刚才想了一下，linkedlist用singly就可以了吧？貌似实现起来比array还简化了很多。
: 对没一个cell加lock的话，貌似对我的implementation作用不大呀。因为我一次性可能
: 清很多个cell。这个应该由一个thread来完成，貌似不能并行呀。
如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
，而不是用一个last。
多。
【在 p*****2 的大作中提到】
:
: 刚才想了一下，linkedlist用singly就可以了吧？貌似实现起来比array还简化了很多。
: 对没一个cell加lock的话，貌似对我的implementation作用不大呀。因为我一次性可能
: 清很多个cell。这个应该由一个thread来完成，貌似不能并行呀。
p*2
68 楼
time
多谢大牛指点。
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
c*a
69 楼
很关键的一点就是request有多频繁。我问了，说大概每秒都能request一两次，我感觉
就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？
就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？
p*2
70 楼
我觉得是。
【在 c******a 的大作中提到】
: 很关键的一点就是request有多频繁。我问了，说大概每秒都能request一两次，我感觉
: 就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
: 这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？
c*a
71 楼
每个node得是个object，有timestamp，lock加在整个list上，对不？
这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
了。list就可以。
time
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
了。list就可以。
time
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
p*2
72 楼
貌似array放一年也没啥问题吧？
linkedlist如果request频繁更消耗空间。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
c*a
73 楼
back of envelope了一下，的确1年都没问题。景仰！！
linkedlist会有些overhead是真的。
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
linkedlist会有些overhead是真的。
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
g*e
74 楼
每秒才一两次，lock随便加哪都行……
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
r*n
75 楼
如果是一个月，一年，时间跨度大，可以用低resolution的array，比如两个indices之
间是1小时，当然最后答案就没有那么精确了，但是你可以求一个统计平均。一个月有
700多个小时，所以最后误差还是很小，更不要说一年了。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
间是1小时，当然最后答案就没有那么精确了，但是你可以求一个统计平均。一个月有
700多个小时，所以最后误差还是很小，更不要说一年了。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
s*x
76 楼
到此一游。
【在 c******a 的大作中提到】
: 室友早上G店面被问了这个
: http://www.careercup.com/question?id=6005446611566592
: 我下午F被问了同个问题
: http://www.careercup.com/question?id=14974850
: 我俩吵到现在还谁都没说服谁。。。
s*r
77 楼
牛人！
a*e
78 楼
I have one question regarding this problem: what does "the last second"
mean? It could mean 1 second before the current time till now, it could also
mean the last second slot (the most recent time round to seconds minus the
second most recent time round to seconds).
The first case (1s before current time till now) is more real time, and in
this case we can use a vector (or deque or any container that can be
dynamically expanded or shrinked with random accesses) to store the time of
incoming requests/events. Maintain the size of the vector. When new request
comes, insert the time into the vector and update the size. Periodically (e.
g., 1 minute) delete the outdated entries from the beginning of the vector (
oldest events, we can safely delete the
events before current time-1 day). Or the delete can be performed upon
every insertion (if we do this the amortized time for insertion is still O(1
) if requests are coming at a stable rate). Now to get the last minute
events, we can calculate the current time-60 seconds and use that time to do
a binary search. This takes O(lgn) where n is the number of events in the
vector.
For the second case (time slot) we can use an circular array with a size of
60*60 if we want to retrieve the number of events upto 1 hour ago, or a size
of 60*60*24 if we want to go back upto 1 day ago. In addition to the
circular array, we use six variables, counterHour, counterMin and counterSec
(and their prior slot versions) to keep track of the number of events
respectively. Upon a new event, we increment the 3 counters for the current
hour, min and sec slots. When we hit an even second, we copy counterSec to
counterSecPrev and clear counterSec. We do similar things upon even minute
and hour. Now to get the last minute events for example, we can just return
counterMinPrev in O(1). Actually we don't need the circular array in this
case. We only need that 6 variables.
For thread safety, we need lock the variable before updating it.
mean? It could mean 1 second before the current time till now, it could also
mean the last second slot (the most recent time round to seconds minus the
second most recent time round to seconds).
The first case (1s before current time till now) is more real time, and in
this case we can use a vector (or deque or any container that can be
dynamically expanded or shrinked with random accesses) to store the time of
incoming requests/events. Maintain the size of the vector. When new request
comes, insert the time into the vector and update the size. Periodically (e.
g., 1 minute) delete the outdated entries from the beginning of the vector (
oldest events, we can safely delete the
events before current time-1 day). Or the delete can be performed upon
every insertion (if we do this the amortized time for insertion is still O(1
) if requests are coming at a stable rate). Now to get the last minute
events, we can calculate the current time-60 seconds and use that time to do
a binary search. This takes O(lgn) where n is the number of events in the
vector.
For the second case (time slot) we can use an circular array with a size of
60*60 if we want to retrieve the number of events upto 1 hour ago, or a size
of 60*60*24 if we want to go back upto 1 day ago. In addition to the
circular array, we use six variables, counterHour, counterMin and counterSec
(and their prior slot versions) to keep track of the number of events
respectively. Upon a new event, we increment the 3 counters for the current
hour, min and sec slots. When we hit an even second, we copy counterSec to
counterSecPrev and clear counterSec. We do similar things upon even minute
and hour. Now to get the last minute events for example, we can just return
counterMinPrev in O(1). Actually we don't need the circular array in this
case. We only need that 6 variables.
For thread safety, we need lock the variable before updating it.
x*0
79 楼
mark
c*a
80 楼
赞思路，赞问的第一个问题。一定会很得面试官心。
circular还是要的。不然59分钟之后一怎么evict第一分钟那个已经out of bound的呢。
also
the
of
request
e.
(
【在 a**********e 的大作中提到】
: I have one question regarding this problem: what does "the last second"
: mean? It could mean 1 second before the current time till now, it could also
: mean the last second slot (the most recent time round to seconds minus the
: second most recent time round to seconds).
: The first case (1s before current time till now) is more real time, and in
: this case we can use a vector (or deque or any container that can be
: dynamically expanded or shrinked with random accesses) to store the time of
: incoming requests/events. Maintain the size of the vector. When new request
: comes, insert the time into the vector and update the size. Periodically (e.
: g., 1 minute) delete the outdated entries from the beginning of the vector (
circular还是要的。不然59分钟之后一怎么evict第一分钟那个已经out of bound的呢。
also
the
of
request
e.
(
【在 a**********e 的大作中提到】
: I have one question regarding this problem: what does "the last second"
: mean? It could mean 1 second before the current time till now, it could also
: mean the last second slot (the most recent time round to seconds minus the
: second most recent time round to seconds).
: The first case (1s before current time till now) is more real time, and in
: this case we can use a vector (or deque or any container that can be
: dynamically expanded or shrinked with random accesses) to store the time of
: incoming requests/events. Maintain the size of the vector. When new request
: comes, insert the time into the vector and update the size. Periodically (e.
: g., 1 minute) delete the outdated entries from the beginning of the vector (
x*0
81 楼
mark
S*n
82 楼
高并发用不用lock每个slot吧，update的时候如果有人在读，再拷贝一份好了，读到的
东西虽然old了一点，但没有什么影响，实际应用中，拷贝的次数也很少
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
东西虽然old了一点，但没有什么影响，实际应用中，拷贝的次数也很少
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
h*p
83 楼
mark
l*o
84 楼
如果我理解题目没错，他只需要你最后一秒一分钟和一小时的request的数。不明白为
什么要用到Array. 应该只需要三个counter就足够了。这个code有什么问题吗？（除了
不支持并发）
long startTime = new Date().getTime();
int lastSecondRequests = 0;
long lastMinuteRequests = 0;
long lastHourRequests = 0;
long whichSecond = 0;
long whichMinute = 0;
void requestHandler(HttpRequest request) {
long currentTime = new Date().getTime();
long secondSpan = Math.round((currentTime - startTime) / 1000 + 0.5);
long minuteSpan = Math.round((currentTime - startTime) / 60 * 1000 + 0.5
);
long hourSpan = Math.round((currentTime - startTime) / 3600 * 1000 + 0.5
);
if(hourSpan > whichHour) {
whichHour = HourSpan;
lastHourRequests = 1;
} else {
lastHourRequests++;
}
if(minuteSpan > whichMinute) {
whichMinute = minuteSpan;
lastMinuteRequests = 1;
} else {
lastMinuteRequests++;
}
if(secondSpan > whichSecond) {
whichSecond = secondSpan;
lastSecondRequests = 1;
} else {
lastSecondRequests++;
}
}
什么要用到Array. 应该只需要三个counter就足够了。这个code有什么问题吗？（除了
不支持并发）
long startTime = new Date().getTime();
int lastSecondRequests = 0;
long lastMinuteRequests = 0;
long lastHourRequests = 0;
long whichSecond = 0;
long whichMinute = 0;
void requestHandler(HttpRequest request) {
long currentTime = new Date().getTime();
long secondSpan = Math.round((currentTime - startTime) / 1000 + 0.5);
long minuteSpan = Math.round((currentTime - startTime) / 60 * 1000 + 0.5
);
long hourSpan = Math.round((currentTime - startTime) / 3600 * 1000 + 0.5
);
if(hourSpan > whichHour) {
whichHour = HourSpan;
lastHourRequests = 1;
} else {
lastHourRequests++;
}
if(minuteSpan > whichMinute) {
whichMinute = minuteSpan;
lastMinuteRequests = 1;
} else {
lastMinuteRequests++;
}
if(secondSpan > whichSecond) {
whichSecond = secondSpan;
lastSecondRequests = 1;
} else {
lastSecondRequests++;
}
}
s*u
85 楼
没太明白用list怎么计数。是说node里面存当前1秒的数量么？然后用一个double list
，如果要计一小时，就往前数3600个node？
我在想能不能用list每个node存timestamp，然后用map来存timestamp-id的mapping，
然后两个id一减。当然，其实这个就是前面有人提到的bst了。
，如果要计一小时，就往前数3600个node？
我在想能不能用list每个node存timestamp，然后用map来存timestamp-id的mapping，
然后两个id一减。当然，其实这个就是前面有人提到的bst了。
c*a
86 楼
室友早上G店面被问了这个
http://www.careercup.com/question?id=6005446611566592
我下午F被问了同个问题
http://www.careercup.com/question?id=14974850
我俩吵到现在还谁都没说服谁。。。
http://www.careercup.com/question?id=6005446611566592
我下午F被问了同个问题
http://www.careercup.com/question?id=14974850
我俩吵到现在还谁都没说服谁。。。
h*n
87 楼
Interval tree
p*2
88 楼
这个用个循环数组可以吗
x*w
89 楼
order statistic tree
每个node按时间顺序排序，每个node保存子树个数和代表event的时间戳，一个node获
取需要lgn的复杂度。每当一个event arrive, 很快可以知道时间范围。
问题是怎么有效的清除过期节点并保持statistic tree的平衡
每个node按时间顺序排序，每个node保存子树个数和代表event的时间戳，一个node获
取需要lgn的复杂度。每当一个event arrive, 很快可以知道时间范围。
问题是怎么有效的清除过期节点并保持statistic tree的平衡
h*a
90 楼
基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
，任何超过常数时间的算法都是不可行的。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
，任何超过常数时间的算法都是不可行的。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
p*2
91 楼
多谢大牛confirm，循环数组O(1)就可以了。
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
r*h
92 楼
请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
top5呢？
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
top5呢？
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
r*h
93 楼
二爷能展开说说吗？如何做到O(1)找到当前top5呢
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
h*a
94 楼
ft，你有什么更好的idea可以分享一下啊，这道是高频题
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
p*2
95 楼
有说找top5吗？
【在 r**h 的大作中提到】
: 二爷能展开说说吗？如何做到O(1)找到当前top5呢
h*a
96 楼
这道题问的是request的count，不需要保存数据啊。没有什么top 5啊.
【在 r**h 的大作中提到】
: 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
: 那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
: 是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
: top5呢？
【在 r**h 的大作中提到】
: 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
: 那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
: 是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
: top5呢？
r*h
97 楼
哦，我和那一题找5分钟、1小时、24小时内的query搞混了。。不好意思啊
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
h*a
98 楼
用循环数组也有tricky的地方，你写写 code试试。
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
p*2
99 楼
是。我能想到一些cases。一段时间没有request的话，需要把中间的都清零。
【在 h*****a 的大作中提到】
: 用循环数组也有tricky的地方，你写写 code试试。
p*2
100 楼
我觉得高频题太多了，搞不过来呀。
【在 h*****a 的大作中提到】
: ft，你有什么更好的idea可以分享一下啊，这道是高频题
c*a
101 楼
感动得暴出了泪花。当时狗急跳墙用的就是一个数组去循环，没想到给我蒙对了！！！
不过wrap around很难写bug free，我时间到了连brutal force都没写完，唉。。。。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
不过wrap around很难写bug free，我时间到了连brutal force都没写完，唉。。。。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
c*a
102 楼
频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
然后就是2011年一次。
恰好跟室友撞了而已。
【在 p*****2 的大作中提到】
:
: 我觉得高频题太多了，搞不过来呀。
然后就是2011年一次。
恰好跟室友撞了而已。
【在 p*****2 的大作中提到】
:
: 我觉得高频题太多了，搞不过来呀。
p*2
103 楼
你室友怎么做的？这题在板上以前确实看到过几次。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
h*a
104 楼
这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
系统，都有类似的需求。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
系统，都有类似的需求。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
z*8
105 楼
二爷能具体讲讲吗？
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
p*2
106 楼
瞎写了一个。
final int SIZE=60*60; //seconds in one hour
int[] arr=new int[SIZE];
int hour=0;
int minute=0;
long last=0;
long currSecond(){
return System.currentTimeMillis()/1000;
}
long clear(){
long curr=currSecond();
if(curr>last){
if(curr-last>=SIZE){
hour=0;
minute=0;
Arrays.fill(arr,0);
}
else{
if(curr-last>=60){
minute=0;
}
else{
for(long i=last-60+1;i<=curr-60;i++){
minute-=arr[(int)(i%SIZE)];
}
}
for(long i=last+1;i<=curr;i++){
int p=(int)(i%SIZE);
hour-=arr[p];
arr[p]=0;
}
}
last=curr;
}
return curr;
}
void request(){
long curr=clear();
arr[(int)(curr%SIZE)]++;
hour++;
minute++;
}
int lastSecond(){
long curr=clear();
return arr[(int)(curr%SIZE)];
}
int lastMinute(){
clear();
return minute;
}
int lastHour(){
clear();
return hour;
}
【在 z*********8 的大作中提到】
: 二爷能具体讲讲吗？
r*e
107 楼
膜拜
【在 p*****2 的大作中提到】
:
: 瞎写了一个。
: final int SIZE=60*60; //seconds in one hour
: int[] arr=new int[SIZE];
: int hour=0;
: int minute=0;
: long last=0;
:
: long currSecond(){
: return System.currentTimeMillis()/1000;
【在 p*****2 的大作中提到】
:
: 瞎写了一个。
: final int SIZE=60*60; //seconds in one hour
: int[] arr=new int[SIZE];
: int hour=0;
: int minute=0;
: long last=0;
:
: long currSecond(){
: return System.currentTimeMillis()/1000;
a*r
108 楼
Only need 2 60 element array. Just record request count for last 60 seconds
and counts for last 60 mins. Update them accordingly based on the count for
each new seconds.
and counts for last 60 mins. Update them accordingly based on the count for
each new seconds.
r*e
109 楼
你这个得不到严格意义上的last hour count
因为minite array里的数据都是对齐在整minite边界上的
而查询的时候不一定是在整minite上
当然对于近似的查询没问题
seconds
for
【在 a*******r 的大作中提到】
: Only need 2 60 element array. Just record request count for last 60 seconds
: and counts for last 60 mins. Update them accordingly based on the count for
: each new seconds.
因为minite array里的数据都是对齐在整minite边界上的
而查询的时候不一定是在整minite上
当然对于近似的查询没问题
seconds
for
【在 a*******r 的大作中提到】
: Only need 2 60 element array. Just record request count for last 60 seconds
: and counts for last 60 mins. Update them accordingly based on the count for
: each new seconds.
c*a
110 楼
丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
【在 p*****2 的大作中提到】
:
: 瞎写了一个。
: final int SIZE=60*60; //seconds in one hour
: int[] arr=new int[SIZE];
: int hour=0;
: int minute=0;
: long last=0;
:
: long currSecond(){
: return System.currentTimeMillis()/1000;
【在 p*****2 的大作中提到】
:
: 瞎写了一个。
: final int SIZE=60*60; //seconds in one hour
: int[] arr=new int[SIZE];
: int hour=0;
: int minute=0;
: long last=0;
:
: long currSecond(){
: return System.currentTimeMillis()/1000;
r*e
111 楼
circular buckets是正道，B+是走入歧途了
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
p*2
112 楼
感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
吧？我感觉面试没有必要上来就想搞最优解。
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
h*a
113 楼
一个扩展问题是要thread safe.
【在 p*****2 的大作中提到】
:
: 感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
: solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
: 吧？我感觉面试没有必要上来就想搞最优解。
【在 p*****2 的大作中提到】
:
: 感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
: solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
: 吧？我感觉面试没有必要上来就想搞最优解。
p*2
114 楼
如果只是要求thread safe的话，加上synchronized keyword就可以了。
【在 h*****a 的大作中提到】
: 一个扩展问题是要thread safe.
g*e
115 楼
这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
时候可以做sampling然后predict
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
时候可以做sampling然后predict
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
h*a
116 楼
如果request 非常频繁的话，明显效率不高啊
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
g*e
117 楼
赞，这才是这个题真正的目的
metrics
【在 h*****a 的大作中提到】
: 这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
: 系统，都有类似的需求。
metrics
【在 h*****a 的大作中提到】
: 这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
: 系统，都有类似的需求。
h*a
118 楼
难道这不是metrics/monitoring系统必须解决的实际问题么？
【在 g**e 的大作中提到】
: 这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
: 时候可以做sampling然后predict
【在 g**e 的大作中提到】
: 这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
: 时候可以做sampling然后predict
g*e
119 楼
是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
大的
【在 h*****a 的大作中提到】
: 难道这不是metrics/monitoring系统必须解决的实际问题么？
大的
【在 h*****a 的大作中提到】
: 难道这不是metrics/monitoring系统必须解决的实际问题么？
h*a
120 楼
你说的有道理。绝对精确确实不需要，但基本精确还是要保证的，尤其是用于
monitoring的时候。
【在 g**e 的大作中提到】
: 是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
:
: 大的
monitoring的时候。
【在 g**e 的大作中提到】
: 是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
:
: 大的
p*2
121 楼
所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
【在 h*****a 的大作中提到】
: 如果request 非常频繁的话，明显效率不高啊
h*a
122 楼
hehe, 如果问你这道题的interviewer让你实现thread safe，你说你是应该主动问他是
不是我应该考虑高并发，然后给他一个支持高并发的solution，还是应该直接用
synchronized呢？虽然问题比较模糊，但事实上我觉得既然这是一个比较实际的问题，
而且用circular array的一个前提就是request比较频繁（否则完全可以用double
linked list），那高并发是理所应当的啊。
【在 p*****2 的大作中提到】
:
: 所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
不是我应该考虑高并发，然后给他一个支持高并发的solution，还是应该直接用
synchronized呢？虽然问题比较模糊，但事实上我觉得既然这是一个比较实际的问题，
而且用circular array的一个前提就是request比较频繁（否则完全可以用double
linked list），那高并发是理所应当的啊。
【在 p*****2 的大作中提到】
:
: 所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
p*2
123 楼
对。所以我会跟面试官说如果只是考虑thread safe的话我可以用synchronized. 这个
时候面试官应该就会提示也需要考虑高并发了吧？
按照java的library看，thread safe和concurrent貌似是分开的，并没有混在一起。
double linked list我也没考虑过。实现起来比array容易吗？
具体来说高并发，可不可以这样。
如果curr==last的话，就可以直接返回结果，但是结果不是精确的，可能是近似的
如果curr!=last, 就wait
另外一个线程专门处理request, 如果curr>last, 最后last=curr以后notifiyAll
这个行吗？
【在 h*****a 的大作中提到】
: hehe, 如果问你这道题的interviewer让你实现thread safe，你说你是应该主动问他是
: 不是我应该考虑高并发，然后给他一个支持高并发的solution，还是应该直接用
: synchronized呢？虽然问题比较模糊，但事实上我觉得既然这是一个比较实际的问题，
: 而且用circular array的一个前提就是request比较频繁（否则完全可以用double
: linked list），那高并发是理所应当的啊。
h*a
124 楼
用array的实现来了一个新的request，有可能要去最多check数组里所有的3600个元素
，如果request非常少的话，这个额外开销是不小的。
用double linked list 保存每一个request的timestamp，在list size 确定不会太大
的情况下是可行的。实现也并不复杂。
concurrency我的想法是对每一个array的cell加锁，而不是对整个数组或者object加锁
，不过还没具体写过。
【在 p*****2 的大作中提到】
:
: 对。所以我会跟面试官说如果只是考虑thread safe的话我可以用synchronized. 这个
: 时候面试官应该就会提示也需要考虑高并发了吧？
: 按照java的library看，thread safe和concurrent貌似是分开的，并没有混在一起。
: double linked list我也没考虑过。实现起来比array容易吗？
: 具体来说高并发，可不可以这样。
: 如果curr==last的话，就可以直接返回结果，但是结果不是精确的，可能是近似的
: 如果curr!=last, 就wait
: 另外一个线程专门处理request, 如果curr>last, 最后last=curr以后notifiyAll
: 这个行吗？
，如果request非常少的话，这个额外开销是不小的。
用double linked list 保存每一个request的timestamp，在list size 确定不会太大
的情况下是可行的。实现也并不复杂。
concurrency我的想法是对每一个array的cell加锁，而不是对整个数组或者object加锁
，不过还没具体写过。
【在 p*****2 的大作中提到】
:
: 对。所以我会跟面试官说如果只是考虑thread safe的话我可以用synchronized. 这个
: 时候面试官应该就会提示也需要考虑高并发了吧？
: 按照java的library看，thread safe和concurrent貌似是分开的，并没有混在一起。
: double linked list我也没考虑过。实现起来比array容易吗？
: 具体来说高并发，可不可以这样。
: 如果curr==last的话，就可以直接返回结果，但是结果不是精确的，可能是近似的
: 如果curr!=last, 就wait
: 另外一个线程专门处理request, 如果curr>last, 最后last=curr以后notifiyAll
: 这个行吗？
p*2
125 楼
刚才想了一下，linkedlist用singly就可以了吧？貌似实现起来比array还简化了很多。
对没一个cell加lock的话，貌似对我的implementation作用不大呀。因为我一次性可能
清很多个cell。这个应该由一个thread来完成，貌似不能并行呀。
【在 h*****a 的大作中提到】
: 用array的实现来了一个新的request，有可能要去最多check数组里所有的3600个元素
: ，如果request非常少的话，这个额外开销是不小的。
: 用double linked list 保存每一个request的timestamp，在list size 确定不会太大
: 的情况下是可行的。实现也并不复杂。
: concurrency我的想法是对每一个array的cell加锁，而不是对整个数组或者object加锁
: ，不过还没具体写过。
h*a
126 楼
是，好像linked list就可以了。只要从头上开始清old record就好了。
如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
，而不是用一个last。
多。
【在 p*****2 的大作中提到】
:
: 刚才想了一下，linkedlist用singly就可以了吧？貌似实现起来比array还简化了很多。
: 对没一个cell加lock的话，貌似对我的implementation作用不大呀。因为我一次性可能
: 清很多个cell。这个应该由一个thread来完成，貌似不能并行呀。
如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
，而不是用一个last。
多。
【在 p*****2 的大作中提到】
:
: 刚才想了一下，linkedlist用singly就可以了吧？貌似实现起来比array还简化了很多。
: 对没一个cell加lock的话，貌似对我的implementation作用不大呀。因为我一次性可能
: 清很多个cell。这个应该由一个thread来完成，貌似不能并行呀。
p*2
127 楼
time
多谢大牛指点。
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
c*a
128 楼
很关键的一点就是request有多频繁。我问了，说大概每秒都能request一两次，我感觉
就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？
就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？
p*2
129 楼
我觉得是。
【在 c******a 的大作中提到】
: 很关键的一点就是request有多频繁。我问了，说大概每秒都能request一两次，我感觉
: 就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
: 这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？
c*a
130 楼
每个node得是个object，有timestamp，lock加在整个list上，对不？
这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
了。list就可以。
time
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
了。list就可以。
time
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
p*2
131 楼
貌似array放一年也没啥问题吧？
linkedlist如果request频繁更消耗空间。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
c*a
132 楼
back of envelope了一下，的确1年都没问题。景仰！！
linkedlist会有些overhead是真的。
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
linkedlist会有些overhead是真的。
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
g*e
133 楼
每秒才一两次，lock随便加哪都行……
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
r*n
134 楼
如果是一个月，一年，时间跨度大，可以用低resolution的array，比如两个indices之
间是1小时，当然最后答案就没有那么精确了，但是你可以求一个统计平均。一个月有
700多个小时，所以最后误差还是很小，更不要说一年了。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
间是1小时，当然最后答案就没有那么精确了，但是你可以求一个统计平均。一个月有
700多个小时，所以最后误差还是很小，更不要说一年了。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
s*x
135 楼
到此一游。
【在 c******a 的大作中提到】
: 室友早上G店面被问了这个
: http://www.careercup.com/question?id=6005446611566592
: 我下午F被问了同个问题
: http://www.careercup.com/question?id=14974850
: 我俩吵到现在还谁都没说服谁。。。
s*r
136 楼
牛人！
a*e
137 楼
I have one question regarding this problem: what does "the last second"
mean? It could mean 1 second before the current time till now, it could also
mean the last second slot (the most recent time round to seconds minus the
second most recent time round to seconds).
The first case (1s before current time till now) is more real time, and in
this case we can use a vector (or deque or any container that can be
dynamically expanded or shrinked with random accesses) to store the time of
incoming requests/events. Maintain the size of the vector. When new request
comes, insert the time into the vector and update the size. Periodically (e.
g., 1 minute) delete the outdated entries from the beginning of the vector (
oldest events, we can safely delete the
events before current time-1 day). Or the delete can be performed upon
every insertion (if we do this the amortized time for insertion is still O(1
) if requests are coming at a stable rate). Now to get the last minute
events, we can calculate the current time-60 seconds and use that time to do
a binary search. This takes O(lgn) where n is the number of events in the
vector.
For the second case (time slot) we can use an circular array with a size of
60*60 if we want to retrieve the number of events upto 1 hour ago, or a size
of 60*60*24 if we want to go back upto 1 day ago. In addition to the
circular array, we use six variables, counterHour, counterMin and counterSec
(and their prior slot versions) to keep track of the number of events
respectively. Upon a new event, we increment the 3 counters for the current
hour, min and sec slots. When we hit an even second, we copy counterSec to
counterSecPrev and clear counterSec. We do similar things upon even minute
and hour. Now to get the last minute events for example, we can just return
counterMinPrev in O(1). Actually we don't need the circular array in this
case. We only need that 6 variables.
For thread safety, we need lock the variable before updating it.
mean? It could mean 1 second before the current time till now, it could also
mean the last second slot (the most recent time round to seconds minus the
second most recent time round to seconds).
The first case (1s before current time till now) is more real time, and in
this case we can use a vector (or deque or any container that can be
dynamically expanded or shrinked with random accesses) to store the time of
incoming requests/events. Maintain the size of the vector. When new request
comes, insert the time into the vector and update the size. Periodically (e.
g., 1 minute) delete the outdated entries from the beginning of the vector (
oldest events, we can safely delete the
events before current time-1 day). Or the delete can be performed upon
every insertion (if we do this the amortized time for insertion is still O(1
) if requests are coming at a stable rate). Now to get the last minute
events, we can calculate the current time-60 seconds and use that time to do
a binary search. This takes O(lgn) where n is the number of events in the
vector.
For the second case (time slot) we can use an circular array with a size of
60*60 if we want to retrieve the number of events upto 1 hour ago, or a size
of 60*60*24 if we want to go back upto 1 day ago. In addition to the
circular array, we use six variables, counterHour, counterMin and counterSec
(and their prior slot versions) to keep track of the number of events
respectively. Upon a new event, we increment the 3 counters for the current
hour, min and sec slots. When we hit an even second, we copy counterSec to
counterSecPrev and clear counterSec. We do similar things upon even minute
and hour. Now to get the last minute events for example, we can just return
counterMinPrev in O(1). Actually we don't need the circular array in this
case. We only need that 6 variables.
For thread safety, we need lock the variable before updating it.
x*0
138 楼
mark
c*a
139 楼
赞思路，赞问的第一个问题。一定会很得面试官心。
circular还是要的。不然59分钟之后一怎么evict第一分钟那个已经out of bound的呢。
also
the
of
request
e.
(
【在 a**********e 的大作中提到】
: I have one question regarding this problem: what does "the last second"
: mean? It could mean 1 second before the current time till now, it could also
: mean the last second slot (the most recent time round to seconds minus the
: second most recent time round to seconds).
: The first case (1s before current time till now) is more real time, and in
: this case we can use a vector (or deque or any container that can be
: dynamically expanded or shrinked with random accesses) to store the time of
: incoming requests/events. Maintain the size of the vector. When new request
: comes, insert the time into the vector and update the size. Periodically (e.
: g., 1 minute) delete the outdated entries from the beginning of the vector (
circular还是要的。不然59分钟之后一怎么evict第一分钟那个已经out of bound的呢。
also
the
of
request
e.
(
【在 a**********e 的大作中提到】
: I have one question regarding this problem: what does "the last second"
: mean? It could mean 1 second before the current time till now, it could also
: mean the last second slot (the most recent time round to seconds minus the
: second most recent time round to seconds).
: The first case (1s before current time till now) is more real time, and in
: this case we can use a vector (or deque or any container that can be
: dynamically expanded or shrinked with random accesses) to store the time of
: incoming requests/events. Maintain the size of the vector. When new request
: comes, insert the time into the vector and update the size. Periodically (e.
: g., 1 minute) delete the outdated entries from the beginning of the vector (
x*0
140 楼
mark
S*n
141 楼
高并发用不用lock每个slot吧，update的时候如果有人在读，再拷贝一份好了，读到的
东西虽然old了一点，但没有什么影响，实际应用中，拷贝的次数也很少
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
东西虽然old了一点，但没有什么影响，实际应用中，拷贝的次数也很少
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
h*p
142 楼
mark
l*o
143 楼
如果我理解题目没错，他只需要你最后一秒一分钟和一小时的request的数。不明白为
什么要用到Array. 应该只需要三个counter就足够了。这个code有什么问题吗？（除了
不支持并发）
long startTime = new Date().getTime();
int lastSecondRequests = 0;
long lastMinuteRequests = 0;
long lastHourRequests = 0;
long whichSecond = 0;
long whichMinute = 0;
void requestHandler(HttpRequest request) {
long currentTime = new Date().getTime();
long secondSpan = Math.round((currentTime - startTime) / 1000 + 0.5);
long minuteSpan = Math.round((currentTime - startTime) / 60 * 1000 + 0.5
);
long hourSpan = Math.round((currentTime - startTime) / 3600 * 1000 + 0.5
);
if(hourSpan > whichHour) {
whichHour = HourSpan;
lastHourRequests = 1;
} else {
lastHourRequests++;
}
if(minuteSpan > whichMinute) {
whichMinute = minuteSpan;
lastMinuteRequests = 1;
} else {
lastMinuteRequests++;
}
if(secondSpan > whichSecond) {
whichSecond = secondSpan;
lastSecondRequests = 1;
} else {
lastSecondRequests++;
}
}
什么要用到Array. 应该只需要三个counter就足够了。这个code有什么问题吗？（除了
不支持并发）
long startTime = new Date().getTime();
int lastSecondRequests = 0;
long lastMinuteRequests = 0;
long lastHourRequests = 0;
long whichSecond = 0;
long whichMinute = 0;
void requestHandler(HttpRequest request) {
long currentTime = new Date().getTime();
long secondSpan = Math.round((currentTime - startTime) / 1000 + 0.5);
long minuteSpan = Math.round((currentTime - startTime) / 60 * 1000 + 0.5
);
long hourSpan = Math.round((currentTime - startTime) / 3600 * 1000 + 0.5
);
if(hourSpan > whichHour) {
whichHour = HourSpan;
lastHourRequests = 1;
} else {
lastHourRequests++;
}
if(minuteSpan > whichMinute) {
whichMinute = minuteSpan;
lastMinuteRequests = 1;
} else {
lastMinuteRequests++;
}
if(secondSpan > whichSecond) {
whichSecond = secondSpan;
lastSecondRequests = 1;
} else {
lastSecondRequests++;
}
}
s*u
144 楼
没太明白用list怎么计数。是说node里面存当前1秒的数量么？然后用一个double list
，如果要计一小时，就往前数3600个node？
我在想能不能用list每个node存timestamp，然后用map来存timestamp-id的mapping，
然后两个id一减。当然，其实这个就是前面有人提到的bst了。
，如果要计一小时，就往前数3600个node？
我在想能不能用list每个node存timestamp，然后用map来存timestamp-id的mapping，
然后两个id一减。当然，其实这个就是前面有人提到的bst了。
g*g
145 楼
两部分：
1 建立counter for every second
可以用循环数组
2 建立 window （5分钟，1 小时，等等）
这个问题就是一个固定window 滑动的问题了。
可以在 O（1） 返回结果
1 建立counter for every second
可以用循环数组
2 建立 window （5分钟，1 小时，等等）
这个问题就是一个固定window 滑动的问题了。
可以在 O（1） 返回结果
g*g
146 楼
两部分：
1 建立counter for every second
可以用循环数组
2 建立 window （5分钟，1 小时，等等）
这个问题就是一个固定window 滑动的问题了。
可以在 O（1） 返回结果
1 建立counter for every second
可以用循环数组
2 建立 window （5分钟，1 小时，等等）
这个问题就是一个固定window 滑动的问题了。
可以在 O（1） 返回结果
g*g
147 楼
Second this, if you need sub-second accuracy. You can record each request
with the timestamp, retrieve the head and tail second records for adjustment.
You'll need a linked list, plus a 3600 second indexing rotational array for
data
structure, each array entry would point to the first request after a round
second. Build another index for minute or whatever period.
【在 g*****g 的大作中提到】
: 两部分：
: 1 建立counter for every second
: 可以用循环数组
: 2 建立 window （5分钟，1 小时，等等）
: 这个问题就是一个固定window 滑动的问题了。
: 可以在 O（1） 返回结果
with the timestamp, retrieve the head and tail second records for adjustment.
You'll need a linked list, plus a 3600 second indexing rotational array for
data
structure, each array entry would point to the first request after a round
second. Build another index for minute or whatever period.
【在 g*****g 的大作中提到】
: 两部分：
: 1 建立counter for every second
: 可以用循环数组
: 2 建立 window （5分钟，1 小时，等等）
: 这个问题就是一个固定window 滑动的问题了。
: 可以在 O（1） 返回结果
相关阅读
cvs 在 5/7 之前如何花 $20 啊How to buy this week?[转让]Similac 3off coupon 10张有没有ＴＸ喜欢这个公司的包包RecycleBank的 Naked Juice 死了？20多刀ebay bucks能买啥 (转载)靶子店25折大家都买到了啥？上图吧！{出售}couponFree Dove Daily Treatment Conditioner Sample2包子求 angelsun的电话囧了，FSA是包括tax的Safeway: Hallmark card moneymaker this weekGO8，那个O牌的蒜泥酱在哪个货架啊。。找不到喔。请教各位新开的CVS extracare卡怎么申请得到$5off20 啊？包子（求）shopper链接Aveeno Sun Care at Target, Only $0.99尾毛physician fomula的绿叶子mascara都是干的？CVS 有些巧克力75% OFF,Rite Aid Thermacare恭喜老Ｅ， 恭喜猪版！！