E*********8 发帖数: 99 | 1 刚在一亩三分地上看到别人的帖子有个题挺有意思,题是设计一个数据结构使得一个
request在1秒之内只能执行50次。
做法是用一个queue来存timestamp,每次来一个request的时候 if 50 > queueSize 直
接加到queue里 else (50 == queueSize) 把queue前面所有大于1秒的timestamp删除,
如果此时queue size小于50了再加进去. 但是这个做法面试官不满意,请问应该怎么做
呢?应该涉及到什么数据结构呢?
哪个大牛给讲讲思路?我能想到的和上面那人也差不多。 |
w***u 发帖数: 156 | 2 不知道思路对不对
假设bucket 里面有50个token,每秒都会填满bucket,每个reguest需要先拿到token,
service才会执行这个request。 |
G**O 发帖数: 147 | 3 哈哈,这就是标准的rate limiter
【在 w***u 的大作中提到】 : 不知道思路对不对 : 假设bucket 里面有50个token,每秒都会填满bucket,每个reguest需要先拿到token, : service才会执行这个request。
|
d****n 发帖数: 12461 | 4 这个token怎么拿到?假设有10个用户要1个token,怎么给?还是说是assign的?
【在 w***u 的大作中提到】 : 不知道思路对不对 : 假设bucket 里面有50个token,每秒都会填满bucket,每个reguest需要先拿到token, : service才会执行这个request。
|
M**********l 发帖数: 68 | |
b***s 发帖数: 117 | 6 我觉得可以稍微修改一下
每个request进来,只需要判断queue里最头的request是不是在一秒之内就可以了
如果是,新的request fail
不是,删掉最老的,添加新的
每个request是 O(1)
当然,最外面是 Map
【在 E*********8 的大作中提到】 : 刚在一亩三分地上看到别人的帖子有个题挺有意思,题是设计一个数据结构使得一个 : request在1秒之内只能执行50次。 : 做法是用一个queue来存timestamp,每次来一个request的时候 if 50 > queueSize 直 : 接加到queue里 else (50 == queueSize) 把queue前面所有大于1秒的timestamp删除, : 如果此时queue size小于50了再加进去. 但是这个做法面试官不满意,请问应该怎么做 : 呢?应该涉及到什么数据结构呢? : 哪个大牛给讲讲思路?我能想到的和上面那人也差不多。
|
o*******r 发帖数: 73 | 7 小白抛砖引玉一下。
public class Solution {
private long lastTime = System.currentTimeMillis();
private int limitPerSecond;
private int remains = limitPerSecond;
public Solution(int permitsPerSecond) {
this.limitPerSecond = permitsPerSecond;
}
public boolean acquire() {
long curTime = System.currentTimeMillis();
double timeEplaseInSec = (curTime - lastTime) / 1000.0;
lastTime = curTime;
remains += (int)(timeEplaseInSec * limitPerSecond);
if (remains > limitPerSecond) {
remains = limitPerSecond;
}
if (remains < 1) return false;
else {
remains -= 1;
return true;
}
}
public static void main(String[] args) {
Solution limiter = new Solution(50);
while (true) {
if (limiter.acquire()) {
// Do something
} else {
// wait...
}
}
}
} |
i***h 发帖数: 12655 | 8 去年有个相同主题你找找
我以为有人挖坟呢
【在 E*********8 的大作中提到】 : 刚在一亩三分地上看到别人的帖子有个题挺有意思,题是设计一个数据结构使得一个 : request在1秒之内只能执行50次。 : 做法是用一个queue来存timestamp,每次来一个request的时候 if 50 > queueSize 直 : 接加到queue里 else (50 == queueSize) 把queue前面所有大于1秒的timestamp删除, : 如果此时queue size小于50了再加进去. 但是这个做法面试官不满意,请问应该怎么做 : 呢?应该涉及到什么数据结构呢? : 哪个大牛给讲讲思路?我能想到的和上面那人也差不多。
|
E*********8 发帖数: 99 | 9 搜到了,原来已经有人在这里讨论过了,谢谢啊
【在 i***h 的大作中提到】 : 去年有个相同主题你找找 : 我以为有人挖坟呢
|