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

17

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

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

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

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

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

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

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

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

    
задан Eyal 02.05.2011 в 14:32
источник
  • Что такое i в наборе и множестве? –  Felix Kling 02.05.2011 в 14:35
  • Я предполагаю, что n = длина массива, где эффективность равна O (n)? –  Nathan Fig 02.05.2011 в 14:35
  • почему возникла бы проблема, если кто-то установил callet setAll, а затем установил, а затем получил? (в этом порядке, по-видимому). Кроме того, похоже, что это вопрос домашнего задания, а не тот, который принадлежит в разделе вопросов интервью. –  Timothy Groote 02.05.2011 в 14:37
  • Является ли этот вопрос интервью? на какую позицию вы претендовали? Это кажется более сложным и продвинутым, чем другие вопросы интервью. Должен ли я знать о параллелизме, временной отметке и т. Д.? Поскольку я не знаю никого из них! –  Hengameh 24.07.2015 в 02:39

2 ответа

11

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

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

    
ответ дан Sanrag Sood 02.05.2011 в 14:41
источник
  • Спасибо! Так просто.. –  Eyal 02.05.2011 в 16:41
  • @ Решение Хаммара, использующее номер версии, вероятно, лучше. Проблема с метками времени заключается в том, что вы полагаетесь на отсутствие двух изменений с одинаковой меткой времени. Это определенно зависит от частоты изменений и разрешения вашей метки времени. Например, Windows известна своей низкой точностью. –  Matthieu M. 02.05.2011 в 16:51
  • @Matthieu @Hammer Я думаю, что в общем, вы можете выбрать ответ, который помог вам больше всего, потому что вы задали вопрос, и вы ищете что-то конкретное. В этом случае Хаммер действительно дал очень хорошее решение, полный ответ, я согласен. Но все, что мне было нужно, это то, что сказал Санраг Суд. Только идея :) Опять же, это не значит, что ответ Хаммера не был хорош :) Это здорово! –  Eyal 04.05.2011 в 08:04
31

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

 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++;
 }
    
ответ дан hammar 02.05.2011 в 14:41
источник
  • Спасибо! Это просто здорово .. –  Eyal 02.05.2011 в 16:40
  • @Eyal: в зависимости от количества обновлений не забывайте иметь дело с циклом версии (обратно в 0 для unsigned и становиться отрицательным для подписанных). –  Matthieu M. 02.05.2011 в 16:49
  • Проблема заключается в том, что set (i) не установлен (i, value) :-) –  May 2 '11 at 17:06 02.05.2011 в 19:06
  • вы можете комбинировать оба ответа, используя временную метку времени эпохи вплоть до наносекундной точности, так как никакие 2 команды не будут завершены на той же наносекунде. это в основном простой MVCC –  Asaf 02.05.2011 в 21:17
  • @Moron: Я предполагаю, что это была опечатка. –  hammar 02.05.2011 в 23:18
Показать остальные комментарии