l*****n
发帖数: 199 | 1 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
两个function;
void hit()
long getHits() //返回五分钟内hit了几次 |
h********g
发帖数: 496 | 2 用static variable吗？
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
l*n
发帖数: 529 | 3 看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
钟的时间窗口。真是一个题什么都涉及到了。
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
z*********8
发帖数: 2070 | 4 正解
G/Y!也问过类似的题目， circular buffer答出来就基本搞定了
【在 l*n 的大作中提到】
: 看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
: 是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
: 钟的时间窗口。真是一个题什么都涉及到了。
|
l*****n
发帖数: 199 | 5 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
让我写unit test测试,然后再讨论如何concurrent. |
f******p
发帖数: 173 | 6 记得不久前有版友分享g的题目，也是统计hit之类， last 1 min, last 1 hr, last
day 链接找不到了。 那个题也是这个思路吗？
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
z*********8
发帖数: 2070 | 7 对的
【在 f******p 的大作中提到】
: 记得不久前有版友分享g的题目，也是统计hit之类， last 1 min, last 1 hr, last
: day 链接找不到了。 那个题也是这个思路吗？
|
c********p
发帖数: 1969 | |
M*********r
发帖数: 70 | 9
楼主可以写个code参考一下吗，我不是太明白“发现上次时间超过了一秒就重新计数0
”的意思。多谢了！
【在 l*****n 的大作中提到】
: 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
: 时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
: getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
: 让我写unit test测试,然后再讨论如何concurrent.
|
l*****n
发帖数: 199 | 10 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
两个function;
void hit()
long getHits() //返回五分钟内hit了几次 |
|
|
l*n
发帖数: 529 | 11 看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
钟的时间窗口。真是一个题什么都涉及到了。
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
z*********8
发帖数: 2070 | 12 正解
G/Y!也问过类似的题目， circular buffer答出来就基本搞定了
【在 l*n 的大作中提到】
: 看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
: 是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
: 钟的时间窗口。真是一个题什么都涉及到了。
|
l*****n
发帖数: 199 | 13 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
让我写unit test测试,然后再讨论如何concurrent. |
f******p
发帖数: 173 | 14 记得不久前有版友分享g的题目，也是统计hit之类， last 1 min, last 1 hr, last
day 链接找不到了。 那个题也是这个思路吗？
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
z*********8
发帖数: 2070 | 15 对的
【在 f******p 的大作中提到】
: 记得不久前有版友分享g的题目，也是统计hit之类， last 1 min, last 1 hr, last
: day 链接找不到了。 那个题也是这个思路吗？
|
c********p
发帖数: 1969 | |
M*********r
发帖数: 70 | 17
楼主可以写个code参考一下吗，我不是太明白“发现上次时间超过了一秒就重新计数0
”的意思。多谢了！
【在 l*****n 的大作中提到】
: 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
: 时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
: getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
: 让我写unit test测试,然后再讨论如何concurrent.
|
m*****k
发帖数: 731 | 18 co-ask on this “发现上次时间超过了一秒就重新计数0
0 |
l*****a
发帖数: 14598 | 19 数组300 ITEM
每一个对一秒中HIT NUMBER进行计数
每次新hit跟last hit timestamp比较
如果超出了一秒，显然要对last timestamp到现在这段全部清0，再写入本次hit 信息
【在 m*****k 的大作中提到】
: co-ask on this “发现上次时间超过了一秒就重新计数0
: 0
|
m*****k
发帖数: 731 | 20 上一秒的都清0了，还咋统计last 1 min data? |
|
|
s********l
发帖数: 998 | 21 他们是说 那个static hit 次数清领
不是timestamp
楼上各位牛牛 是这意思把？
【在 m*****k 的大作中提到】
: 上一秒的都清0了，还咋统计last 1 min data?
|
s*****4
发帖数: 25 | 22 I wrote the code based on LZ's description.
Do you guys think this is correct?
Any suggestion/improvement is appreciated!
class HitsCounter {
private:
vector hitcnt; // stores the hit for each second
long long total; // always keeps the current hit count
long long last; // the time of last hit
int size; // size of hitcnt array, for this question set to
300
public:
HitsCounter(int secondCnt) {
// in this case, secondCnt shoule be 300
hitcnt = vector(secondCnt, 0);
total = 0;
size = secondCnt;
}
long long getHit() {
// total always stores the current hit count
return total;
}
void hit(long long cur) {
// suppose the unit of time() is second
// long long cur = time();
// if cur > last, some previous value need to be reset to 0
// also, if t - last > size, we've set 0 for entire queue, no need
to continue
for (int t = last + 1; t <= cur && t - last <= size; t++) {
// update total, and reset the specific count to 0
total -= hitcnt[t % size];
hitcnt[t % size] = 0;
}
// update hitcnt, total and last for this hit
hitcnt[cur % size]++;
total++;
last = cur;
}
}; |
m*****k
发帖数: 731 | 23 从last＋ 1开始清0，makes sense. |
t*******e
发帖数: 274 | 24
我有两个问题关于你的代码：
1）hitcnt的index是什么含义，我理解每个index是1秒的间隔，hitcnt[0]表示cur hit
()之前300秒时的hit()数目，hitcnt[299]表示last hit()数目， 假如cur hit()是
last hit()之后2秒，根据你的代码，会把hitcnt[0]和hitcnt[1]置0, 但是这里是否需
要把剩余的298个值往前移两格呢？
2）你更新的时候都是自增1，但是题目并没有说明每秒的hit()数目都固定为1，这里我
也有疑问
【在 s*****4 的大作中提到】
: I wrote the code based on LZ's description.
: Do you guys think this is correct?
: Any suggestion/improvement is appreciated!
: class HitsCounter {
: private:
: vector hitcnt; // stores the hit for each second
: long long total; // always keeps the current hit count
: long long last; // the time of last hit
: int size; // size of hitcnt array, for this question set to
: 300
|
w*****u
发帖数: 6 | |
n****2
发帖数: 307 | |
s*****4
发帖数: 25 | 27 Unit test要写到多详细呢 有人可以给个例子吗?
test cases我只想到这三个:
1. last hit和cur hit发生在同一秒
2. last hit和cur hit发生在不同秒, 检查结果是否正确的把last hit到cur hit之间
的element reset 0
3. 同2, 且last hit跟cur hit发生的间隔很大(ex. 30000s), 检查run time, 看是否
在reset完300个element后就early return
concurrency是不是只需要用一个mutex把hit()头尾用mutex.lock(), nutex.unlock()
包住就行了? 不是很确定... |
m******n
发帖数: 233 | 28 谢谢楼主分享！
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
h***s
发帖数: 45 | 29 这里精确到秒的意思是不是每秒hit()被调用的次数是可知的？还是说每秒最多只能调
用一次？
【在 l*****a 的大作中提到】
: 数组300 ITEM
: 每一个对一秒中HIT NUMBER进行计数
: 每次新hit跟last hit timestamp比较
: 如果超出了一秒，显然要对last timestamp到现在这段全部清0，再写入本次hit 信息
|
m*******g
发帖数: 410 | |
|
|
e***m
发帖数: 92 | 31 这个code有个小问题。gethit()里，应先调time()找出当前时间，再去vector里找对应
的hit个数
【在 s*****4 的大作中提到】
: I wrote the code based on LZ's description.
: Do you guys think this is correct?
: Any suggestion/improvement is appreciated!
: class HitsCounter {
: private:
: vector hitcnt; // stores the hit for each second
: long long total; // always keeps the current hit count
: long long last; // the time of last hit
: int size; // size of hitcnt array, for this question set to
: 300
|
d******v
发帖数: 801 | |
j******8
发帖数: 105 | 33 mark
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
e***m
发帖数: 92 | 34 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
数组中已有数据，经过很长时间的silent后，来了个hit
【在 s*****4 的大作中提到】
: I wrote the code based on LZ's description.
: Do you guys think this is correct?
: Any suggestion/improvement is appreciated!
: class HitsCounter {
: private:
: vector hitcnt; // stores the hit for each second
: long long total; // always keeps the current hit count
: long long last; // the time of last hit
: int size; // size of hitcnt array, for this question set to
: 300
|
y**********a
发帖数: 824 | 35
我看了一下 circular buffer。和你的解法应该殊途同归，不过 cb 更加
系统一些吧。
赞分享。顺求 Google 以前的 hit 题。
【在 l*****n 的大作中提到】
: 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
: 时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
: getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
: 让我写unit test测试,然后再讨论如何concurrent.
|
r*******e
发帖数: 971 | 36 那样会直接清0了。
有一个问题是，经过很长时间的silence 来了个gethit
【在 e***m 的大作中提到】
: 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
: 数组中已有数据，经过很长时间的silent后，来了个hit
|
d****n
发帖数: 233 | 37 为什么ＬｉｎｋｅｄＬｉｓｔ不行呢？这样做应该比Circular Buffer简单吧：
struct ListNode
{
int seconds;
int hits;
ListNode next;
}
// Assume the accuracy is to seconds level
Class FiveMinuteCounter
{
private long m_hits;
private ListNode m_head;
private ListNode m_tail;
public FiveMinuteCounter()
{
m_head = m_tail = new ListNode(0);
m_hits = 0;
}
public void Hits()
{
long current = GetCurrentSeconds();
if (m_tail.seconds < current) {
m_tail.next = new ListNode () { seconds = current, hits = 1};
m_tail = m_tail.next;
} else {
m_tail.hits++;
}
m_hits++;
while(m_head.next != null && m_head.next.seconds < current-300)
{
m_hits -= m_head.next.hits;
m_head.next = m_head.next.next;
}
}
public long GetHits()
{
long current = GetCurrentSeconds();
while(m_head.next != null && m_head.next.seconds < current-300)
{
m_hits -= m_head.next.hits;
m_head.next = m_head.next.next;
}
if (m_head.next == null) {
m_tail = m_head;
}
return m_hits;
}
｝
【在 l*n 的大作中提到】
: 看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
: 是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
: 钟的时间窗口。真是一个题什么都涉及到了。
|
m*******1
发帖数: 168 | |
h***k
发帖数: 161 | |
s*****4
发帖数: 25 | 40 的确啊, 谢谢了! 这是个大bug, 奇怪我之前都检查2, 3次了, 怎么没发现呢...
【在 e***m 的大作中提到】
: 这个code有个小问题。gethit()里，应先调time()找出当前时间，再去vector里找对应
: 的hit个数
|
|
|
s*****4
发帖数: 25 | 41 这个我不太懂, 是考虑time overflow吗?
【在 e***m 的大作中提到】
: 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
: 数组中已有数据，经过很长时间的silent后，来了个hit
|
e***m
发帖数: 92 | 42 我的concern是：经过很长的一个silent period, 数组中的所有counter可能因为太久
远了不能用了
【在 s*****4 的大作中提到】
: 这个我不太懂, 是考虑time overflow吗?
|
s*****4
发帖数: 25 | 43 了解~ 我想我的getHit()应该要做类似hit()里做的事, 先把last到cur间的值清零, 再
加总剩下的值, 这样的话应该work?
【在 e***m 的大作中提到】
: 我的concern是：经过很长的一个silent period, 数组中的所有counter可能因为太久
: 远了不能用了
|
e***m
发帖数: 92 | 44 if cur-300>last
整个数组清零
else
(last-300,cur-300］对应的counters清零
再把cur对应的counter加一
【在 s*****4 的大作中提到】
: 了解~ 我想我的getHit()应该要做类似hit()里做的事, 先把last到cur间的值清零, 再
: 加总剩下的值, 这样的话应该work?
|
l**********1
发帖数: 415 | |
H********k
发帖数: 122 | |
Q*****a
发帖数: 33 | 47 #include "stdafx.h"
#include
#include
#include
namespace {
class IStopWatch {
public:
virtual void Start() = 0;
virtual double SecondsFromStart() = 0;
};
class StopWatch: public IStopWatch {
private:
time_t start_;
public:
StopWatch(bool start) {
if (start) {
Start();
}
}
virtual void Start() {
time(&start_);
}
virtual double SecondsFromStart() {
time_t cur;
time(&cur);
return difftime(cur, start_);
}
};
class HitCounter {
IStopWatch* stopWatch_;
std::vector counts_;
int lastSecond_;
int curHit_;
public:
HitCounter(IStopWatch* stopWatch, int intervals): stopWatch_(
stopWatch), counts_(intervals) {
stopWatch_->Start();
lastSecond_ = 0;
curHit_ = 0;
}
void Hit() {
int curSecond = (int)stopWatch_->SecondsFromStart();
ExpireHits(curSecond);
++counts_[curSecond % counts_.size()];
++curHit_;
lastSecond_ = curSecond;
}
void ExpireHits(int curSecond) {
if (curSecond >= lastSecond_ + (int)counts_.size()) {
std::fill_n(counts_.begin(), counts_.size(), 0);
curHit_ = 0;
}
else {
for (int i = lastSecond_ + 1; i <= curSecond; ++i) {
int j = i % counts_.size();
curHit_ -= counts_[j];
counts_[j] = 0;
}
}
}
int TotalHit() {
int curSecond = (int)stopWatch_->SecondsFromStart();
ExpireHits(curSecond);
return curHit_;
}
};
class FakeStopWatch : public IStopWatch {
double toReturn_;
public:
FakeStopWatch() : toReturn_(0) {
}
void SetToReturn(double toReturn) {
toReturn_ = toReturn;
}
virtual void Start(){}
virtual double SecondsFromStart() {
return toReturn_;
}
};
TEST(HitCounter, Simple) {
FakeStopWatch stopWatch;
HitCounter counter(&stopWatch, 5);
for (int i = 0; i < 6; ++i)counter.Hit();
ASSERT_EQ(6, counter.TotalHit());
stopWatch.SetToReturn(3);
ASSERT_EQ(6, counter.TotalHit());
counter.Hit();
ASSERT_EQ(7, counter.TotalHit());
stopWatch.SetToReturn(5);
ASSERT_EQ(1, counter.TotalHit());
}
TEST(HitCounter, Increasing) {
FakeStopWatch stopWatch;
HitCounter counter(&stopWatch, 5);
for (int i = 0; i < 10; ++i) {
stopWatch.SetToReturn(i);
for (int j = 0; j <= i; ++j) {
counter.Hit();
}
if (i < 5) {
ASSERT_EQ((i + 1) * (i + 2) / 2, counter.TotalHit());
}
else {
ASSERT_EQ(((i + 1) * (i + 2) - (i - 4)*(i - 3)) / 2, counter
.TotalHit());
}
}
}
} |
s*****B
发帖数: 32 | |
f***b
发帖数: 21 | |
g*******0
发帖数: 20 | 50 前两天电面也被问到了这个题，没看版上的面经，肠子已悔青。
这题相当tricky，用circular buffer并不好做，我最早想到的就是circular buffer，
但是写了一遍，面试官说有bug，fix了面试官说还有bug，这样来来回回了好几趟。主
要得考虑相邻两次hit是不是在一个bucket中，并且相差多远（大于5分钟还是小于5分
钟），不仅得考虑两次hit，还需要考虑getHit与上次hit相差多远（大于5分钟还是小
于5分钟），中途问面试官可不可以用一个background job来清空bucket，被告知不可
以。相比起来应该还是用链表更好写一些。
把所有bug都fix过后，面试官又问在多线程的情况下这段code怎么改，本来应该给所有
变量都加个读写锁的，但是已经没有时间，只有把整个函数都给锁掉。鉴于fix了很多
次bug以及效率很低下的锁，现在只有坐等据信了:(
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
|
|
m*****k
发帖数: 18 | |
n****a
发帖数: 195 | |
v*******C
发帖数: 28 | |
m*****k
发帖数: 731 | 54 co-ask on this “发现上次时间超过了一秒就重新计数0
0 |
l*****a
发帖数: 14598 | 55 数组300 ITEM
每一个对一秒中HIT NUMBER进行计数
每次新hit跟last hit timestamp比较
如果超出了一秒，显然要对last timestamp到现在这段全部清0，再写入本次hit 信息
【在 m*****k 的大作中提到】
: co-ask on this “发现上次时间超过了一秒就重新计数0
: 0
|
m*****k
发帖数: 731 | 56 上一秒的都清0了，还咋统计last 1 min data? |
s********l
发帖数: 998 | 57 他们是说 那个static hit 次数清领
不是timestamp
楼上各位牛牛 是这意思把？
【在 m*****k 的大作中提到】
: 上一秒的都清0了，还咋统计last 1 min data?
|
s*****4
发帖数: 25 | 58 I wrote the code based on LZ's description.
Do you guys think this is correct?
Any suggestion/improvement is appreciated!
class HitsCounter {
private:
vector hitcnt; // stores the hit for each second
long long total; // always keeps the current hit count
long long last; // the time of last hit
int size; // size of hitcnt array, for this question set to
300
public:
HitsCounter(int secondCnt) {
// in this case, secondCnt shoule be 300
hitcnt = vector(secondCnt, 0);
total = 0;
size = secondCnt;
}
long long getHit() {
// total always stores the current hit count
return total;
}
void hit(long long cur) {
// suppose the unit of time() is second
// long long cur = time();
// if cur > last, some previous value need to be reset to 0
// also, if t - last > size, we've set 0 for entire queue, no need
to continue
for (int t = last + 1; t <= cur && t - last <= size; t++) {
// update total, and reset the specific count to 0
total -= hitcnt[t % size];
hitcnt[t % size] = 0;
}
// update hitcnt, total and last for this hit
hitcnt[cur % size]++;
total++;
last = cur;
}
}; |
m*****k
发帖数: 731 | 59 从last＋ 1开始清0，makes sense. |
t*******e
发帖数: 274 | 60
LZ 提到的unit test有什么edge case可以测么？另外关于concurrent的解法，网上搜
到一些，但是看着有些乱，你有比较清晰的解法么？
【在 s*****4 的大作中提到】
: I wrote the code based on LZ's description.
: Do you guys think this is correct?
: Any suggestion/improvement is appreciated!
: class HitsCounter {
: private:
: vector hitcnt; // stores the hit for each second
: long long total; // always keeps the current hit count
: long long last; // the time of last hit
: int size; // size of hitcnt array, for this question set to
: 300
|
|
|
w*****u
发帖数: 6 | |
n****2
发帖数: 307 | |
s*****4
发帖数: 25 | 63 Unit test要写到多详细呢 有人可以给个例子吗?
test cases我只想到这三个:
1. last hit和cur hit发生在同一秒
2. last hit和cur hit发生在不同秒, 检查结果是否正确的把last hit到cur hit之间
的element reset 0
3. 同2, 且last hit跟cur hit发生的间隔很大(ex. 30000s), 检查run time, 看是否
在reset完300个element后就early return
concurrency是不是只需要用一个mutex把hit()头尾用mutex.lock(), nutex.unlock()
包住就行了? 不是很确定... |
h***s
发帖数: 45 | 64 这里精确到秒的意思是不是每秒hit()被调用的次数是可知的？还是说每秒最多只能调
用一次？
【在 l*****a 的大作中提到】
: 数组300 ITEM
: 每一个对一秒中HIT NUMBER进行计数
: 每次新hit跟last hit timestamp比较
: 如果超出了一秒，显然要对last timestamp到现在这段全部清0，再写入本次hit 信息
|
m*******g
发帖数: 410 | |
e***m
发帖数: 92 | 66 这个code有个小问题。gethit()里，应先调time()找出当前时间，再去vector里找对应
的hit个数
【在 s*****4 的大作中提到】
: I wrote the code based on LZ's description.
: Do you guys think this is correct?
: Any suggestion/improvement is appreciated!
: class HitsCounter {
: private:
: vector hitcnt; // stores the hit for each second
: long long total; // always keeps the current hit count
: long long last; // the time of last hit
: int size; // size of hitcnt array, for this question set to
: 300
|
d******v
发帖数: 801 | |
j******8
发帖数: 105 | 68 mark
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
e***m
发帖数: 92 | 69 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
数组中已有数据，经过很长时间的silent后，来了个hit
【在 s*****4 的大作中提到】
: I wrote the code based on LZ's description.
: Do you guys think this is correct?
: Any suggestion/improvement is appreciated!
: class HitsCounter {
: private:
: vector hitcnt; // stores the hit for each second
: long long total; // always keeps the current hit count
: long long last; // the time of last hit
: int size; // size of hitcnt array, for this question set to
: 300
|
y**********a
发帖数: 824 | 70
我看了一下 circular buffer。和你的解法应该殊途同归，不过 cb 更加
系统一些吧。
赞分享。顺求 Google 以前的 hit 题。
【在 l*****n 的大作中提到】
: 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
: 时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
: getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
: 让我写unit test测试,然后再讨论如何concurrent.
|
|
|
r*******e
发帖数: 971 | 71 那样会直接清0了。
有一个问题是，经过很长时间的silence 来了个gethit
【在 e***m 的大作中提到】
: 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
: 数组中已有数据，经过很长时间的silent后，来了个hit
|
d****n
发帖数: 233 | 72 为什么ＬｉｎｋｅｄＬｉｓｔ不行呢？这样做应该比Circular Buffer简单吧：
struct ListNode
{
int seconds;
int hits;
ListNode next;
}
// Assume the accuracy is to seconds level
Class FiveMinuteCounter
{
private long m_hits;
private ListNode m_head;
private ListNode m_tail;
public FiveMinuteCounter()
{
m_head = m_tail = new ListNode(0);
m_hits = 0;
}
public void Hits()
{
long current = GetCurrentSeconds();
if (m_tail.seconds < current) {
m_tail.next = new ListNode () { seconds = current, hits = 1};
m_tail = m_tail.next;
} else {
m_tail.hits++;
}
m_hits++;
while(m_head.next != null && m_head.next.seconds < current-300)
{
m_hits -= m_head.next.hits;
m_head.next = m_head.next.next;
}
}
public long GetHits()
{
long current = GetCurrentSeconds();
while(m_head.next != null && m_head.next.seconds < current-300)
{
m_hits -= m_head.next.hits;
m_head.next = m_head.next.next;
}
if (m_head.next == null) {
m_tail = m_head;
}
return m_hits;
}
｝
【在 l*n 的大作中提到】
: 看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
: 是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
: 钟的时间窗口。真是一个题什么都涉及到了。
|
m*******1
发帖数: 168 | |
h***k
发帖数: 161 | |
s*****4
发帖数: 25 | 75 的确啊, 谢谢了! 这是个大bug, 奇怪我之前都检查2, 3次了, 怎么没发现呢...
【在 e***m 的大作中提到】
: 这个code有个小问题。gethit()里，应先调time()找出当前时间，再去vector里找对应
: 的hit个数
|
s*****4
发帖数: 25 | 76 这个我不太懂, 是考虑time overflow吗?
【在 e***m 的大作中提到】
: 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
: 数组中已有数据，经过很长时间的silent后，来了个hit
|
e***m
发帖数: 92 | 77 我的concern是：经过很长的一个silent period, 数组中的所有counter可能因为太久
远了不能用了
【在 s*****4 的大作中提到】
: 这个我不太懂, 是考虑time overflow吗?
|
s*****4
发帖数: 25 | 78 了解~ 我想我的getHit()应该要做类似hit()里做的事, 先把last到cur间的值清零, 再
加总剩下的值, 这样的话应该work?
【在 e***m 的大作中提到】
: 我的concern是：经过很长的一个silent period, 数组中的所有counter可能因为太久
: 远了不能用了
|
e***m
发帖数: 92 | 79 if cur-300>last
整个数组清零
else
(last-300,cur-300］对应的counters清零
再把cur对应的counter加一
【在 s*****4 的大作中提到】
: 了解~ 我想我的getHit()应该要做类似hit()里做的事, 先把last到cur间的值清零, 再
: 加总剩下的值, 这样的话应该work?
|
l**********1
发帖数: 415 | |
|
|
H********k
发帖数: 122 | |
Q*****a
发帖数: 33 | 82 #include "stdafx.h"
#include
#include
#include
namespace {
class IStopWatch {
public:
virtual void Start() = 0;
virtual double SecondsFromStart() = 0;
};
class StopWatch: public IStopWatch {
private:
time_t start_;
public:
StopWatch(bool start) {
if (start) {
Start();
}
}
virtual void Start() {
time(&start_);
}
virtual double SecondsFromStart() {
time_t cur;
time(&cur);
return difftime(cur, start_);
}
};
class HitCounter {
IStopWatch* stopWatch_;
std::vector counts_;
int lastSecond_;
int curHit_;
public:
HitCounter(IStopWatch* stopWatch, int intervals): stopWatch_(
stopWatch), counts_(intervals) {
stopWatch_->Start();
lastSecond_ = 0;
curHit_ = 0;
}
void Hit() {
int curSecond = (int)stopWatch_->SecondsFromStart();
ExpireHits(curSecond);
++counts_[curSecond % counts_.size()];
++curHit_;
lastSecond_ = curSecond;
}
void ExpireHits(int curSecond) {
if (curSecond >= lastSecond_ + (int)counts_.size()) {
std::fill_n(counts_.begin(), counts_.size(), 0);
curHit_ = 0;
}
else {
for (int i = lastSecond_ + 1; i <= curSecond; ++i) {
int j = i % counts_.size();
curHit_ -= counts_[j];
counts_[j] = 0;
}
}
}
int TotalHit() {
int curSecond = (int)stopWatch_->SecondsFromStart();
ExpireHits(curSecond);
return curHit_;
}
};
class FakeStopWatch : public IStopWatch {
double toReturn_;
public:
FakeStopWatch() : toReturn_(0) {
}
void SetToReturn(double toReturn) {
toReturn_ = toReturn;
}
virtual void Start(){}
virtual double SecondsFromStart() {
return toReturn_;
}
};
TEST(HitCounter, Simple) {
FakeStopWatch stopWatch;
HitCounter counter(&stopWatch, 5);
for (int i = 0; i < 6; ++i)counter.Hit();
ASSERT_EQ(6, counter.TotalHit());
stopWatch.SetToReturn(3);
ASSERT_EQ(6, counter.TotalHit());
counter.Hit();
ASSERT_EQ(7, counter.TotalHit());
stopWatch.SetToReturn(5);
ASSERT_EQ(1, counter.TotalHit());
}
TEST(HitCounter, Increasing) {
FakeStopWatch stopWatch;
HitCounter counter(&stopWatch, 5);
for (int i = 0; i < 10; ++i) {
stopWatch.SetToReturn(i);
for (int j = 0; j <= i; ++j) {
counter.Hit();
}
if (i < 5) {
ASSERT_EQ((i + 1) * (i + 2) / 2, counter.TotalHit());
}
else {
ASSERT_EQ(((i + 1) * (i + 2) - (i - 4)*(i - 3)) / 2, counter
.TotalHit());
}
}
}
} |
s*****B
发帖数: 32 | |
f***b
发帖数: 21 | |
g*******0
发帖数: 20 | 85 前两天电面也被问到了这个题，没看版上的面经，肠子已悔青。
这题相当tricky，用circular buffer并不好做，我最早想到的就是circular buffer，
但是写了一遍，面试官说有bug，fix了面试官说还有bug，这样来来回回了好几趟。主
要得考虑相邻两次hit是不是在一个bucket中，并且相差多远（大于5分钟还是小于5分
钟），不仅得考虑两次hit，还需要考虑getHit与上次hit相差多远（大于5分钟还是小
于5分钟），中途问面试官可不可以用一个background job来清空bucket，被告知不可
以。相比起来应该还是用链表更好写一些。
把所有bug都fix过后，面试官又问在多线程的情况下这段code怎么改，本来应该给所有
变量都加个读写锁的，但是已经没有时间，只有把整个函数都给锁掉。鉴于fix了很多
次bug以及效率很低下的锁，现在只有坐等据信了:(
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
m*****k
发帖数: 18 | |
n****a
发帖数: 195 | |
v*******C
发帖数: 28 | |
w*****x
发帖数: 11 | |
f*****d
发帖数: 2285 | 90 和当年我店面Dropbox的题一样啊。2年了题还没改啊。 |
|
|
T******7
发帖数: 1419 | |
b*********n
发帖数: 1258 | 92 可以在300个counter的同时，再用300个timestamp，把counter and timestamp它们放
到同一个slot
getHit 的时候，把这300个slot加一遍，就可以了
300个slot扫一边，应该很快。
我觉得这个逻辑比较简单。
不知道是否忽略了什么问题。
import java.util.Date;
class Solution {
public static void main(String[] args) throws InterruptedException {
Answer ans = new Answer();
ans.hit();
ans.hit();
ans.hit();
Thread.sleep(1000);
ans.hit();
ans.hit();
System.out.println(ans.getHit());
}
}
class Answer {
Item[] buffer;
public Answer() {
buffer = new Item[300];
for (int i = 0; i < 300; i++) {
buffer[i] = new Item();
}
}
public void hit() {
long now = getCurrentTimeInSecond();
int bucket = (int) (now % 300);
Item item = buffer[bucket];
if (item.timestamp == now) {
item.counter++;
} else {
item.timestamp = now;
item.counter = 1;
}
}
public int getHit() {
long now = getCurrentTimeInSecond();
int sum = 0;
for (int i = 0; i < 300; i++) {
Item item = buffer[i];
if (now - item.timestamp < 300) {
sum += item.counter;
}
}
return sum;
}
public long getCurrentTimeInSecond() {
return new Date().getTime() / 1000;
}
}
class Item {
int counter;
long timestamp;
public Item() {
this.counter = 0;
this.timestamp = 0;
}
}
【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
|
i*****7
发帖数: 92 | |
g*******d
发帖数: 495 | 94 我觉得concurrency不仅涉及正确性的问题，还有就是运行速度。
之前twitter电面我时候遇到的题也是问了concurrency。题目本身是不断插入hashtag
，让随时统计频率最高的。跟这个题一样，有一个插入函数（类似hit)。我的回答是有
一个线程专门负责插入，其它线程给这个线程发送插入的请求。这样需要加锁的部分就
是发送插入请求这块。如果可以用Go的话，直接上channel，无锁搞定（不知道channel
的实现是不是用到锁）。面试官表示满意。
【在 s*****4 的大作中提到】
: Unit test要写到多详细呢 有人可以给个例子吗?
: test cases我只想到这三个:
: 1. last hit和cur hit发生在同一秒
: 2. last hit和cur hit发生在不同秒, 检查结果是否正确的把last hit到cur hit之间
: 的element reset 0
: 3. 同2, 且last hit跟cur hit发生的间隔很大(ex. 30000s), 检查run time, 看是否
: 在reset完300个element后就early return
: concurrency是不是只需要用一个mutex把hit()头尾用mutex.lock(), nutex.unlock()
: 包住就行了? 不是很确定...
|
j********3
发帖数: 33 | 95 我来个python 版本的。
精确度考量： 当前版本精度为一秒。 如果要提高精度可以提高memory或者用queue
log所有的hit timestamp，然后压缩timestamp来减少memory。 tradeoff memory O(N)
instead of constant.
scalability：缩小维度，增加memory 使用 distrubuted array in python:
distarray。
edge case: in real world,应该不用考虑一秒内的request超出max integer，面试官
真的要问的话， 超出的话，可以溢出到下一个bucket
concurrency: 基本for loop in reset() 和 count++的地方都需要加锁了...
import time
N = 300
class Counter:
def __init__(self,lock):
self.last_index = 0
self.last_hit_time = 0
self.total_hit = 0
self.cir_buf = []
self.lock = lock
def reset(self):
cur_time = time.time()
silent_gap = min(cur_time - self.last_hit_time, N)
for i in xrange(silent_gap):
self.last_index = (self.las_index + 1) % N
self.total_hit -= self.cir_buf[self.last_index]
self.cir_buf[self.last_index] = 0
self.last_hit_time = cur_time
def hit(self):
self.lock.acquire()
self.reset()
self.cir_buf[(self.last_index + 1) % N] += 1
self.total_hit += 1
self.lock.release()
def get_hit(self):
return self.total_hit |
