c*****n 发帖数: 95 | 1 第一题phone number to words. 被怀疑刷过题,如实回答后直接进入第二题。
design hit logger, return number of hits in last 5 mins.
看到有人被问到这题,大概思路对了,用的rotation array, 但在清空的环节上卡住
了。 哎,还是大意了。
感觉面试的题还是很tricky的。 |
j******o 发帖数: 4219 | 2 别承认刷过题不就行了,难道公司还想找没刷过题还能BUG FREE的人? |
c*****n 发帖数: 95 | 3 很难装没做过吧。。。做没做过,还是很容易看出来的
真的是水涨船高。。。 |
d******e 发帖数: 2265 | 4 这个直接用tail加上一个filter就可以吧。
【在 c*****n 的大作中提到】 : 第一题phone number to words. 被怀疑刷过题,如实回答后直接进入第二题。 : design hit logger, return number of hits in last 5 mins. : 看到有人被问到这题,大概思路对了,用的rotation array, 但在清空的环节上卡住 : 了。 哎,还是大意了。 : 感觉面试的题还是很tricky的。
|
c*****n 发帖数: 95 | 5 class logger{
vector hits(300);
long startTime;
long lastTimeCalled;
public:
logger() {
lastTimeCalled = -1;
startTime = time();
}
void zeroOut(int lapsed) {
int lastPos = lastTimeCalled % 300;
if(lapsed >= 300) {
for(int i = 0; i < hits.size(); i++) {
hits[i] = 0;
}
} else if(lastTimeCalled != -1){
for(int i = lastPos + 1; i < lastPos + lapsed; i++) {
hits[i % 300] = 0;
}
}
}
void logHit() {
long curTime = time() - startTime;
long lapsed = curTime - lastTimeCalled;
curSecond = curTime % 300;
zeroOut(lapsed);
if(curSecond == lastTimeCalled % 300) {
hits[curSecond]++;
} else {
hits[curSecond] = 1;
}
lastTimeCalled = curTime;
}
int getHitLastFiveMin() {
// need to do similar things here
long curTime = time() - startTime;
long lapsed = curTime - lastTimeCalled;
zeroOut(lapsed);
lastTimeCalled = curTime;
int res = 0;
for(int i = 0; i < hits.size(); i++) {
res += hits[i];
}
return res;
}
} |
c*****n 发帖数: 95 | 6 似乎用一个linked list 实现会更简单啊。每个node 都保存一个timestamp |
g****v 发帖数: 971 | 7 楼主能分享下为什么需要清空和怎么清空么?
【在 c*****n 的大作中提到】 : 第一题phone number to words. 被怀疑刷过题,如实回答后直接进入第二题。 : design hit logger, return number of hits in last 5 mins. : 看到有人被问到这题,大概思路对了,用的rotation array, 但在清空的环节上卡住 : 了。 哎,还是大意了。 : 感觉面试的题还是很tricky的。
|
c*****n 发帖数: 95 | 8 已经把代码贴出来了。不过觉得这题用fix length array 实现不是很好。会涉及到清
空的问题,弄起来很麻烦。
比较简单的做法应该用linkedlist ?
每个node保存一个timestamp, 一个头指针,一个尾指针。当要getCounts 时,从头开
始往后扫。如果curTime - timestamp > limit, 就不计数,并且删掉节点。
【在 g****v 的大作中提到】 : 楼主能分享下为什么需要清空和怎么清空么?
|