Неопределенность структуры данных

Я не могу понять этот вопрос интервью.

У вас есть массив целых чисел. Вам нужно предоставить другую структуру данных, которая будет иметь следующие функции:

int get(int index)
void set (int index, int value)
void setall(int value)

Они все делают то, что, как вы предполагаете, они должны делать. Ограничение состоит в том, что каждая функция находится в O (1).

Как вы можете создать его так, чтобы setAll был O (1).

Я думал о добавлении другого поля в каждое целое число, которое укажет на целое число, которое будет изменяться каждый раз при вызове setAll. проблема возникает, когда кто-то вызывает setAll, а затем устанавливает тогда get.

Изменить: я изменил имена переменных, чтобы они были понятнее. Кроме того, поскольку вы спросили, get, предположим, вернет массив [i], set (index, value), предположим, чтобы поместить значение в массив [index].

После setall(index, value) вы должны get (get(i) == get(j) == value) для каждого i, j массива.

Ответ 1

Храните поле DateTime (или просто счетчик) с каждым элементом в массиве, переменной setAllValue и переменной setAllDateTime. С каждым набором обновите DateTime/counter элемента. С SetAll обновите значение и DateTime для setAllDateTime.

В get, сравните DateTime SetAll с DateTime элемента, в зависимости от того, что более новое, верните это.

Ответ 2

Как насчет сохранения "номера версии" с каждой переменной, т.е.

 int globalValue, globalVersion;
 int nextVersion;
 int[] localValue, localVersion;

 int get(int i) {
     if (localVersion[i] > globalVersion)
         return localValue[i];
     else
         return globalValue;
 }


 void set(int i, int value) {
     localValue[i] = value;
     localVersion[i] = nextVersion++;
 }

 void setAll(int value) {
     globalValue = value;
     globalVersion = nextVersion++;
 }