刚收到短信通知 485 RFE TSC，求祝福, 谢谢大家 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>EB23 - 劳工卡

刚收到短信通知 485 RFE TSC，求祝福, 谢谢大家

刚收到短信通知 485 RFE TSC，求祝福, 谢谢大家# EB23 - 劳工卡

j*42017-08-08 07:08

1 楼

估计挂了，有一题基本不知道怎么解。
设计一个function: bool cancall(), 保证每秒钟内return true的数量小于 N,
想了两个办法，
a)写个queue, 每次 call 把 request time放到queue 里面，dequeue 1秒以前的
request.然后看queue的size..没效率，被否。
b)每秒一个bucket,然后保证当前bucket,的count小于N/2,不精确，被否。
然后就没时间了，这个怎么搞，到底？提示是"keep track of available count
instead... "
面试管好像说是一个XXX algorithm,在network里面用的。有人听着耳熟么？我是不是
被黑了。

l*l2017-08-08 07:08

2 楼

顺便问一下高人，RFE是不是意味着背景调查已经结束并通过了？

B*g2017-08-08 07:08

3 楼

难道不是设个count，每次减1，<0就false，每秒reset count back to N

【在 j*****4 的大作中提到】

: 估计挂了，有一题基本不知道怎么解。
: 设计一个function: bool cancall(), 保证每秒钟内return true的数量小于 N,
: 想了两个办法，
: a)写个queue, 每次 call 把 request time放到queue 里面，dequeue 1秒以前的
: request.然后看queue的size..没效率，被否。
: b)每秒一个bucket,然后保证当前bucket,的count小于N/2,不精确，被否。
: 然后就没时间了，这个怎么搞，到底？提示是"keep track of available count
: instead... "
: 面试管好像说是一个XXX algorithm,在network里面用的。有人听着耳熟么？我是不是
: 被黑了。

p*e2017-08-08 07:08

4 楼

你是寄出RRFE，还是等着收到RFE?
我RRFE都半个月了，TSC还没消息。

t*t2017-08-08 07:08

5 楼

a list of size N, store the time of last N true calls
when new call, throw element out from head of list until the time is 1
second from current time. if list is full, return false, else if return true
, store it at end of list, if return false, do nothing

【在 j*****4 的大作中提到】

l*l2017-08-08 07:08

6 楼

在等正式的RFE信

【在 p*******e 的大作中提到】

: 你是寄出RRFE，还是等着收到RFE?
: 我RRFE都半个月了，TSC还没消息。

b*g2017-08-08 07:08

7 楼

电面吗？

【在 j*****4 的大作中提到】

e*r2017-08-08 07:08

8 楼

big bless!!

v*y2017-08-08 07:08

9 楼

是不是可以维护两个变量，time, count。
if(curTime>time+1){
time = curTime;
count = 1;
return true;
}else if(countcount++;
return true;
}
return false;
不过要解决同步问题。

B*o2017-08-08 07:08

10 楼

bless!!!

v*y2017-08-08 07:08

11 楼

true
不用“throw element out from head of list until the time is 1
出来，新时间加到后面，return true,不是的话，直接return false

【在 t***t 的大作中提到】

: a list of size N, store the time of last N true calls
: when new call, throw element out from head of list until the time is 1
: second from current time. if list is full, return false, else if return true
: , store it at end of list, if return false, do nothing

l*i2017-08-08 07:08

12 楼

Bless！！

p*32017-08-08 07:08

13 楼

要多线程吗，不用的话就
int stateTime, stateCount;
boolean canCall() {
int curTime = systimestamp();
if (curTime != stateTIme) {
stateTime = curTime;
stateCount = 1;
return true;
}
if (curCount >= maxCount)
return false;
curCount ++;
return true;
}

l*n2017-08-08 07:08

14 楼

timeline？

j*42017-08-08 07:08

15 楼

如果上妙所有的call都在后半妙，下秒的所有的call都在前半妙，这个就超了。所以应
该是N/2, 但是他说不精确。。

【在 v*****y 的大作中提到】

: 是不是可以维护两个变量，time, count。
: if(curTime>time+1){
: time = curTime;
: count = 1;
: return true;
: }else if(count: count++;
: return true;
: }
: return false;

t*t2017-08-08 07:08

16 楼

bless!求timeline

j*42017-08-08 07:08

17 楼

昂赛。

【在 b*******g 的大作中提到】

: 电面吗？

N*02017-08-08 07:08

18 楼

What is your RFE? Medical?

【在 p*******e 的大作中提到】

: 你是寄出RRFE，还是等着收到RFE?
: 我RRFE都半个月了，TSC还没消息。

p*32017-08-08 07:08

19 楼

如果以毫秒为最小单位的话建一个int a[1000]，就是一个size是1000的循环队列, 维
护一个count = 0; 和一个curIt = msec%1000;
如果每个毫秒都有call的话 ==> 如果curIt改变了， count = count - a[curIt], 如
果call的不是很频繁，可能需要clear多个slot, 但是amortize的效率还可以，可能他
说的提示就是这个意思

