Неоднозначность структуры данных

Question

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

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

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

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

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

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

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

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

Answer 1

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

 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++;
 }

Answer 2

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

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