logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
三哥靠谱不：中国士兵向印度军队要饭 (转载)
avatar
三哥靠谱不：中国士兵向印度军队要饭 (转载)# Joke - 肚皮舞运动
l*n
1 楼
新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
两个function;
void hit()
long getHits() //返回五分钟内hit了几次
avatar
m*c
2 楼
【 以下文字转载自 Military 讨论区 】
发信人: yeting (徐向前), 信区: Military
标 题: 三哥靠谱不：中国士兵向印度军队要饭
发信站: BBS 未名空间站 (Fri Jul 26 14:00:06 2013, 美东)
这个貌似不是土星了
美国之音
07.26.2013
印度最大的通讯社印度报业托拉斯（PTI）7月25日报道说，自四月中印两军在“实控线
”拉达克发生对峙以来，中国军队7月20日再次试图越过位于列城东北部楚玛尔段的国
际边界，在遭遇印度军队后撤离。
报道指出，中国军队越过边界就遭到印度的边防警卫部队的对峙堵截。中国军队声称
他们是执行中国人民解放军总部的指令，前往深入印度境内5公里远的泰伯地区拍照。
中国部队声称这是中国的领土。
在中国军队被堵截返回楚玛尔段国际边界中国境内的时候，需要走一段很长的路，这
个时候，中国士兵的东西已经吃完，于是就要拦截他们的印度士兵给他们一些食物充饥
。可是，印度士兵并没有随身携带食物，就给了中国士兵一些果汁罐头。
在不久以前，楚玛尔段边界已发生了多起中国军队越境事件，其中包括6月17日中国军
队拆除了印方用来监视执行巡逻任务的中国军队的监视摄像头。
楚玛尔段边界位于距列城300公里处，此区域也是中印两国间定义的国际边界，它已经
成为中国首要关注的议题。中国宣称楚玛尔是中方领土，每年都会以派遣直升机越界的
方式“光顾”。去年，人民解放军在楚玛尔拆除了印度军队和印藏边界警察的临时储存
帐篷。
avatar
h*g
3 楼
用static variable吗？

【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
avatar
l*y
4 楼
印度兵的日子也不好过啊。。
avatar
l*n
5 楼
看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
钟的时间窗口。真是一个题什么都涉及到了。

【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
avatar
P*e
6 楼
这幸亏三哥拦下了提前回头了，真走到目的地那不饿死了

【在 m******c 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: yeting (徐向前), 信区: Military
: 标 题: 三哥靠谱不：中国士兵向印度军队要饭
: 发信站: BBS 未名空间站 (Fri Jul 26 14:00:06 2013, 美东)
: 这个貌似不是土星了
: 美国之音
: 07.26.2013
: 印度最大的通讯社印度报业托拉斯（PTI）7月25日报道说，自四月中印两军在“实控线
: ”拉达克发生对峙以来，中国军队7月20日再次试图越过位于列城东北部楚玛尔段的国
: 际边界，在遭遇印度军队后撤离。
avatar
z*8
7 楼
正解
G/Y!也问过类似的题目， circular buffer答出来就基本搞定了

【在 l*n 的大作中提到】
: 看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
: 是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
: 钟的时间窗口。真是一个题什么都涉及到了。
avatar
d*z
8 楼
可能三哥士兵把罐头卖了，回头说给白兔了。
avatar
l*n
9 楼
我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
让我写unit test测试,然后再讨论如何concurrent.
avatar
s*x
10 楼
简直是中印一家亲啊，是不是巡逻的时候还互相打招呼：
来啦？
来了，你们今天怎么走
我们路线是。。。呃，你们带什么好吃的了？
我们的都吃完了。。。你们那？
就水果罐头了，要么？
看着还不错，来几罐吧。回见。
走好
avatar
f*p
11 楼
记得不久前有版友分享g的题目，也是统计hit之类， last 1 min, last 1 hr, last
day 链接找不到了。 那个题也是这个思路吗？

【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
avatar
s*d
12 楼
中方侦察兵就这样取得了印军补给的情报和伙食数据。

【 以下文字转载自 Military 讨论区 】发信人: yeting (徐向前), 信区: Military
标

【在 m******c 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: yeting (徐向前), 信区: Military
: 标 题: 三哥靠谱不：中国士兵向印度军队要饭
: 发信站: BBS 未名空间站 (Fri Jul 26 14:00:06 2013, 美东)
: 这个貌似不是土星了
: 美国之音
: 07.26.2013
: 印度最大的通讯社印度报业托拉斯（PTI）7月25日报道说，自四月中印两军在“实控线
: ”拉达克发生对峙以来，中国军队7月20日再次试图越过位于列城东北部楚玛尔段的国
: 际边界，在遭遇印度军队后撤离。
avatar
z*8
13 楼
对的