【在 j*****4 的大作中提到】

p*e2017-08-08 07:08

20 楼

Yes, Medical only. NIW.
我准备好了EVL,但只要了Medical，所以没给。

【在 N**********0 的大作中提到】

: What is your RFE? Medical?

w*e2017-08-08 07:08

21 楼

bool cancall() {
static int array[1000]={0};
static int totCnt;
static int lastTime;
static int index;
if(getTime()-lastTime<1) {
lastTime = getTime();
if(totCnt>=N) return false;
array[index]++;
totCnt++;
return true;
}
else {
lastTime = getTime();
index = (index+1)%1000;
totCnt -= array[index];
array[index] = 1;
totCnt++;
return true;
}
}
if you need improve the granularity, increase the size of array and the
timer accuracy.

【在 j*****4 的大作中提到】

r*t2017-08-08 07:08

22 楼

Can you share the timeline? My PD is 2013/3 (end) but did not receive any
RFE from NSC and no response for SR. Nearly one month has passed.

【在 l*******l 的大作中提到】

: 顺便问一下高人，RFE是不是意味着背景调查已经结束并通过了？

h*d2017-08-08 07:08

23 楼

用一个queue，里面保存上次成功的时间，如果已经size N而且第一个时间差<1秒就拒
绝，如果第一个>1秒就出queue，把新的成功cancall加入queue。

l*l2017-08-08 07:08

24 楼

pd: 8/2012
rd: 3/2014
EB2-3
现在还没收到信，不知道具体是什么，收到后马上汇报

B*g2017-08-08 07:08

25 楼

题目明白了

【在 j*****4 的大作中提到】

: 昂赛。

l*l2017-08-08 07:08

26 楼

8/12 收到信，住申请人要了FORM J和体检，副申请人要了体检。

B*g2017-08-08 07:08

27 楼

这和lz解法1有什么区别？

【在 h*d 的大作中提到】

: 用一个queue，里面保存上次成功的时间，如果已经size N而且第一个时间差<1秒就拒
: 绝，如果第一个>1秒就出queue，把新的成功cancall加入queue。

j*92017-08-08 07:08

28 楼

big bless

h*d2017-08-08 07:08

29 楼

:( 这个为啥没效率呢？

【在 B*****g 的大作中提到】

: 这和lz解法1有什么区别？

B*g2017-08-08 07:08

30 楼

难道是不用queue，因为本身request就是有序的，一个list就够了？

【在 h*d 的大作中提到】

: :( 这个为啥没效率呢？

h*d2017-08-08 07:08

31 楼

FIFO我觉得应该用Queue啊，不过可能每次都查太慢？这个可以考虑降低储存的时间的
精度，设定一个delta来保存，这样Queue变化的频率就降低了，另外可能需要考虑lock
的问题？如果同时上百万的请求访问这个，可以考虑把服务的false结果作一个cache，
指定一个delta时间，比如1/10秒，这样1/10之内的所有访问就不需要对Queue进行任何
操作，直接拿false的结果？

【在 B*****g 的大作中提到】

: 难道是不用queue，因为本身request就是有序的，一个list就够了？

B*g2017-08-08 07:08

32 楼

顶，看来得等大牛出手xxx算法了

lock

【在 h*d 的大作中提到】

: FIFO我觉得应该用Queue啊，不过可能每次都查太慢？这个可以考虑降低储存的时间的
: 精度，设定一个delta来保存，这样Queue变化的频率就降低了，另外可能需要考虑lock
: 的问题？如果同时上百万的请求访问这个，可以考虑把服务的false结果作一个cache，
: 指定一个delta时间，比如1/10秒，这样1/10之内的所有访问就不需要对Queue进行任何
: 操作，直接拿false的结果？

a*u2017-08-08 07:08

33 楼

那个算法是leaky bucket algorithm吗？

e*n2017-08-08 07:08

34 楼

int counter = n;
// thread-safe
increase_counter():
n = n + 1
// thread-safe
decrease_counter():
n = n - 1
boolean cancall():
if n equals 0
return false
else
decrease_counter()
set an asynchronous call of increase_counter() 1000ms later
return true

n*e2017-08-08 07:08

35 楼

boolean cancall(){
return false;
}

v*y2017-08-08 07:08

36 楼

那我可能不太理解题意。题目中的一秒指的是绝对的，不是相对的？我的理解是任意一
个一秒的window中返回true的次数都不能多于N。

【在 j*****4 的大作中提到】

: 昂赛。

B*g2017-08-08 07:08

37 楼

假使N=10，
0.0000一个
0.9999九个 (total 10)
1.0001一个 (total 10)
1.0002一个（这个要return false）

【在 v*****y 的大作中提到】

:
: 那我可能不太理解题意。题目中的一秒指的是绝对的，不是相对的？我的理解是任意一
: 个一秒的window中返回true的次数都不能多于N。