l********o
发帖数: 56 | 1 这个问题我被问过3次，3个不同的公司，其中第一次遇到是在google。
设计一个数据结构使得一个request在1秒之内只能执行50次。
我的做法是用一个queue来存timestamp，每次来一个request的时候 if 50 >
queueSize 直接加到queue里 else (50 == queueSize) 把queue前面所有大于1秒的
timestamp删除，如果此时queue size小于50了再加进去.
面试官很不满意，说复杂度太高。面试结束的时候问他到底怎么样才最优，他说是
secret。 |
S********t
发帖数: 3431 | 2 guava RateLimiter
【在 l********o 的大作中提到】
: 这个问题我被问过3次，3个不同的公司，其中第一次遇到是在google。
: 设计一个数据结构使得一个request在1秒之内只能执行50次。
: 我的做法是用一个queue来存timestamp，每次来一个request的时候 if 50 >
: queueSize 直接加到queue里 else (50 == queueSize) 把queue前面所有大于1秒的
: timestamp删除，如果此时queue size小于50了再加进去.
: 面试官很不满意，说复杂度太高。面试结束的时候问他到底怎么样才最优，他说是
: secret。
|
l*******g
发帖数: 84 | 3 我想了一下。
这里好像不用复杂的数据结构。开一个50个元素的数组。两个指针，一个是头指针，一
个是尾指针
。移动头指针到 当前时间-1 秒。如果头指针和尾指针重合，说明有50次了，放弃。如
果没有的话，插入到尾指针。如果尾指针到了数组的末了话，把尾指针移到数组的头，
作一个循环数组。
数组里面存的是Request 的时间，不知道Request是不是唯一的，如果每次的Request不
一样这种做法就不行了。
个人意见，请指正。 |
l********o
发帖数: 56 | 4 request是唯一的。感觉这个做法是不是就相当于用array实现了queue？
面试官提示说如果要支持request limit为1million的话，用任何数据结构存timestamp
都会导致占用内存。他想要O(1)空间复杂度的解法。我想了很久都没有想到。。
【在 l*******g 的大作中提到】
: 我想了一下。
: 这里好像不用复杂的数据结构。开一个50个元素的数组。两个指针，一个是头指针，一
: 个是尾指针
: 。移动头指针到 当前时间-1 秒。如果头指针和尾指针重合，说明有50次了，放弃。如
: 果没有的话，插入到尾指针。如果尾指针到了数组的末了话，把尾指针移到数组的头，
: 作一个循环数组。
: 数组里面存的是Request 的时间，不知道Request是不是唯一的，如果每次的Request不
: 一样这种做法就不行了。
: 个人意见，请指正。
|
r*******y
发帖数: 270 | 5 这题不需要开array或者queue，只要维护counter和last seconds就可以了，确实是O(1
)的。 |
l********o
发帖数: 56 | 6 来说说怎么做？
(1
【在 r*******y 的大作中提到】
: 这题不需要开array或者queue，只要维护counter和last seconds就可以了，确实是O(1
: )的。
|
r*********r
发帖数: 53 | |
l***4
发帖数: 1788 | 8 leaky bucket
【在 l********o 的大作中提到】
: 来说说怎么做？
:
: (1
|
l********o
发帖数: 56 | 9 看了一下leaky bucket的定义。对于这道题来说关键在于怎么控制overflow的触发条件
是吧，感觉还是得用queue啊
【在 l***4 的大作中提到】
: leaky bucket
|
j**********3
发帖数: 3211 | |
|
|
l********o
发帖数: 56 | 11 我自己觉得是Google的面试官搞错了。。这题要是想做到精确控制就得用数据结构存
timestamp。。拜托大家帮忙想一想，谢啦！ |
p**********8
发帖数: 7 | 12 这面试官想考算法还是concurrency？后者就往lock, thread上去想。另外，你的题目
也很模糊. |
S********t
发帖数: 3431 | 13 guava RateLimiter要我说几遍啊 |
t******i
发帖数: 483 | 14 1.一个计数器Counter，取值0-50
2.Counter每1/50秒自增1，如果超过50则保持50不变
3，if 新的request 进来，如果counter >0, Counter--,执行这个request;
如果Counter == 0,不自减，这个request丢弃，也就是不执行这个request
大概就是这么个意思。欢迎批评指正。 |
d********y
发帖数: 93 | 15 欢迎加入Slack讨论组：GoogleOffer和dietpepsi等大神一起讨论
填写你的邮箱后，我把你拉进去：https://docs.google.com/forms/d/
1l29Ucpo4Fnle7T-_UZbwC2-lMEaPKeSeBATiKpSlZwM/viewform
或者可以加微信群： |
h****n
发帖数: 1093 | 16 正解 就是leaky bucket
【在 t******i 的大作中提到】
: 1.一个计数器Counter，取值0-50
: 2.Counter每1/50秒自增1，如果超过50则保持50不变
: 3，if 新的request 进来，如果counter >0, Counter--,执行这个request;
: 如果Counter == 0,不自减，这个request丢弃，也就是不执行这个request
: 大概就是这么个意思。欢迎批评指正。
|
S********t
发帖数: 3431 | 17 secret个屁，Google自己给开源的Guava摆在那儿
【在 l********o 的大作中提到】
: 这个问题我被问过3次，3个不同的公司，其中第一次遇到是在google。
: 设计一个数据结构使得一个request在1秒之内只能执行50次。
: 我的做法是用一个queue来存timestamp，每次来一个request的时候 if 50 >
: queueSize 直接加到queue里 else (50 == queueSize) 把queue前面所有大于1秒的
: timestamp删除，如果此时queue size小于50了再加进去.
: 面试官很不满意，说复杂度太高。面试结束的时候问他到底怎么样才最优，他说是
: secret。
|
I*******y
发帖数: 4893 | 18 50个request在第一个1/50秒进来，后面49/50秒没有request。你这个岂不是只执行一次
【在 t******i 的大作中提到】
: 1.一个计数器Counter，取值0-50
: 2.Counter每1/50秒自增1，如果超过50则保持50不变
: 3，if 新的request 进来，如果counter >0, Counter--,执行这个request;
: 如果Counter == 0,不自减，这个request丢弃，也就是不执行这个request
: 大概就是这么个意思。欢迎批评指正。
|
l*********g
发帖数: 107 | 19
t : counter = 50
t~t+1/50), 50 requests come in, counter --> 0
t+1/50 counter = 1
it will process more than 50 requests within 1 seconds
【在 t******i 的大作中提到】
: 1.一个计数器Counter，取值0-50
: 2.Counter每1/50秒自增1，如果超过50则保持50不变
: 3，if 新的request 进来，如果counter >0, Counter--,执行这个request;
: 如果Counter == 0,不自减，这个request丢弃，也就是不执行这个request
: 大概就是这么个意思。欢迎批评指正。
|
h****n
发帖数: 1093 | 20 counter初值0 就ok了
【在 l*********g 的大作中提到】
:
: t : counter = 50
: t~t+1/50), 50 requests come in, counter --> 0
: t+1/50 counter = 1
: it will process more than 50 requests within 1 seconds
|
|
|
h****n
发帖数: 1093 | 21 题目只要求限制任何一秒内最多不能超过50个吧 这个到下一秒就处理50个了 长期来
看平均还是每秒50个左右
一次
【在 I*******y 的大作中提到】
: 50个request在第一个1/50秒进来，后面49/50秒没有request。你这个岂不是只执行一次
|
j*********n
发帖数: 74 | |
c*******i
发帖数: 135 | 23 Request 在一秒内超过50要丢弃还是存起来不执行？ |
s******3
发帖数: 344 | 24 re
【在 t******i 的大作中提到】
: 1.一个计数器Counter，取值0-50
: 2.Counter每1/50秒自增1，如果超过50则保持50不变
: 3，if 新的request 进来，如果counter >0, Counter--,执行这个request;
: 如果Counter == 0,不自减，这个request丢弃，也就是不执行这个request
: 大概就是这么个意思。欢迎批评指正。
|
h***n
发帖数: 1600 | 25 +1
【在 S********t 的大作中提到】
: guava RateLimiter要我说几遍啊
|
h**********0
发帖数: 88 | 26 use one token to send each request, 然后limit token release limit per minute
as
rate_perSecond = 3000/60
也就是50 tokens per second |
l*********w
发帖数: 472 | 27 我不太理解你的这个方法。请问我下面的理解对吗？
等到counter==50的时候在0.02 s内发送50个request，counter归零了，等到0.50s的时
候counter变成24，再发送24个request。那么在0.5s内一共执行了75个request。
【在 t******i 的大作中提到】
: 1.一个计数器Counter，取值0-50
: 2.Counter每1/50秒自增1，如果超过50则保持50不变
: 3，if 新的request 进来，如果counter >0, Counter--,执行这个request;
: 如果Counter == 0,不自减，这个request丢弃，也就是不执行这个request
: 大概就是这么个意思。欢迎批评指正。
|
I*******y
发帖数: 4893 | 28 那我先给你一秒没有任何request，counter不就变成50了，再来一个楼上的情境，不就
超了。
【在 h****n 的大作中提到】
: counter初值0 就ok了
|
I*******y
发帖数: 4893 | 29 你咋不说我直接decline所有的request，那永远也不超过50个
【在 h****n 的大作中提到】
: 题目只要求限制任何一秒内最多不能超过50个吧 这个到下一秒就处理50个了 长期来
: 看平均还是每秒50个左右
:
: 一次
|
h****n
发帖数: 1093 | 30 这哪能一样 一个长期平均来看还是50次每秒 跟
完全decline两码事 另外你上面说的那个有点死板了 看怎么定义秒的起始了 如果题目
要求的是从任何时间点算起下一秒的数量不超过50 那么我相信你是找不出什么完美的
解法的 比如你的解法任意整数秒内不超50 但是比如0.5秒到1.5秒就会超了 换一种角
度去理解秒的起始就好了 token bucket 假设初始值0 一秒内没request到50，然后0.
02秒来了50个request清0 到2秒的时候基本上一共处理了99个request 平均每秒50个
有啥问题？这个和另外一种情况 比如 0.5秒没request 0.5秒到1秒处理了50个req，1
到1.5秒内处理了49个 1.5秒到两秒处理了1个req有啥本质区别？？把秒的起始指做个0
.5秒offset没有任何区别 rate limiter能保证长期以来一秒内平均都不超过50 而且
是各种网络协议 通信标准做速率控制的标准做法了
【在 I*******y 的大作中提到】
: 你咋不说我直接decline所有的request，那永远也不超过50个
|
|
|
y***g
发帖数: 1492 | 31 Ratelimiter 最简单的实现map就搞定了 做range query |
w****e
发帖数: 586 | 32 就是经典的token bucket啊，只要存两个数，一个是上次request的timestamp，一个是
当前的token数（浮点数）。
初始化token为50（或者0，取决于面试官要求），上次request的timestamp为开始时间
每次request进来，先用当前时间和上次request时间计算该加多少token，即(
timestamp_now - timestamp_last) * 50, 并且保证token数capped by 50
然后只要token数>=1，就允许这次操作，并token减去1
最后timestamp_last = timestamp_now
一共没几行code，O(1)，没有request也不需要弄个timer在那计时加token，反正下个
request进来的时候会先补token |
l*********g
发帖数: 107 | 33 there is a time t: token: 50 (or 49)
at time t~ t+0.001, 50 (or 49) requests come in, consumed all tokens
timestamp_last = t + 0.001
at time t + 0.101, another request comes in, you have another 5 tokens
...
you will process more than 50 requests within 1 second
does not work
【在 w****e 的大作中提到】
: 就是经典的token bucket啊，只要存两个数，一个是上次request的timestamp，一个是
: 当前的token数（浮点数）。
: 初始化token为50（或者0，取决于面试官要求），上次request的timestamp为开始时间
: 每次request进来，先用当前时间和上次request时间计算该加多少token，即(
: timestamp_now - timestamp_last) * 50, 并且保证token数capped by 50
: 然后只要token数>=1，就允许这次操作，并token减去1
: 最后timestamp_last = timestamp_now
: 一共没几行code，O(1)，没有request也不需要弄个timer在那计时加token，反正下个
: request进来的时候会先补token
|
w****e
发帖数: 586 | 34 这个就取决于题目怎么定义了。实际工程中这是比较标准的做法，保证的是平均意义上
的。
要确切保证任意一个一秒的window内的request数，可以多开个线程负责加token。接
request的线程signal加token的线程，而后者维护一个request timestamp的list并根
据这个控制sleep的时间
最后time complexity还是O(1), space是50
【在 l*********g 的大作中提到】
: there is a time t: token: 50 (or 49)
: at time t~ t+0.001, 50 (or 49) requests come in, consumed all tokens
: timestamp_last = t + 0.001
: at time t + 0.101, another request comes in, you have another 5 tokens
: ...
: you will process more than 50 requests within 1 second
: does not work
|
A***g
发帖数: 1816 | 35 从数学角度讲，如果要求严格任意一秒钟内，比如4:14:13.05 到 4:14:14.05之间都不
能超过50个，那么不记录request的时间是不可能的啊，否则拿掉超过一秒的最老的
request之后，怎么才能知道这剩下的已经有的request是什么时间的？
timestamp
【在 l********o 的大作中提到】
: request是唯一的。感觉这个做法是不是就相当于用array实现了queue？
: 面试官提示说如果要支持request limit为1million的话，用任何数据结构存timestamp
: 都会导致占用内存。他想要O(1)空间复杂度的解法。我想了很久都没有想到。。
|
p**********i
发帖数: 276 | 36 同感，任意1s滑动窗口而且要跑满50/s，肯定需要记录每一个Request时间。
如果不要求1s滑动窗口，bucket之类的应该比较合适，而且一个变量就够啦。
每个request应该在上一个request后，等1/50才进入。这样正好每秒50个。如果有一个
request太快了，等了1/100就进入了，那它就用掉后面request的1/100时间。
总的bucket计为-1/100，这样过一段时间强制把bucket清零。是不是也可以？
【在 A***g 的大作中提到】
: 从数学角度讲，如果要求严格任意一秒钟内，比如4:14:13.05 到 4:14:14.05之间都不
: 能超过50个，那么不记录request的时间是不可能的啊，否则拿掉超过一秒的最老的
: request之后，怎么才能知道这剩下的已经有的request是什么时间的？
:
: timestamp
|
s*******u
发帖数: 692 | 37 按你这个办法， 头1/50秒 来了个一万个request, 后49/50 秒 一个request也没来
你这个service 就是死的 一个request 也不serve.
【在 t******i 的大作中提到】
: 1.一个计数器Counter，取值0-50
: 2.Counter每1/50秒自增1，如果超过50则保持50不变
: 3，if 新的request 进来，如果counter >0, Counter--,执行这个request;
: 如果Counter == 0,不自减，这个request丢弃，也就是不执行这个request
: 大概就是这么个意思。欢迎批评指正。
|
I*******y
发帖数: 4893 | 38 题目明明说的就是一秒内不超过50啊，并没有说平均。没有完美解法说明题出错了。。
0.
1
个0
【在 h****n 的大作中提到】
: 这哪能一样 一个长期平均来看还是50次每秒 跟
: 完全decline两码事 另外你上面说的那个有点死板了 看怎么定义秒的起始了 如果题目
: 要求的是从任何时间点算起下一秒的数量不超过50 那么我相信你是找不出什么完美的
: 解法的 比如你的解法任意整数秒内不超50 但是比如0.5秒到1.5秒就会超了 换一种角
: 度去理解秒的起始就好了 token bucket 假设初始值0 一秒内没request到50，然后0.
: 02秒来了50个request清0 到2秒的时候基本上一共处理了99个request 平均每秒50个
: 有啥问题？这个和另外一种情况 比如 0.5秒没request 0.5秒到1秒处理了50个req，1
: 到1.5秒内处理了49个 1.5秒到两秒处理了1个req有啥本质区别？？把秒的起始指做个0
: .5秒offset没有任何区别 rate limiter能保证长期以来一秒内平均都不超过50 而且
: 是各种网络协议 通信标准做速率控制的标准做法了
|