【在 f******p 的大作中提到】
: 记得不久前有版友分享g的题目，也是统计hit之类， last 1 min, last 1 hr, last
: day 链接找不到了。 那个题也是这个思路吗？
avatar
X*r
14 楼
显然啊

【在 d****z 的大作中提到】
: 可能三哥士兵把罐头卖了，回头说给白兔了。
avatar
c*p
15 楼
Mark
avatar
H*9
16 楼
原来是这样

【在 s*x 的大作中提到】
: 简直是中印一家亲啊，是不是巡逻的时候还互相打招呼：
: 来啦？
: 来了，你们今天怎么走
: 我们路线是。。。呃，你们带什么好吃的了？
: 我们的都吃完了。。。你们那？
: 就水果罐头了，要么？
: 看着还不错，来几罐吧。回见。
: 走好
avatar
M*r
17 楼

楼主可以写个code参考一下吗，我不是太明白“发现上次时间超过了一秒就重新计数0
”的意思。多谢了！

【在 l*****n 的大作中提到】
: 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
: 时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
: getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
: 让我写unit test测试,然后再讨论如何concurrent.
avatar
t*g
18 楼
无非是黄咖喱多还是红咖喱多之类的。

【在 s**********d 的大作中提到】
: 中方侦察兵就这样取得了印军补给的情报和伙食数据。
:
: 【 以下文字转载自 Military 讨论区 】发信人: yeting (徐向前), 信区: Military
: 标
avatar
l*n
19 楼
新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
两个function;
void hit()
long getHits() //返回五分钟内hit了几次
avatar
y*g
20 楼
我觉得
是三哥被解放军缴邂了。。。回去编到故事。

【在 s*x 的大作中提到】
: 简直是中印一家亲啊，是不是巡逻的时候还互相打招呼：
: 来啦？
: 来了，你们今天怎么走
: 我们路线是。。。呃，你们带什么好吃的了？
: 我们的都吃完了。。。你们那？
: 就水果罐头了，要么？
: 看着还不错，来几罐吧。回见。
: 走好
avatar
l*n
21 楼
看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
钟的时间窗口。真是一个题什么都涉及到了。

【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
avatar
z*8
22 楼
正解
G/Y!也问过类似的题目， circular buffer答出来就基本搞定了

【在 l*n 的大作中提到】
: 看起来容易，做起来不简单啊。getHits的输出都到long级别了，用linkedList来数数
: 是不可能了。只能用static变量按秒进行计数，然后还要有circular buffer来处理5分
: 钟的时间窗口。真是一个题什么都涉及到了。
avatar
l*n
23 楼
我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
让我写unit test测试,然后再讨论如何concurrent.
avatar
f*p
24 楼
记得不久前有版友分享g的题目，也是统计hit之类， last 1 min, last 1 hr, last
day 链接找不到了。 那个题也是这个思路吗？

【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
avatar
z*8
25 楼
对的

【在 f******p 的大作中提到】
: 记得不久前有版友分享g的题目，也是统计hit之类， last 1 min, last 1 hr, last
: day 链接找不到了。 那个题也是这个思路吗？
avatar
c*p
26 楼
Mark
avatar
M*r
27 楼

楼主可以写个code参考一下吗，我不是太明白“发现上次时间超过了一秒就重新计数0
”的意思。多谢了！

【在 l*****n 的大作中提到】
: 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
: 时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
: getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
: 让我写unit test测试,然后再讨论如何concurrent.
avatar
m*k
28 楼
co-ask on this “发现上次时间超过了一秒就重新计数0
0
avatar
l*a
29 楼
数组300 ITEM
每一个对一秒中HIT NUMBER进行计数
每次新hit跟last hit timestamp比较
如果超出了一秒，显然要对last timestamp到现在这段全部清0，再写入本次hit 信息

【在 m*****k 的大作中提到】
: co-ask on this “发现上次时间超过了一秒就重新计数0
: 0
avatar
m*k
30 楼
上一秒的都清0了，还咋统计last 1 min data?
avatar
s*l
31 楼
他们是说 那个static hit 次数清领
不是timestamp
楼上各位牛牛 是这意思把？

【在 m*****k 的大作中提到】
: 上一秒的都清0了，还咋统计last 1 min data?
avatar
s*4
32 楼
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;
}
};
avatar
m*k
33 楼
从last＋ 1开始清0，makes sense.
avatar
t*e
34 楼

我有两个问题关于你的代码：
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
avatar
w*u
35 楼
mark
avatar
n*2
36 楼
mark
avatar
s*4
37 楼
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()
包住就行了? 不是很确定...
avatar
m*n
38 楼
谢谢楼主分享！

【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
avatar
h*s
39 楼
这里精确到秒的意思是不是每秒hit()被调用的次数是可知的？还是说每秒最多只能调
用一次？

