Войти Регистрация
Алгоритмы

177. Чей это был идентификатор в прошлом

Средняя

Каждую секунду с 1-й по n-ю приходит один запрос из списка ops (запрос ops[i] — секунда i + 1):

["CHANGE", name, id] — товар name получает идентификатор id; его прежний id освобождается, а если id был у другого товара, у того id сбрасывается. ["GET", id, time] — какой товар носил id сразу после запроса секунды time (time меньше текущей секунды).

Верните ответы на все GET по порядку: имя товара или строку "404", если id в тот момент был свободен.

В работе: Каталог Ozon: SKU переиспользуют после снятия товара, а поддержке нужно понять, на что ссылался старый заказ.

Пример 1

Ввод
ops = [["CHANGE", "product1", 10], ["CHANGE", "product1", 20], ["GET", 10, 1], ["GET", 10, 3], ["CHANGE", "product2", 20], ["GET", 20, 5]]
Вывод
["product1", "404", "product2"]

После секунды 2 id 10 свободен, а после 5-й id 20 перешёл к product2.

Ограничения

  • 1 ≤ длина ops ≤ 3·10⁵
  • 1 ≤ id ≤ 10⁵
  • Имена — до 10 латинских букв и цифр
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def product_ids(ops):
Бинарный поискХеш-таблицаВерсионированиецельO(n log n)

Источник: Ozon, отборочный контест Route 256, 2024 (репозиторий участника). Условие пересказано своими словами.