j*****4
发帖数: 12 | 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里面用的。有人听着耳熟么？ 我是不是
被黑了。 |
B*****g
发帖数: 34098 | 2 难道不是设个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里面用的。有人听着耳熟么？ 我是不是
: 被黑了。
|
t***t
发帖数: 6066 | 3 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 的大作中提到】
: 估计挂了，有一题基本不知道怎么解。
: 设计一个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里面用的。有人听着耳熟么？ 我是不是
: 被黑了。
|
b*******g
发帖数: 57 | 4 电面吗？
【在 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里面用的。有人听着耳熟么？ 我是不是
: 被黑了。
|
v*****y
发帖数: 68 | 5 是不是可以维护两个变量，time, count。
if(curTime>time+1){
time = curTime;
count = 1;
return true;
}else if(count
count++;
return true;
}
return false;
不过要解决同步问题。 |
v*****y
发帖数: 68 | 6
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
|
p*****3
发帖数: 488 | 7 要多线程吗，不用的话就
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;
} |
j*****4
发帖数: 12 | 8
如果上妙所有的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;
|
j*****4
发帖数: 12 | 9 昂赛。
【在 b*******g 的大作中提到】
: 电面吗？
|
p*****3
发帖数: 488 | 10
如果以毫秒为最小单位的话建一个int a[1000]，就是一个size是1000的循环队列, 维
护一个count = 0; 和一个curIt = msec%1000;
如果每个毫秒都有call的话 ==> 如果curIt改变了， count = count - a[curIt], 如
果call的不是很频繁，可能需要clear多个slot, 但是amortize的效率还可以，可能他
说的提示就是这个意思
【在 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里面用的。有人听着耳熟么？ 我是不是
: 被黑了。
|
|
|
w*******e
发帖数: 395 | 11 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 的大作中提到】
: 估计挂了，有一题基本不知道怎么解。
: 设计一个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里面用的。有人听着耳熟么？ 我是不是
: 被黑了。
|
h*d
发帖数: 19309 | 12 用一个queue，里面保存上次成功的时间，如果已经size N而且第一个时间差<1秒就拒
绝，如果第一个>1秒就出queue，把新的成功cancall加入queue。 |
B*****g
发帖数: 34098 | 13 题目明白了
【在 j*****4 的大作中提到】
: 昂赛。
|
B*****g
发帖数: 34098 | 14 这和lz解法1有什么区别？
【在 h*d 的大作中提到】
: 用一个queue，里面保存上次成功的时间，如果已经size N而且第一个时间差<1秒就拒
: 绝，如果第一个>1秒就出queue，把新的成功cancall加入queue。
|
h*d
发帖数: 19309 | 15 :( 这个为啥没效率呢？
【在 B*****g 的大作中提到】
: 这和lz解法1有什么区别？
|
B*****g
发帖数: 34098 | 16 难道是不用queue，因为本身request就是有序的，一个list就够了？
【在 h*d 的大作中提到】
: :( 这个为啥没效率呢？
|
h*d
发帖数: 19309 | 17 FIFO我觉得应该用Queue啊，不过可能每次都查太慢？这个可以考虑降低储存的时间的
精度，设定一个delta来保存，这样Queue变化的频率就降低了，另外可能需要考虑lock
的问题？如果同时上百万的请求访问这个，可以考虑把服务的false结果作一个cache，
指定一个delta时间，比如1/10秒，这样1/10之内的所有访问就不需要对Queue进行任何
操作，直接拿false的结果？
【在 B*****g 的大作中提到】
: 难道是不用queue，因为本身request就是有序的，一个list就够了？
|
B*****g
发帖数: 34098 | 18 顶，看来得等大牛出手xxx算法了
lock
【在 h*d 的大作中提到】
: FIFO我觉得应该用Queue啊，不过可能每次都查太慢？这个可以考虑降低储存的时间的
: 精度，设定一个delta来保存，这样Queue变化的频率就降低了，另外可能需要考虑lock
: 的问题？如果同时上百万的请求访问这个，可以考虑把服务的false结果作一个cache，
: 指定一个delta时间，比如1/10秒，这样1/10之内的所有访问就不需要对Queue进行任何
: 操作，直接拿false的结果？
|
a******u
发帖数: 14 | 19 那个算法是leaky bucket algorithm吗？ |
e*n
发帖数: 22 | 20 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********e
发帖数: 41 | 21 boolean cancall(){
return false;
} |
v*****y
发帖数: 68 | 22
那我可能不太理解题意。题目中的一秒指的是绝对的，不是相对的？我的理解是任意一
个一秒的window中返回true的次数都不能多于N。
【在 j*****4 的大作中提到】
: 昂赛。
|
B*****g
发帖数: 34098 | 23 假使N=10，
0.0000一个
0.9999九个 (total 10)
1.0001一个 (total 10)
1.0002一个 （这个要return false）
【在 v*****y 的大作中提到】
:
: 那我可能不太理解题意。题目中的一秒指的是绝对的，不是相对的？我的理解是任意一
: 个一秒的window中返回true的次数都不能多于N。
|