【在 l*****a 的大作中提到】
: 数组300 ITEM
: 每一个对一秒中HIT NUMBER进行计数
: 每次新hit跟last hit timestamp比较
: 如果超出了一秒，显然要对last timestamp到现在这段全部清0，再写入本次hit 信息
avatar
m*g
40 楼
蛮难的啊。
avatar
e*m
41 楼
这个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
avatar
d*v
42 楼
Mark
avatar
j*8
43 楼
mark

【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
avatar
e*m
44 楼
还有一个问题，不应该用数组的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
avatar
y*a
45 楼

我看了一下 circular buffer。和你的解法应该殊途同归，不过 cb 更加
系统一些吧。
赞分享。顺求 Google 以前的 hit 题。

【在 l*****n 的大作中提到】
: 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
: 时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
: getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
: 让我写unit test测试,然后再讨论如何concurrent.
avatar
r*e
46 楼
那样会直接清0了。
有一个问题是，经过很长时间的silence 来了个gethit

【在 e***m 的大作中提到】
: 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
: 数组中已有数据，经过很长时间的silent后，来了个hit
avatar
d*n
47 楼
为什么ＬｉｎｋｅｄＬｉｓｔ不行呢？这样做应该比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分
: 钟的时间窗口。真是一个题什么都涉及到了。
avatar
m*1
48 楼
mark
avatar
h*k
49 楼
mark
avatar
s*4
50 楼
的确啊, 谢谢了! 这是个大bug, 奇怪我之前都检查2, 3次了, 怎么没发现呢...

【在 e***m 的大作中提到】
: 这个code有个小问题。gethit()里，应先调time()找出当前时间，再去vector里找对应
: 的hit个数
avatar
s*4
51 楼
这个我不太懂, 是考虑time overflow吗?

【在 e***m 的大作中提到】
: 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
: 数组中已有数据，经过很长时间的silent后，来了个hit
avatar
e*m
52 楼
我的concern是：经过很长的一个silent period, 数组中的所有counter可能因为太久
远了不能用了

【在 s*****4 的大作中提到】
: 这个我不太懂, 是考虑time overflow吗?
avatar
s*4
53 楼
了解~ 我想我的getHit()应该要做类似hit()里做的事, 先把last到cur间的值清零, 再
加总剩下的值, 这样的话应该work?

【在 e***m 的大作中提到】
: 我的concern是：经过很长的一个silent period, 数组中的所有counter可能因为太久
: 远了不能用了
avatar
e*m
54 楼
if cur-300>last
整个数组清零
else
(last-300,cur-300］对应的counters清零
再把cur对应的counter加一

【在 s*****4 的大作中提到】
: 了解~ 我想我的getHit()应该要做类似hit()里做的事, 先把last到cur间的值清零, 再
: 加总剩下的值, 这样的话应该work?
avatar
l*1
55 楼
mark
avatar
H*k
56 楼
mark
avatar
Q*a
57 楼
#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());
}
}
}
}
avatar
s*B
58 楼
mark
avatar
f*b
59 楼
deque能不能用
avatar
g*0
60 楼
前两天电面也被问到了这个题，没看版上的面经，肠子已悔青。
这题相当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了几次
avatar
n*a
62 楼
FPS...
avatar
v*C
63 楼
mark
avatar
m*k
64 楼
co-ask on this “发现上次时间超过了一秒就重新计数0
0
avatar
l*a
65 楼
数组300 ITEM
每一个对一秒中HIT NUMBER进行计数
每次新hit跟last hit timestamp比较
如果超出了一秒，显然要对last timestamp到现在这段全部清0，再写入本次hit 信息

【在 m*****k 的大作中提到】
: co-ask on this “发现上次时间超过了一秒就重新计数0
: 0
avatar
m*k
66 楼
上一秒的都清0了，还咋统计last 1 min data?
avatar
s*l
67 楼
他们是说 那个static hit 次数清领
不是timestamp
楼上各位牛牛 是这意思把？

【在 m*****k 的大作中提到】
: 上一秒的都清0了，还咋统计last 1 min data?
avatar
s*4
68 楼
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;
}
};
avatar
m*k
69 楼
从last＋ 1开始清0，makes sense.
avatar
t*e
70 楼

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
avatar
w*u
71 楼
mark
avatar
n*2
72 楼
mark
avatar
s*4
73 楼
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()
包住就行了? 不是很确定...
avatar
h*s
74 楼
这里精确到秒的意思是不是每秒hit()被调用的次数是可知的？还是说每秒最多只能调
用一次？

【在 l*****a 的大作中提到】
: 数组300 ITEM
: 每一个对一秒中HIT NUMBER进行计数
: 每次新hit跟last hit timestamp比较
: 如果超出了一秒，显然要对last timestamp到现在这段全部清0，再写入本次hit 信息
avatar
m*g
75 楼
蛮难的啊。
avatar
e*m
76 楼
这个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
avatar
d*v
77 楼
Mark
avatar
j*8
78 楼
mark

