由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 面完了G
相关主题
请教一个系统设计问题 (转载)question 2: o(1) euque and dequeue?
web count 设计如何实现binary tree的从下到上的分层打印?
Dropbox 电面share 面试题
问一个system design的题,看看大家怎么想的。Is this a DP problem?
问个Google的面试题这个用stack实现queue
G面试题求解求救: 打印binary tree
A第一轮电面,求建议,面完必update求教一道面试题
ebay第一轮电话面经如何用JAVA中的circular array of queue 解决Josephus problem? (转载)
相关话题的讨论汇总
话题: return话题: true话题: cancall话题: false话题: totcnt
进入JobHunting版参与讨论
1 (共1页)
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里面用的。有人听着耳熟么? 我是不是
: 被黑了。

相关主题
G面试题求解question 2: o(1) euque and dequeue?
A第一轮电面,求建议,面完必update如何实现binary tree的从下到上的分层打印?
ebay第一轮电话面经share 面试题
进入JobHunting版参与讨论
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
相关主题
Is this a DP problem?求教一道面试题
这个用stack实现queue如何用JAVA中的circular array of queue 解决Josephus problem? (转载)
求救: 打印binary tree问个题:get max value from Queue, with O(1)?
进入JobHunting版参与讨论
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。

1 (共1页)
进入JobHunting版参与讨论
相关主题
如何用JAVA中的circular array of queue 解决Josephus problem? (转载)问个Google的面试题
问个题:get max value from Queue, with O(1)?G面试题求解
F家 一道LIS 的变种A第一轮电面,求建议,面完必update
面试题ebay第一轮电话面经
请教一个系统设计问题 (转载)question 2: o(1) euque and dequeue?
web count 设计如何实现binary tree的从下到上的分层打印?
Dropbox 电面share 面试题
问一个system design的题,看看大家怎么想的。Is this a DP problem?
相关话题的讨论汇总
话题: return话题: true话题: cancall话题: false话题: totcnt