Есть ли опыт реализации операций с константным временем выполнения?

Что проверяют

Понимаете ли вы, что O(1) бывает средним, амортизированным и гарантированным, и умеете ли применить это в коде, а не только назвать хэш-таблицу. Следом часто просят спроектировать LRU-кэш с get и put за O(1) или объяснить, почему pop(0) у списка медленный.

Как отвечать

Опишите реальную задачу, где вы заменили линейную операцию на константную, и назовите свои цифры: объём данных, время до и после. Если такой истории нет, честно скажите и покажите понимание на типовых примерах из Python:

• dict и set: поиск, вставка и удаление в среднем за O(1), в худшем случае при массовых коллизиях O(n). Типичная оптимизация: проверку x in list внутри цикла, это O(n) на каждый вызов, заменить на set;
• list: доступ по индексу O(1), append амортизированно O(1) за счёт запаса ёмкости, но insert(0, x) и pop(0) сдвигают весь массив и стоят O(n);
• collections.deque: добавление и удаление с обоих концов за O(1), правильный выбор для очереди;
• LRU-кэш: словарь для поиска плюс двусвязный список для порядка. В Python это OrderedDict с move_to_end и popitem(last=False) или готовый functools.lru_cache;
• стек с минимумом: второй стек хранит текущий минимум, и get_min работает за O(1).

Упомяните и второй смысл термина. В безопасности операция с константным временем это операция, время которой не зависит от данных. Токены и подписи сравнивают через hmac.compare_digest: обычное == может завершиться на первом несовпадении и открывает дорогу атаке по времени.

Где спотыкаются

Называют O(1) у словаря гарантией. Это среднее значение, а хэш-таблица без обработки коллизий, как в учебных примерах с hash(key) % size, просто перезапишет чужой ключ.

Путают амортизированную оценку с худшей: отдельный append может вызвать перевыделение памяти и копирование всего списка.

Считают, что O(1) всегда быстрее O(log n) или даже O(n). На маленьких данных решает константа, и линейный проход по списку из десяти элементов бывает быстрее хэширования сложного ключа.