Количество последних вызовов

Легкая

easy , queue

26 February 2024

Описание задачи #

Вам дан класс RecentCounter, который подсчитывает количество последних вызовов за определенный период времени. Реализуйте этот класс.

Конструктор RecentCounter инициализирует счетчик с нулевым количеством последних вызовов.
Класс имеет метод ping, который принимает в качестве аргумента параметр t (время в миллисекундах последнего вызова) и в качестве ответа возвращает количество вызовов, произошедших за последние 3000 мс.

Гарантируется, что каждый вызов ping использует строго большее значение t, чем предыдущий вызов.

Ограничения #

Значение t находится в диапазоне от 1 до 10⁹.
Каждый пример будет вызывать ping со строго возрастающими значениями t.
Для проверки будет совершено не более 10⁴ вызовов метода ping.

Примеры #

```
counter := Constructor()

counter.Ping(1)
counter.Ping(100)
counter.Ping(3001)
counter.Ping(3002)
counter.Ping(3003)
```
Ответ: 4

Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [100, 3001, 3002, 3003].
```
counter := Constructor()

counter.Ping(1)
counter.Ping(100)
counter.Ping(3001)
```
Ответ: 3

Пояснение: За последние 3000 мс было сделано 4 вызова в следующее время [1, 100, 3001].

Решение #

Эта задача решается буквально в несколько строчек.

Для хранения вызовов определим массив calls внутри класса, который при инициализации экземпляра получает значение пустого массива.

Далее в реализации метода ping сначала надо добавить время нового вызова в массив calls, а потом удалить из начала все элементы, которые вываливаются из интервала в 3000 миллисекунд, тем самым реализовав простую очередь. В конце нужно лишь вернуть длину оставшегося массива.

package number_of_recent_calls

type RecentCounter struct {
	calls []int
}

func Constructor() RecentCounter {
	return RecentCounter{
		calls: []int{},
	}
}

func (this *RecentCounter) Ping(t int) int {
	this.calls = append(this.calls, t)

	for this.calls[0] < t-3000 {
		this.calls = this.calls[1:]
	}

	return len(this.calls)
}

export class RecentCounter {
    calls: number[]

    constructor() {
        this.calls = []
    }

    ping(t: number): number {
        this.calls.push(t)

        while (this.calls[0] < t - 3000) {
            this.calls.shift()
        }

        return this.calls.length;
    }
}

Оценка сложности #

По времени

Основная временная сложность нашего метода ping заключается в цикле, который в худшем случае будет выполнять 3000 итераций для извлечения всех устаревших элементов, а в лучшем случае — одну итерацию. Исходя из этого сложность равна O(3000) = O(1).

По памяти

Сложность O(1), так как максимальная длина нашего массива вызовов — 3000 элементов. По условию задачи, каждое новое значение в нем является целым числом и строго больше предыдущего, поэтому мы точно можем определить максимальный размер массива.

Оригинал задачи на Leetcode

Algorithmics