Я не могу понять этот вопрос интервью.
У вас есть массив целых чисел. Вам нужно предоставить другую структуру данных, которая будет иметь следующие функции:
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 массива.
Храните поле DateTime (или просто счетчик) с каждым элементом в массиве, переменной setAllValue и переменной setAllDateTime. С каждым набором обновите DateTime/counter элемента. С SetAll обновите значение и DateTime для setAllDateTime.
В get, сравните DateTime SetAll с DateTime элемента, в зависимости от того, что более новое, верните это.
Как насчет сохранения "номера версии" с каждой переменной, т.е.
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++;
}