Redian新闻
>
Re: 和公司老员工聊天,感叹多数人没有过贫困线 (转载)
avatar
Re: 和公司老员工聊天,感叹多数人没有过贫困线 (转载)# Joke - 肚皮舞运动
a*d
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);
各位大神能给点好的思路不?
谢谢
avatar
r*g
2
【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: Re: 和公司老员工聊天,感叹多数人没有过贫困线
发信站: BBS 未名空间站 (Mon Sep 16 18:09:35 2013, 美东)
草你大爷 快来补充说你LP很丑, 不然这里WSN都羡慕的失去活下去的意义了.
avatar
w*t
3
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时,若只有单独一个分隔符,直接分割,若有两个或以上的连续分隔符,去掉一
个保留一个,再继续处理后面的字符串。。。
avatar
M*e
4
虽然很好笑,可我笑不出来。

【在 r*******g 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: Re: 和公司老员工聊天,感叹多数人没有过贫困线
: 发信站: BBS 未名空间站 (Mon Sep 16 18:09:35 2013, 美东)
: 草你大爷 快来补充说你LP很丑, 不然这里WSN都羡慕的失去活下去的意义了.

avatar
m*g
5
RateLimit是否可以用token bucket 来实现, 一个timer thread定期添加token, 一个
请求消耗一个token, bucket 为空时reject request. 也可以用类似select()的
function实现timer 与demultiplex.
avatar
d*f
6
我比较关心他老婆的id

【在 r*******g 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: Re: 和公司老员工聊天,感叹多数人没有过贫困线
: 发信站: BBS 未名空间站 (Mon Sep 16 18:09:35 2013, 美东)
: 草你大爷 快来补充说你LP很丑, 不然这里WSN都羡慕的失去活下去的意义了.

avatar
g*g
7
可以用queue(也可以循环数组实现),每个元素是当前时间戳
每次request,从队头remove超时的
比较size, 如果超过qps return false
否则,入队,return true
avatar
m*n
8
退休做什么? 做慈善的话, 860万的确不多。
avatar
a*d
9
我用了个list,每次binary search 当前时间减1秒之内之前的request,返回那个
index看和list尾部距离
avatar
c*r
10
这种给joke版添堵的帖子应格杀勿论
avatar
l*6
11
first question has to deal with multithread
avatar
M*9
12
嗯, 同意, 哈哈

【在 c*******r 的大作中提到】
: 这种给joke版添堵的帖子应格杀勿论
avatar
l*d
13
2) 每个 string 前面加上其长度?
例如,["have","a","good","day"] <=> "4have1a4good3day"
avatar
c*i
14
还好啦,也就是帝都5-10套房产。国内有些根基的达到这种水平不少。
avatar
S*A
15
这个是不对的,因为你的time thread 只加不减。
因为可以出现这样情况,前面10 秒钟一个 request 没有,然后后面
一秒钟 burst 5 倍 rate limit, 你的算法就全部批准了。

【在 m**********g 的大作中提到】
: RateLimit是否可以用token bucket 来实现, 一个timer thread定期添加token, 一个
: 请求消耗一个token, bucket 为空时reject request. 也可以用类似select()的
: function实现timer 与demultiplex.

avatar
M*e
16
不堵不堵
我们吃得健康,通畅的很

【在 c*******r 的大作中提到】
: 这种给joke版添堵的帖子应格杀勿论
avatar
g*e
17
标准答案 http://en.wikipedia.org/wiki/Leaky_bucket

一个

【在 S*A 的大作中提到】
: 这个是不对的,因为你的time thread 只加不减。
: 因为可以出现这样情况,前面10 秒钟一个 request 没有,然后后面
: 一秒钟 burst 5 倍 rate limit, 你的算法就全部批准了。

avatar
d*l
18
搜搜非死不可主人老婆的照片,不难。

【在 r*******g 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: Re: 和公司老员工聊天,感叹多数人没有过贫困线
: 发信站: BBS 未名空间站 (Mon Sep 16 18:09:35 2013, 美东)
: 草你大爷 快来补充说你LP很丑, 不然这里WSN都羡慕的失去活下去的意义了.

avatar
r*g
19
难道不是简单的把前个request到来的时间保存,下一个来的request的时间减去前个时
间,时间差小于1秒就return false?
avatar
g*e
20
都没上过computer networks的课没读过Andrew Tanenbaum的书?

【在 r******g 的大作中提到】
: 难道不是简单的把前个request到来的时间保存,下一个来的request的时间减去前个时
: 间,时间差小于1秒就return false?

avatar
G*n
21
请问 如果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#"

avatar
P*f
22

请问如何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#"

avatar
w*t
23
list怎么做binary search呢?

【在 a**d 的大作中提到】
: 我用了个list,每次binary search 当前时间减1秒之内之前的request,返回那个
: index看和list尾部距离

avatar
w*t
24
如果原始串里面出现了数字,这个就不work了
"4have" --> "54have"

【在 l*********d 的大作中提到】
: 2) 每个 string 前面加上其长度?
: 例如,["have","a","good","day"] <=> "4have1a4good3day"

avatar
w*t
25
这个case确实不work了
另外想到了一个解法:
第一个字符:一个数字表示(1-9),表示字符串长度有多少位
接下来的1-9个字符,就是字符串的长度
最后是字符串
如 "abcde" --> "15abcde"
"12abc" --> "1512abc"
"123456789abc" --> "212123456789abc"

【在 P*****f 的大作中提到】
:
: 请问如何decode "a###b#" ? 是 ["a" ,"#b"]呢还是["a#", "b"]?

avatar
a*d
26
他提示用escape //n这样。。没太懂
avatar
b*m
27
第二题:
先输出list.size(),然后循环:
DataOutputStream.writeUTF
这样算cheat?
avatar
d*e
28
第二题版上以前有同学给过答案,好像说这题是密码学里比较简单的。
跟前面有位同学说的差不多,在每个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

avatar
d*e
29
我面的时候就用escape,虽然也可行,但面试官明确说这不是好的解法。

【在 a**d 的大作中提到】
: 他提示用escape //n这样。。没太懂
avatar
g*i
30
没学过网络,大牛可以展开讲讲这个漏桶算法怎么用在第一题里吗?谢谢!

【在 g**e 的大作中提到】
: 标准答案 http://en.wikipedia.org/wiki/Leaky_bucket
:
: 一个

avatar
k*o
31
mark
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。