G面试题求解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G面试题求解

G面试题求解# JobHunting - 待字闺中

E*82017-04-09 07:04

1 楼

刚在一亩三分地上看到别人的帖子有个题挺有意思，题是设计一个数据结构使得一个
request在1秒之内只能执行50次。
做法是用一个queue来存timestamp，每次来一个request的时候 if 50 > queueSize 直
接加到queue里 else (50 == queueSize) 把queue前面所有大于1秒的timestamp删除，
如果此时queue size小于50了再加进去. 但是这个做法面试官不满意，请问应该怎么做
呢？应该涉及到什么数据结构呢？
哪个大牛给讲讲思路？我能想到的和上面那人也差不多。

w*u2017-04-09 07:04

2 楼

不知道思路对不对
假设bucket 里面有50个token，每秒都会填满bucket，每个reguest需要先拿到token，
service才会执行这个request。

G*O2017-04-09 07:04

3 楼

哈哈，这就是标准的rate limiter

【在 w***u 的大作中提到】

: 不知道思路对不对
: 假设bucket 里面有50个token，每秒都会填满bucket，每个reguest需要先拿到token，
: service才会执行这个request。

d*n2017-04-09 07:04

4 楼

这个token怎么拿到？假设有10个用户要1个token，怎么给？还是说是assign的？

【在 w***u 的大作中提到】

: 不知道思路对不对
: 假设bucket 里面有50个token，每秒都会填满bucket，每个reguest需要先拿到token，
: service才会执行这个request。

M*l2017-04-09 07:04

5 楼

L 359

b*s2017-04-09 07:04

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*r2017-04-09 07:04

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...
}
}
}
}