Структура данных истечения времени

Question

В недавнем интервью по кодированию меня попросили реализовать структуру данных хранилища ключей и значений. Implement

size (): Количество элементов в списке.

find (key): Возвращает значение в ключе, в противном случае выдается исключение nosuchelement.

insert (key, timestamp): добавьте или обновите элемент с помощью этого ключа. Если список полон, то ничего не делайте.

• В списке содержится максимальное количество элементов, которое он может содержать
• Каждый элемент вставляется как ключ и значение, продолжительность, после которой он не должен рассматриваться как в список и отметка времени, в которое оно было введено.
• Если список полон, игнорируйте элемент, который пытается добавить, если только он не является дублирующим ключом.
• Если элемент с таким же ключом уже существует, обновите существующее значение и существующую отметку времени
• Как только время превысит отметку времени + продолжительность элемента, не учитывайте его быть частью структуры больше. Это означает, что если список ранее был полным, он больше не является полным.

Мне не удалось найти эффективный способ отслеживания элементов, которые все еще находятся в списке, учитывая, что элементы могут быть извлечены из списка, если их время истекло.

Answer 1

Я думаю, что вы ищете индексированную очередь с приоритетами. По сути, вы создаете очередь с минимальным приоритетом, ключ которой - отметка времени. И вы создаете индекс (по ключу), который отслеживает расположение элементов в очереди с приоритетами.

При каждой операции вы можете удалять элементы с истекшим сроком действия из очереди, например:

while (pq.peek().timestamp < current_time) {
    pq.remove();
}

Сложность этого будет O (k log n), где k - количество удаляемых элементов, а n - общее количество элементов в очереди.

Доступна реализация очереди с индексированными приоритетами. на http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html. Я слышал об этом много хорошего, но сам никогда этим не пользовался.