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 的大作中提到】
: 去年有个相同主题你找找
: 我以为有人挖坟呢
|
