c******a
发帖数: 789 | |
h*****n
发帖数: 15 | |
p*****2
发帖数: 21240 | |
x*********w
发帖数: 533 | 4 order statistic tree
每个node按时间顺序排序，每个node保存子树个数和代表event的时间戳，一个node获
取需要lgn的复杂度。每当一个event arrive, 很快可以知道时间范围。
问题是怎么有效的清除过期节点并保持statistic tree的平衡 |
h*****a
发帖数: 1718 | 5 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
，任何超过常数时间的算法都是不可行的。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
|
p*****2
发帖数: 21240 | 6
多谢大牛confirm，循环数组O(1)就可以了。
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
|
r**h
发帖数: 1288 | 7 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
top5呢？
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
|
r**h
发帖数: 1288 | 8 二爷能展开说说吗？如何做到O(1)找到当前top5呢
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
|
h*****a
发帖数: 1718 | 9 ft，你有什么更好的idea可以分享一下啊，这道是高频题
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
|
p*****2
发帖数: 21240 | 10
有说找top5吗？
【在 r**h 的大作中提到】
: 二爷能展开说说吗？如何做到O(1)找到当前top5呢
|
|
|
h*****a
发帖数: 1718 | 11 这道题问的是request的count，不需要保存数据啊。没有什么top 5啊.
【在 r**h 的大作中提到】
: 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
: 那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
: 是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
: top5呢？
|
r**h
发帖数: 1288 | 12 哦，我和那一题找5分钟、1小时、24小时内的query搞混了。。不好意思啊
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
|
h*****a
发帖数: 1718 | 13 用循环数组也有tricky的地方，你写写 code试试。
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
|
p*****2
发帖数: 21240 | 14
是。我能想到一些cases。一段时间没有request的话，需要把中间的都清零。
【在 h*****a 的大作中提到】
: 用循环数组也有tricky的地方，你写写 code试试。
|
p*****2
发帖数: 21240 | 15
我觉得高频题太多了，搞不过来呀。
【在 h*****a 的大作中提到】
: ft，你有什么更好的idea可以分享一下啊，这道是高频题
|
c******a
发帖数: 789 | 16 感动得暴出了泪花。当时狗急跳墙用的就是一个数组去循环，没想到给我蒙对了！！！
不过wrap around很难写bug free，我时间到了连brutal force都没写完，唉。。。。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
|
c******a
发帖数: 789 | 17 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
然后就是2011年一次。
恰好跟室友撞了而已。
【在 p*****2 的大作中提到】
:
: 我觉得高频题太多了，搞不过来呀。
|
p*****2
发帖数: 21240 | 18
你室友怎么做的？这题在板上以前确实看到过几次。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
|
h*****a
发帖数: 1718 | 19 这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
系统，都有类似的需求。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
|
z*********8
发帖数: 2070 | 20 二爷能具体讲讲吗？
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
|
|
|
p*****2
发帖数: 21240 | 21
瞎写了一个。
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
发帖数: 7583 | 22 膜拜
【在 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
发帖数: 122 | 23 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. |
r*******e
发帖数: 7583 | 24 你这个得不到严格意义上的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.
|
c******a
发帖数: 789 | 25 丫用的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;
|
r*******e
发帖数: 7583 | 26 circular buckets是正道，B+是走入歧途了
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
|
p*****2
发帖数: 21240 | 27
感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
吧？我感觉面试没有必要上来就想搞最优解。
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
|
h*****a
发帖数: 1718 | 28 一个扩展问题是要thread safe.
【在 p*****2 的大作中提到】
:
: 感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
: solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
: 吧？我感觉面试没有必要上来就想搞最优解。
|
p*****2
发帖数: 21240 | 29
如果只是要求thread safe的话，加上synchronized keyword就可以了。
【在 h*****a 的大作中提到】
: 一个扩展问题是要thread safe.
|
g**e
发帖数: 6127 | 30 这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
时候可以做sampling然后predict
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
|
|
|
h*****a
发帖数: 1718 | 31 如果request 非常频繁的话，明显效率不高啊
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
|
g**e
发帖数: 6127 | 32 赞，这才是这个题真正的目的
metrics
【在 h*****a 的大作中提到】
: 这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
: 系统，都有类似的需求。
|
h*****a
发帖数: 1718 | 33 难道这不是metrics/monitoring系统必须解决的实际问题么？
【在 g**e 的大作中提到】
: 这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
: 时候可以做sampling然后predict
|
g**e
发帖数: 6127 | 34 是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
大的
【在 h*****a 的大作中提到】
: 难道这不是metrics/monitoring系统必须解决的实际问题么？
|
h*****a
发帖数: 1718 | 35 你说的有道理。绝对精确确实不需要，但基本精确还是要保证的，尤其是用于
monitoring的时候。
【在 g**e 的大作中提到】
: 是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
:
: 大的
|
p*****2
发帖数: 21240 | 36
所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
【在 h*****a 的大作中提到】
: 如果request 非常频繁的话，明显效率不高啊
|
h*****a
发帖数: 1718 | 37 hehe, 如果问你这道题的interviewer让你实现thread safe，你说你是应该主动问他是
不是我应该考虑高并发，然后给他一个支持高并发的solution，还是应该直接用
synchronized呢？虽然问题比较模糊，但事实上我觉得既然这是一个比较实际的问题，
而且用circular array的一个前提就是request比较频繁（否则完全可以用double
linked list），那高并发是理所应当的啊。
【在 p*****2 的大作中提到】
:
: 所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
|
p*****2
发帖数: 21240 | 38
对。所以我会跟面试官说如果只是考虑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
发帖数: 1718 | 39 用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
: 这个行吗？
|
p*****2
发帖数: 21240 | 40
刚才想了一下，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
发帖数: 1718 | 41 是，好像linked list就可以了。只要从头上开始清old record就好了。
如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
，而不是用一个last。
多。
【在 p*****2 的大作中提到】
:
: 刚才想了一下，linkedlist用singly就可以了吧？貌似实现起来比array还简化了很多。
: 对没一个cell加lock的话，貌似对我的implementation作用不大呀。因为我一次性可能
: 清很多个cell。这个应该由一个thread来完成，貌似不能并行呀。
|
p*****2
发帖数: 21240 | 42
time
多谢大牛指点。
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
|
c******a
发帖数: 789 | 43 很关键的一点就是request有多频繁。我问了，说大概每秒都能request一两次，我感觉
就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？ |
p*****2
发帖数: 21240 | 44
我觉得是。
【在 c******a 的大作中提到】
: 很关键的一点就是request有多频繁。我问了，说大概每秒都能request一两次，我感觉
: 就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
: 这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？
|
c******a
发帖数: 789 | 45 每个node得是个object，有timestamp，lock加在整个list上，对不？
这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
了。list就可以。
time
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
|
p*****2
发帖数: 21240 | 46
貌似array放一年也没啥问题吧？
linkedlist如果request频繁更消耗空间。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
|
c******a
发帖数: 789 | 47 back of envelope了一下，的确1年都没问题。景仰！！
linkedlist会有些overhead是真的。
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
|
g**e
发帖数: 6127 | 48 每秒才一两次，lock随便加哪都行……
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
|
r*********n
发帖数: 4553 | 49 如果是一个月，一年，时间跨度大，可以用低resolution的array，比如两个indices之
间是1小时，当然最后答案就没有那么精确了，但是你可以求一个统计平均。一个月有
700多个小时，所以最后误差还是很小，更不要说一年了。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
|
s**x
发帖数: 7506 | |
|
|
s**********r
发帖数: 8153 | |
a**********e
发帖数: 36 | 52 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. |
x*****0
发帖数: 452 | |
c******a
发帖数: 789 | 54 赞思路，赞问的第一个问题。一定会很得面试官心。
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
发帖数: 452 | |
S******n
发帖数: 132 | 56 高并发用不用lock每个slot吧，update的时候如果有人在读，再拷贝一份好了，读到的
东西虽然old了一点，但没有什么影响，实际应用中，拷贝的次数也很少
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
|
h****p
发帖数: 87 | |
l****o
发帖数: 315 | 58 如果我理解题目没错，他只需要你最后一秒一分钟和一小时的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++;
}
} |
s********u
发帖数: 1109 | 59 没太明白用list怎么计数。是说node里面存当前1秒的数量么？然后用一个double list
，如果要计一小时，就往前数3600个node？
我在想能不能用list每个node存timestamp，然后用map来存timestamp-id的mapping，
然后两个id一减。当然，其实这个就是前面有人提到的bst了。 |
c******a
发帖数: 789 | |
|
|
h*****n
发帖数: 15 | |
p*****2
发帖数: 21240 | |
x*********w
发帖数: 533 | 63 order statistic tree
每个node按时间顺序排序，每个node保存子树个数和代表event的时间戳，一个node获
取需要lgn的复杂度。每当一个event arrive, 很快可以知道时间范围。
问题是怎么有效的清除过期节点并保持statistic tree的平衡 |
h*****a
发帖数: 1718 | 64 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
，任何超过常数时间的算法都是不可行的。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
|
p*****2
发帖数: 21240 | 65
多谢大牛confirm，循环数组O(1)就可以了。
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
|
r**h
发帖数: 1288 | 66 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
top5呢？
【在 h*****a 的大作中提到】
: 基本上实际中就是用循环数组吧。如果对于时间range内count的request非常频繁的话
: ，任何超过常数时间的算法都是不可行的。
|
r**h
发帖数: 1288 | 67 二爷能展开说说吗？如何做到O(1)找到当前top5呢
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
|
h*****a
发帖数: 1718 | 68 ft，你有什么更好的idea可以分享一下啊，这道是高频题
【在 p*****2 的大作中提到】
:
: 多谢大牛confirm，循环数组O(1)就可以了。
|
p*****2
发帖数: 21240 | 69
有说找top5吗？
【在 r**h 的大作中提到】
: 二爷能展开说说吗？如何做到O(1)找到当前top5呢
|
h*****a
发帖数: 1718 | 70 这道题问的是request的count，不需要保存数据啊。没有什么top 5啊.
【在 r**h 的大作中提到】
: 请问一下，循环数组是用来保持最近5分钟/1小时之内所有的数据吗？
: 那么每次要找出top5有没有什么比较好的方法呢？比线性搜索要快的话？
: 是每次保持并更新一个含有很多条目的histogram吗？这样如何能够有效动态的找到
: top5呢？
|
|
|
r**h
发帖数: 1288 | 71 哦，我和那一题找5分钟、1小时、24小时内的query搞混了。。不好意思啊
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
|
h*****a
发帖数: 1718 | 72 用循环数组也有tricky的地方，你写写 code试试。
【在 p*****2 的大作中提到】
:
: 有说找top5吗？
|
p*****2
发帖数: 21240 | 73
是。我能想到一些cases。一段时间没有request的话，需要把中间的都清零。
【在 h*****a 的大作中提到】
: 用循环数组也有tricky的地方，你写写 code试试。
|
p*****2
发帖数: 21240 | 74
我觉得高频题太多了，搞不过来呀。
【在 h*****a 的大作中提到】
: ft，你有什么更好的idea可以分享一下啊，这道是高频题
|
c******a
发帖数: 789 | 75 感动得暴出了泪花。当时狗急跳墙用的就是一个数组去循环，没想到给我蒙对了！！！
不过wrap around很难写bug free，我时间到了连brutal force都没写完，唉。。。。
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
|
c******a
发帖数: 789 | 76 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
然后就是2011年一次。
恰好跟室友撞了而已。
【在 p*****2 的大作中提到】
:
: 我觉得高频题太多了，搞不过来呀。
|
p*****2
发帖数: 21240 | 77
你室友怎么做的？这题在板上以前确实看到过几次。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
|
h*****a
发帖数: 1718 | 78 这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
系统，都有类似的需求。
【在 c******a 的大作中提到】
: 频率不高，我在glassdoor上愣没找到。careercup上找到最近g问的就是6／15那个贴，
: 然后就是2011年一次。
: 恰好跟室友撞了而已。
|
z*********8
发帖数: 2070 | 79 二爷能具体讲讲吗？
【在 p*****2 的大作中提到】
: 这个用个循环数组可以吗
|
p*****2
发帖数: 21240 | 80
瞎写了一个。
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
发帖数: 7583 | 81 膜拜
【在 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
发帖数: 122 | 82 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. |
r*******e
发帖数: 7583 | 83 你这个得不到严格意义上的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.
|
c******a
发帖数: 789 | 84 丫用的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;
|
r*******e
发帖数: 7583 | 85 circular buckets是正道，B+是走入歧途了
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
|
p*****2
发帖数: 21240 | 86
感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
吧？我感觉面试没有必要上来就想搞最优解。
【在 c******a 的大作中提到】
: 丫用的b＋ tree，maintain很复杂，说丫的45分钟光讲道理，没写code。
|
h*****a
发帖数: 1718 | 87 一个扩展问题是要thread safe.
【在 p*****2 的大作中提到】
:
: 感觉面试一般不会设计到复杂的数据结构，一般还是应该可以写code的，因此第一
: solution应该出自简单数据结构，即使不efficient。如果需要复杂结构面试官会引导
: 吧？我感觉面试没有必要上来就想搞最优解。
|
p*****2
发帖数: 21240 | 88
如果只是要求thread safe的话，加上synchronized keyword就可以了。
【在 h*****a 的大作中提到】
: 一个扩展问题是要thread safe.
|
g**e
发帖数: 6127 | 89 这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
时候可以做sampling然后predict
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
|
h*****a
发帖数: 1718 | 90 如果request 非常频繁的话，明显效率不高啊
【在 p*****2 的大作中提到】
:
: 如果只是要求thread safe的话，加上synchronized keyword就可以了。
|
|
|
g**e
发帖数: 6127 | 91 赞，这才是这个题真正的目的
metrics
【在 h*****a 的大作中提到】
: 这题频率不低，很多公司都问。而且这是一个很实际的问题，各公司内部都有metrics
: 系统，都有类似的需求。
|
h*****a
发帖数: 1718 | 92 难道这不是metrics/monitoring系统必须解决的实际问题么？
【在 g**e 的大作中提到】
: 这个题更多的是考设计吧，load balance然后translate time series data. 数据大的
: 时候可以做sampling然后predict
|
g**e
发帖数: 6127 | 93 是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
大的
【在 h*****a 的大作中提到】
: 难道这不是metrics/monitoring系统必须解决的实际问题么？
|
h*****a
发帖数: 1718 | 94 你说的有道理。绝对精确确实不需要，但基本精确还是要保证的，尤其是用于
monitoring的时候。
【在 g**e 的大作中提到】
: 是啊。metrics不是绝对需要100% data，数据大的时候只做sampling就行了
:
: 大的
|
p*****2
发帖数: 21240 | 95
所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
【在 h*****a 的大作中提到】
: 如果request 非常频繁的话，明显效率不高啊
|
h*****a
发帖数: 1718 | 96 hehe, 如果问你这道题的interviewer让你实现thread safe，你说你是应该主动问他是
不是我应该考虑高并发，然后给他一个支持高并发的solution，还是应该直接用
synchronized呢？虽然问题比较模糊，但事实上我觉得既然这是一个比较实际的问题，
而且用circular array的一个前提就是request比较频繁（否则完全可以用double
linked list），那高并发是理所应当的啊。
【在 p*****2 的大作中提到】
:
: 所以我说如果只是要求thread safe的话。如果要求高并发的话就不合适了。
|
p*****2
发帖数: 21240 | 97
对。所以我会跟面试官说如果只是考虑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
发帖数: 1718 | 98 用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
: 这个行吗？
|
p*****2
发帖数: 21240 | 99
刚才想了一下，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
发帖数: 1718 | 100 是，好像linked list就可以了。只要从头上开始清old record就好了。
如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
，而不是用一个last。
多。
【在 p*****2 的大作中提到】
:
: 刚才想了一下，linkedlist用singly就可以了吧？貌似实现起来比array还简化了很多。
: 对没一个cell加lock的话，貌似对我的implementation作用不大呀。因为我一次性可能
: 清很多个cell。这个应该由一个thread来完成，貌似不能并行呀。
|
|
|
p*****2
发帖数: 21240 | 101
time
多谢大牛指点。
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
|
c******a
发帖数: 789 | 102 很关键的一点就是request有多频繁。我问了，说大概每秒都能request一两次，我感觉
就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？ |
p*****2
发帖数: 21240 | 103
我觉得是。
【在 c******a 的大作中提到】
: 很关键的一点就是request有多频繁。我问了，说大概每秒都能request一两次，我感觉
: 就是一个挂在大堂的dashboard显示当前、1min、1hour的访问率。
: 这种情况下还是array好，大多情况下清掉一个old值就好了。对不对？
|
c******a
发帖数: 789 | 104 每个node得是个object，有timestamp，lock加在整个list上，对不？
这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
了。list就可以。
time
【在 h*****a 的大作中提到】
: 是，好像linked list就可以了。只要从头上开始清old record就好了。
: 如果每个cell加锁，你的implementation肯定要改了。比如每个cell keep自己的time
: ，而不是用一个last。
:
: 多。
|
p*****2
发帖数: 21240 | 105
貌似array放一年也没啥问题吧？
linkedlist如果request频繁更消耗空间。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
|
c******a
发帖数: 789 | 106 back of envelope了一下，的确1年都没问题。景仰！！
linkedlist会有些overhead是真的。
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
|
g**e
发帖数: 6127 | 107 每秒才一两次，lock随便加哪都行……
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
|
r*********n
发帖数: 4553 | 108 如果是一个月，一年，时间跨度大，可以用低resolution的array，比如两个indices之
间是1小时，当然最后答案就没有那么精确了，但是你可以求一个统计平均。一个月有
700多个小时，所以最后误差还是很小，更不要说一年了。
【在 c******a 的大作中提到】
: 每个node得是个object，有timestamp，lock加在整个list上，对不？
: 这个比array更scalable。array size 3600搞的定一小时，让搞一个月、一年就该傻掉
: 了。list就可以。
:
: time
|
s**x
发帖数: 7506 | |
s**********r
发帖数: 8153 | |
|
|
a**********e
发帖数: 36 | 111 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. |
x*****0
发帖数: 452 | |
c******a
发帖数: 789 | 113 赞思路，赞问的第一个问题。一定会很得面试官心。
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
发帖数: 452 | |
S******n
发帖数: 132 | 115 高并发用不用lock每个slot吧，update的时候如果有人在读，再拷贝一份好了，读到的
东西虽然old了一点，但没有什么影响，实际应用中，拷贝的次数也很少
【在 p*****2 的大作中提到】
:
: 貌似array放一年也没啥问题吧？
: linkedlist如果request频繁更消耗空间。
|
h****p
发帖数: 87 | |
l****o
发帖数: 315 | 117 如果我理解题目没错，他只需要你最后一秒一分钟和一小时的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++;
}
} |
s********u
发帖数: 1109 | 118 没太明白用list怎么计数。是说node里面存当前1秒的数量么？然后用一个double list
，如果要计一小时，就往前数3600个node？
我在想能不能用list每个node存timestamp，然后用map来存timestamp-id的mapping，
然后两个id一减。当然，其实这个就是前面有人提到的bst了。 |
g*****g
发帖数: 212 | 119 两部分：
1 建立counter for every second
可以用循环数组
2 建立 window （5分钟，1 小时，等等）
这个问题就是一个固定window 滑动的问题了。
可以在 O（1） 返回结果 |
g*****g
发帖数: 212 | 120 两部分：
1 建立counter for every second
可以用循环数组
2 建立 window （5分钟，1 小时，等等）
这个问题就是一个固定window 滑动的问题了。
可以在 O（1） 返回结果 |
|
|
g*****g
发帖数: 34805 | 121 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） 返回结果
|
