Запрос алгоритма интервью

Question

Запрос алгоритма интервью

Учитывая постоянные целые числа x и t, напишите функцию, которая не принимает
аргумент и возвращает истину, если функция была вызвана х число
раз в последние т сек.

Это моя реализация псевдокода / C ++ для возможного алгоритма, но я не уверен, что он правильный / эффективный:

const int x;
const int t;
vector<long> v;
boolean countNumberOfTimesBeenCalled(){
int numberOfCallsInLastTSeconds=0;
v.push_back(System.currentTimeInMillis());
for(int x=0; x<v.size();x++){
if((v.at(x)>=(System.currentTimeInMillis()-1000*t))&&(v.at(x)<=System.currentTimeInMillis())
numberOfCallsInLastTSeconds++;
}
if(numberOfCallsInLastTSeconds==x)
return true;
else
return false;
}

Кто-нибудь может предложить альтернативы?

2

algorithm c++pseudocode

Решение

Другие решения

bool calledXTimesInLastTSeconds() {
static deque<long> last_calls;
long time = currentTimeInMillis();

// clear last calls
long last_call_to_consider = time - 1000*t;
while (last_calls.front() < last_call_to_consider)
last_calls.pop_front()

last_calls.push_back(time);
return last_calls.size() == x;
}

Временная сложность амортизируется постоянной.

РЕДАКТИРОВАТЬ: это как проверить именно так х звонки. Даже если вы можете просто изменить это как минимум на x вызовов (путем изменения ==x в >=x), но тогда ответ от Росса Смита будет лучше, поскольку использование памяти имеет постоянный верхний предел.

0

Источник

Accepted Answer

Вам не нужно вести полный журнал всех предыдущих звонков; вам просто нужно знать, как долго длились последние x звонки.

const int x;
const int t;
bool have_we_made_enough_calls_lately() {
static deque<int> times;
times.push_back(current_time_in_msec());
if (times.size() > x)
times.pop_front();
return times.back() - times.front() <= 1000 * t;
}

Изменить: проверяя другие ответы, я понимаю, что вопрос был неоднозначным. Не ясно, хотите ли вы вернуть истину, если по крайней мере х звонит (что я предположил) или именно так х звонки (что предполагали другие).

3