【在 l*****n 的大作中提到】
: 新鲜出炉的dropbox电话面经， 叫我写个计数函数，返回5分钟内hit()被运行了几次.
: 两个function;
: void hit()
: long getHits() //返回五分钟内hit了几次
avatar
e*m
79 楼
还有一个问题，不应该用数组的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
avatar
y*a
80 楼

我看了一下 circular buffer。和你的解法应该殊途同归，不过 cb 更加
系统一些吧。
赞分享。顺求 Google 以前的 hit 题。

【在 l*****n 的大作中提到】
: 我是以精确到秒的思想解题的，用size 300的array存次数和上次的hit 时间，然后用
: 时间time%300来找到对应的index,如果发现上次时间超过了一秒就重新计数0，然后
: getHits()就把array 扫一遍加起来。 面试官蛮满意的，但是followup 没答很好，先
: 让我写unit test测试,然后再讨论如何concurrent.
avatar
r*e
81 楼
那样会直接清0了。
有一个问题是，经过很长时间的silence 来了个gethit

【在 e***m 的大作中提到】
: 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
: 数组中已有数据，经过很长时间的silent后，来了个hit
avatar
d*n
82 楼
为什么ＬｉｎｋｅｄＬｉｓｔ不行呢？这样做应该比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分
: 钟的时间窗口。真是一个题什么都涉及到了。
avatar
m*1
83 楼
mark
avatar
h*k
84 楼
mark
avatar
s*4
85 楼
的确啊, 谢谢了! 这是个大bug, 奇怪我之前都检查2, 3次了, 怎么没发现呢...

【在 e***m 的大作中提到】
: 这个code有个小问题。gethit()里，应先调time()找出当前时间，再去vector里找对应
: 的hit个数
avatar
s*4
86 楼
这个我不太懂, 是考虑time overflow吗?

【在 e***m 的大作中提到】
: 还有一个问题，不应该用数组的index直接表示时间。请考虑如下情况:
: 数组中已有数据，经过很长时间的silent后，来了个hit
avatar
e*m
87 楼
我的concern是：经过很长的一个silent period, 数组中的所有counter可能因为太久
远了不能用了

【在 s*****4 的大作中提到】
: 这个我不太懂, 是考虑time overflow吗?
avatar
s*4
88 楼
了解~ 我想我的getHit()应该要做类似hit()里做的事, 先把last到cur间的值清零, 再
加总剩下的值, 这样的话应该work?

【在 e***m 的大作中提到】
: 我的concern是：经过很长的一个silent period, 数组中的所有counter可能因为太久
: 远了不能用了
avatar
e*m
89 楼
if cur-300>last
整个数组清零
else
(last-300,cur-300］对应的counters清零
再把cur对应的counter加一

【在 s*****4 的大作中提到】
: 了解~ 我想我的getHit()应该要做类似hit()里做的事, 先把last到cur间的值清零, 再
: 加总剩下的值, 这样的话应该work?
avatar
l*1
90 楼
mark
avatar
H*k
91 楼
mark
avatar
Q*a
92 楼
#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());
}
}
}
}
avatar
s*B
93 楼
mark
avatar
f*b
94 楼
deque能不能用
avatar
g*0
95 楼
前两天电面也被问到了这个题，没看版上的面经，肠子已悔青。
这题相当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了几次
avatar
n*a
97 楼
FPS...
avatar
v*C
98 楼
mark
avatar
w*x
99 楼
mark
avatar
f*d
100 楼
和当年我店面Dropbox的题一样啊。2年了题还没改啊。
avatar
T*7
101 楼
mark
avatar
b*n
102 楼
可以在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了几次
avatar
i*7
103 楼
MARK
avatar
g*d
104 楼
我觉得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()
: 包住就行了? 不是很确定...
avatar
j*3
105 楼
我来个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
相关阅读
中国特色的通缉令[BSSD]上来抱怨下 (转载)电脑和电视的区别 zt卫生间笑话 zz熊猫粪便养出世界最贵茶叶“熊猫茶” (转载)新版本: 一个凤凰生物WSN 的自白 (转载)朋友九年多，搶了我兩個女友老公回国见了前女友 (转载)zt 有扑克贫嘴的签名 (转载)黄瓜真的是用来美容的！俺的披风好看不大学生提问囧倒性学专家:婚后性不和谐可否离婚 (转载)Sarkozy to Obama: I'm fed up with Netanyahu石家庄连发9起老人退休金中现假币事件看看哥怎么剪指甲的Re: 申请浙江版版副爱尔兰1家航空公司计划在飞机上播放色情片 (转载)（ZT）还有几个段子， 呵呵。小明又来新题目啦，等等
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。