Как реализовать операции get, set, setAll за константное время?

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

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

Как отвечать

Идея: не перезаписывать данные, а помнить, что случилось позже, конкретный set или последний setAll. Для этого нужен монотонный счётчик времени.

• set(i, v): увеличиваем счётчик и кладём в ячейку пару (v, time);
• setAll(v): увеличиваем счётчик и запоминаем all_value и all_time. Больше ничего не трогаем;
• get(i): если ячейки нет или её время меньше all_time, возвращаем all_value, иначе значение из ячейки.

class Store:
    def __init__(self):
        self.data = {}
        self.clock = 0
        self.all_value = None
        self.all_time = -1

    def set(self, i, v):
        self.clock += 1
        self.data[i] = (v, self.clock)

    def set_all(self, v):
        self.clock += 1
        self.all_value, self.all_time = v, self.clock

    def get(self, i):
        item = self.data.get(i)
        if item is None or item[1] < self.all_time:
            return self.all_value
        return item[0]

Все три операции делают постоянное число шагов. Если ключи это индексы от 0 до n, словарь заменяется списком. Целые в Python не переполняются, так что счётчик сбрасывать не нужно.

Альтернатива: на setAll заменять словарь новым пустым. Это работает, но освобождение старого словаря в CPython стоит O(n), константа тут только амортизированная. И оговорите, что dict даёт O(1) в среднем, а не в худшем случае.

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

Внутри setAll пишут [value] * size. Выглядит как одна строка, но это O(n) на каждый вызов.

Держат флаг «был setAll» вместо времени. Тогда set после setAll либо теряется, либо ломает остальные ячейки: get возвращает общее значение даже для ячейки, записанной позже.

Не обсуждают get для ячейки, в которую никогда не писали. До первого setAll нужно договориться, что возвращать: None, значение по умолчанию или исключение.