w**v
发帖数: 14 | 1 被U家猎头联系，安排电面。
第一轮，用coderpad做题，首先merge two sorted list。然后实现功能，使得某函数
在过去给定时段（比如过去10秒）的调用次数不超过100次。
第二轮，同样用coderpad。实现key value store。同时要求限制容量，新的数据挤走
旧的数据，类似LRU。
两轮都要求现场调试加测试。我感觉还不错，但几天后收到猎头反馈，说不match，但
有可能再联系我。我追问反馈细节，猎头就不理我了。:-(
感觉U的bar似乎不低。 |
f**********d
发帖数: 42 | 2 赞面经！
“实现功能，使得某函数在过去给定时段（比如过去10秒）的调用次数不超过100次。
”这个怎么做的？能贴一下代码吗？谢谢！
【在 w**v 的大作中提到】
: 被U家猎头联系，安排电面。
: 第一轮，用coderpad做题，首先merge two sorted list。然后实现功能，使得某函数
: 在过去给定时段（比如过去10秒）的调用次数不超过100次。
: 第二轮，同样用coderpad。实现key value store。同时要求限制容量，新的数据挤走
: 旧的数据，类似LRU。
: 两轮都要求现场调试加测试。我感觉还不错，但几天后收到猎头反馈，说不match，但
: 有可能再联系我。我追问反馈细节，猎头就不理我了。:-(
: 感觉U的bar似乎不低。
|
w******x
发帖数: 28 | 3 google leaky bucket
[在 futureinhand (Future in Hands) 的大作中提到：]
：赞面经！
：“实现功能，使得某函数在过去给定时段（比如过去10秒）的调用次数不超过100次。
：........... |
f*******r
发帖数: 976 | 4 U的bar比较高啊
被U家猎头联系，安排电面。
第一轮，用coderpad做题，首先merge two sorted list。然后实现功能，使得某函数
在过去给定时段（比如过去10秒）的调用次数不超过100次。
第二轮，同样用coderpad。实现key value store。同时要求限制容量，新的数据挤走
旧的数据，类似LRU。
两轮都要求现场调试加测试。我感觉还不错，但几天后收到猎头反馈，说不match，但
有可能再联系我。我追问反馈细节，猎头就不理我了。:-(
感觉U的bar似乎不低。
【在 w**v 的大作中提到】
: 被U家猎头联系，安排电面。
: 第一轮，用coderpad做题，首先merge two sorted list。然后实现功能，使得某函数
: 在过去给定时段（比如过去10秒）的调用次数不超过100次。
: 第二轮，同样用coderpad。实现key value store。同时要求限制容量，新的数据挤走
: 旧的数据，类似LRU。
: 两轮都要求现场调试加测试。我感觉还不错，但几天后收到猎头反馈，说不match，但
: 有可能再联系我。我追问反馈细节，猎头就不理我了。:-(
: 感觉U的bar似乎不低。
|
f*******r
发帖数: 976 | 5 我的思路是用一个circular ring来实现，因为只要求最近10秒，这个ring只要保存11
个元素就可以了，每个元素保存一个pair p. p的第一个值是epoch time
的秒，第二个值是在该秒调用的次数。每次这个函数被调用，就查询一下最近10的总的
调用次数，如果超过了100次，就返回true。否则就返回false。C++代码如下：
class Counter {
private:
vector > counter;
int index;
const int times;
public:
Counter(int seconds, int ts) : counter(seconds+1), index(-1), times(ts) {}
bool quotaExceeded() {
time_t current = time(NULL);
long sum = 0;
for (int i = 0, e = counter.size(); i < e; ++i) {
if (counter[i].first >= current - 10) {
// This happens in the last 10 seconds.
sum += counter[i].second;
} else {
counter[i] = make_pair(0, 0);
}
}
// More than 100 times, we return here directly.
if (sum >= times) return true;
if (index != -1 && counter[index].first == current)
counter[index].second++;
else {
index = (index+1)%counter.size();
counter[index] = make_pair(current, 1);
}
return false;
}
};
比如，你有个函数g，你想要保证g每10秒只被调用100次，那你就可以这么做：
void g() {
static Counter counter(10, 100);
if (counter.quotaExceeded()) return;
std::cout << "g() " << count << std::endl;
}
赞面经！
“实现功能，使得某函数在过去给定时段（比如过去10秒）的调用次数不超过100次。
”这个怎么做的？能贴一下代码吗？谢谢！
【在 f**********d 的大作中提到】
: 赞面经！
: “实现功能，使得某函数在过去给定时段（比如过去10秒）的调用次数不超过100次。
: ”这个怎么做的？能贴一下代码吗？谢谢！
|
f**********d
发帖数: 42 | 6 谢谢！点赞！
11
time
【在 f*******r 的大作中提到】
: 我的思路是用一个circular ring来实现，因为只要求最近10秒，这个ring只要保存11
: 个元素就可以了，每个元素保存一个pair p. p的第一个值是epoch time
: 的秒，第二个值是在该秒调用的次数。每次这个函数被调用，就查询一下最近10的总的
: 调用次数，如果超过了100次，就返回true。否则就返回false。C++代码如下：
: class Counter {
: private:
: vector > counter;
: int index;
: const int times;
: public:
|
c*******t
发帖数: 123 | 7 我觉得你这个似乎有问题？
首先你返回true or false是O(1)吗？这种题目一般要求查询O(1) 复杂度，而你里面还
有for loop.我没细看。
其次，你时间判断 “counter[i].first >= current - 10” 我怎么觉得有点问题？
你下面调用
if (counter.quotaExceeded()) return;
std::cout << "g() " << count << std::endl;
如果在0.000000000秒有100次调用。第10.00000秒你执行if 判断，答案是不能再调用
了。
但实际上是可以调用的，因为假设你if判断执行了0.01毫秒，到第二行std::cout....
真正执行的时候，
第0.0000000000秒的已经过期了。
所以 “counter[i].first >= current - 10” 中的等号是不是应该去掉？
为什么不用queue 呢？
每次只要检查queue前端是否已经过时，过时弹出，这个是不变量，
然后只要 return queue.size<100;
queue size最多100。
而且我们还要考虑多线程调用的情况。
11
time
【在 f*******r 的大作中提到】
: 我的思路是用一个circular ring来实现，因为只要求最近10秒，这个ring只要保存11
: 个元素就可以了，每个元素保存一个pair p. p的第一个值是epoch time
: 的秒，第二个值是在该秒调用的次数。每次这个函数被调用，就查询一下最近10的总的
: 调用次数，如果超过了100次，就返回true。否则就返回false。C++代码如下：
: class Counter {
: private:
: vector > counter;
: int index;
: const int times;
: public:
|
f*******r
发帖数: 976 | 8
我觉得你这个似乎有问题？
首先你返回true or false是O(1)吗？这种题目一般要求查询O(1) 复杂度，而你里面还
有for loop.我没细看。
=======================================================
你还是仔细看完再做评论，没看你就发表评论不好。还有一个就是这题根本没写O(1)的
复杂度。你可以写一个O(1)或者是O(-1)的给大家来欣赏一下。
其次，你时间判断 “counter[i].first >= current - 10” 我怎么觉得有点问题？
你下面调用
if (counter.quotaExceeded()) return;
std::cout << "g() " << count << std::endl;
如果在0.000000000秒有100次调用。第10.00000秒你执行if 判断，答案是不能再调用
了。
但实际上是可以调用的，因为假设你if判断执行了0.01毫秒，到第二行std::cout....
真正执行的时候，
第0.0000000000秒的已经过期了。
==========================================
if判断根本就不要0.01秒，你的假设就已经错了。跟你说一下，Linux不是real time
kernel。你要精确到0.01秒，你还得要发明个hard real-time kernel再来做这道题。
所以 “counter[i].first >= current - 10” 中的等号是不是应该去掉？
为什么不用queue 呢？
================================================
你知道C++ queue是怎么实现的吗？queue和circular ring相比有什么好处吗？
每次只要检查queue前端是否已经过时，过时弹出，这个是不变量，
然后只要 return queue.size<100;
queue size最多100。
=================================================
loop through 100效率高还是loop 10个效率高？
而且我们还要考虑多线程调用的情况。
================================================
对，是要考虑多线程，reentrant, 还要考虑IPC等等
还要考虑时钟漂移，处理器过热等
【在 c*******t 的大作中提到】
: 我觉得你这个似乎有问题？
: 首先你返回true or false是O(1)吗？这种题目一般要求查询O(1) 复杂度，而你里面还
: 有for loop.我没细看。
: 其次，你时间判断 “counter[i].first >= current - 10” 我怎么觉得有点问题？
: 你下面调用
: if (counter.quotaExceeded()) return;
: std::cout << "g() " << count << std::endl;
: 如果在0.000000000秒有100次调用。第10.00000秒你执行if 判断，答案是不能再调用
: 了。
: 但实际上是可以调用的，因为假设你if判断执行了0.01毫秒，到第二行std::cout....
|
r*****n
发帖数: 17 | 9 也许我没看仔细，这个解法似乎没有解决sparse caller的情况：比如说20秒的window
，前10秒每秒调用1次，这样buffer的每个counter是1，后10秒只在最后1秒调用1次，
那么前面的9个couter清空了么？
11
time
【在 f*******r 的大作中提到】
: 我的思路是用一个circular ring来实现，因为只要求最近10秒，这个ring只要保存11
: 个元素就可以了，每个元素保存一个pair p. p的第一个值是epoch time
: 的秒，第二个值是在该秒调用的次数。每次这个函数被调用，就查询一下最近10的总的
: 调用次数，如果超过了100次，就返回true。否则就返回false。C++代码如下：
: class Counter {
: private:
: vector > counter;
: int index;
: const int times;
: public:
|
e********2
发帖数: 495 | |
f*******r
发帖数: 976 | 11 你代码没看懂，再仔细读读。前9个不清空，看你的window大小，只有超过了window
size的才被清空。
window
【在 r*****n 的大作中提到】
: 也许我没看仔细，这个解法似乎没有解决sparse caller的情况：比如说20秒的window
: ，前10秒每秒调用1次，这样buffer的每个counter是1，后10秒只在最后1秒调用1次，
: 那么前面的9个couter清空了么？
:
: 11
: time
|
c*******t
发帖数: 123 | 12 我说的是0.01毫秒，不是0.01秒。你怪别人看你代码不仔细，你就不能仔细看看别人说
的？
你那个确实是bug. 没有什么real time kernel那么复杂，程序执行有一个特征时间，
比如一次程序执行的特征时间是千分之一毫秒，你时间window判断的浮点数误差只要小
于这个特征时间，
就可以排除这个bug.
楼主缺乏精益求精的科学态度。
【在 f*******r 的大作中提到】
: 你代码没看懂，再仔细读读。前9个不清空，看你的window大小，只有超过了window
: size的才被清空。
:
: window
|
