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 的大作中提到】
: 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 的大作中提到】
: 这个是不对的，因为你的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 的大作中提到】
: 难道不是简单的把前个request到来的时间保存，下一个来的request的时间减去前个时
: 间，时间差小于1秒就return false？
|
G*****n
发帖数: 19 | 12 请问 如果rate 很高时, 将队列头部逐个出列 不是很费时吗？这样会造成rate不准...
【在 w*****t 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 我用了个list，每次binary search 当前时间减1秒之内之前的request，返回那个
: index看和list尾部距离
|
w*****t
发帖数: 485 | 15 如果原始串里面出现了数字，这个就不work了
"4have" --> "54have"
【在 l*********d 的大作中提到】
: 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 的大作中提到】
:
: 请问如何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 的大作中提到】
: 肯定跪了。
: 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 的大作中提到】
: 他提示用escape //n这样。。没太懂
|
g*****i
发帖数: 91 | 21 没学过网络，大牛可以展开讲讲这个漏桶算法怎么用在第一题里吗？谢谢！
【在 g**e 的大作中提到】
: 标准答案 http://en.wikipedia.org/wiki/Leaky_bucket
:
: 一个
|
k*****o
发帖数: 43 | |
