a**d 发帖数: 85 | 1 肯定跪了。
interface RateLimit {
/** Sets the rate, from 1 to 1000000 queries per second */
void setQPS(int qps);
/** accept or reject a request, called when request is received */
boolean allowThisRequest();
}
brief example:
server instantiates your object, calls setQPS(1)
at at time t, user1 makes a request, allowThisRequest() returns true
at time t+0.01 sec, user2 makes a request, allowThisRequest() returns false
at at time t+1, user4 makes a request, allowThisRequest() returns true
at time t+5 sec, user3 makes a request, allowThisRequest() returns true
写个class implement这个接口
String encode(List input);
List decode(String input);
各位大神能给点好的思路不?
谢谢 |
w*****t 发帖数: 485 | 2 1) RateLimit大体思路:
use window rolling, 用一个队列,保存request的请求时间
新来一个请求时,先根据当前时间(如 123.45),减去1秒(122.45), 然后将队列头部所
有小于122.45的request出队,再判断队列长度是否还小于qps,是的话插入新的
request,并返回true,否则返回false。
2) encode/decode:
用一个任意的字符来分割list, 比如用'#',如果原string中有该分隔符,就
double一个,
比如:"abc,de#,hij" -> "abc#de###hij#"
"abc,d#f,hij" -> "abc#d##f#hij#"
decode时,若只有单独一个分隔符,直接分割,若有两个或以上的连续分隔符,去掉一
个保留一个,再继续处理后面的字符串。。。 |
m**********g 发帖数: 153 | 3 RateLimit是否可以用token bucket 来实现, 一个timer thread定期添加token, 一个
请求消耗一个token, bucket 为空时reject request. 也可以用类似select()的
function实现timer 与demultiplex. |
g*****g 发帖数: 212 | 4 可以用queue(也可以循环数组实现),每个元素是当前时间戳
每次request,从队头remove超时的
比较size, 如果超过qps return false
否则,入队,return true |
a**d 发帖数: 85 | 5 我用了个list,每次binary search 当前时间减1秒之内之前的request,返回那个
index看和list尾部距离 |
l******6 发帖数: 340 | 6 first question has to deal with multithread |
l*********d 发帖数: 78 | 7 2) 每个 string 前面加上其长度?
例如,["have","a","good","day"] <=> "4have1a4good3day" |
S*A 发帖数: 7142 | 8 这个是不对的,因为你的time thread 只加不减。
因为可以出现这样情况,前面10 秒钟一个 request 没有,然后后面
一秒钟 burst 5 倍 rate limit, 你的算法就全部批准了。
【在 m**********g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : RateLimit是否可以用token bucket 来实现, 一个timer thread定期添加token, 一个 : 请求消耗一个token, bucket 为空时reject request. 也可以用类似select()的 : function实现timer 与demultiplex.
|
g**e 发帖数: 6127 | 9 标准答案 http://en.wikipedia.org/wiki/Leaky_bucket
一个
【在 S*A 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个是不对的,因为你的time thread 只加不减。 : 因为可以出现这样情况,前面10 秒钟一个 request 没有,然后后面 : 一秒钟 burst 5 倍 rate limit, 你的算法就全部批准了。
|
r******g 发帖数: 138 | 10 难道不是简单的把前个request到来的时间保存,下一个来的request的时间减去前个时
间,时间差小于1秒就return false? |
|
|
g**e 发帖数: 6127 | 11 都没上过computer networks的课没读过Andrew Tanenbaum的书?
【在 r******g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道不是简单的把前个request到来的时间保存,下一个来的request的时间减去前个时 : 间,时间差小于1秒就return false?
|
G*****n 发帖数: 19 | 12 请问 如果rate 很高时, 将队列头部逐个出列 不是很费时吗?这样会造成rate不准...
【在 w*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1) RateLimit大体思路: : use window rolling, 用一个队列,保存request的请求时间 : 新来一个请求时,先根据当前时间(如 123.45),减去1秒(122.45), 然后将队列头部所 : 有小于122.45的request出队,再判断队列长度是否还小于qps,是的话插入新的 : request,并返回true,否则返回false。 : 2) encode/decode: : 用一个任意的字符来分割list, 比如用'#',如果原string中有该分隔符,就 : double一个, : 比如:"abc,de#,hij" -> "abc#de###hij#" : "abc,d#f,hij" -> "abc#d##f#hij#"
|
P*****f 发帖数: 2272 | 13
请问如何decode "a###b#" ? 是 ["a" ,"#b"]呢还是["a#", "b"]?
【在 w*****t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 1) RateLimit大体思路: : use window rolling, 用一个队列,保存request的请求时间 : 新来一个请求时,先根据当前时间(如 123.45),减去1秒(122.45), 然后将队列头部所 : 有小于122.45的request出队,再判断队列长度是否还小于qps,是的话插入新的 : request,并返回true,否则返回false。 : 2) encode/decode: : 用一个任意的字符来分割list, 比如用'#',如果原string中有该分隔符,就 : double一个, : 比如:"abc,de#,hij" -> "abc#de###hij#" : "abc,d#f,hij" -> "abc#d##f#hij#"
|
w*****t 发帖数: 485 | 14 list怎么做binary search呢?
【在 a**d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我用了个list,每次binary search 当前时间减1秒之内之前的request,返回那个 : index看和list尾部距离
|
w*****t 发帖数: 485 | 15 如果原始串里面出现了数字,这个就不work了
"4have" --> "54have"
【在 l*********d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2) 每个 string 前面加上其长度? : 例如,["have","a","good","day"] <=> "4have1a4good3day"
|
w*****t 发帖数: 485 | 16 这个case确实不work了
另外想到了一个解法:
第一个字符:一个数字表示(1-9),表示字符串长度有多少位
接下来的1-9个字符,就是字符串的长度
最后是字符串
如 "abcde" --> "15abcde"
"12abc" --> "1512abc"
"123456789abc" --> "212123456789abc"
【在 P*****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 请问如何decode "a###b#" ? 是 ["a" ,"#b"]呢还是["a#", "b"]?
|
a**d 发帖数: 85 | |
b**m 发帖数: 1466 | 18 第二题:
先输出list.size(),然后循环:
DataOutputStream.writeUTF
这样算cheat? |
d**e 发帖数: 6098 | 19 第二题版上以前有同学给过答案,好像说这题是密码学里比较简单的。
跟前面有位同学说的差不多,在每个string加一个header标记,比如是
H{string1_length}S{string1}H{string2_length}S{string2}.....
decode的时候就先看H,然后length,然后是S之后的字符开始取string。
【在 a**d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 肯定跪了。 : interface RateLimit { : /** Sets the rate, from 1 to 1000000 queries per second */ : void setQPS(int qps); : /** accept or reject a request, called when request is received */ : boolean allowThisRequest(); : } : brief example: : server instantiates your object, calls setQPS(1) : at at time t, user1 makes a request, allowThisRequest() returns true
|
d**e 发帖数: 6098 | 20 我面的时候就用escape,虽然也可行,但面试官明确说这不是好的解法。
【在 a**d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 他提示用escape //n这样。。没太懂
|
g*****i 发帖数: 91 | 21 没学过网络,大牛可以展开讲讲这个漏桶算法怎么用在第一题里吗?谢谢!
【在 g**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 标准答案 http://en.wikipedia.org/wiki/Leaky_bucket : : 一个
|
k*****o 发帖数: 43 | |