Datastructure ambiguity

Question

I can't figure this interview question.

You have an array of integers. You need to provide another Data structure that will have these functions:

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

They all do what you guess they're suppose to do. The limitation is that every function is in O(1).

How can you design it so that setAll will be O(1).

I thought about adding another field to each integer, that will point to an integer that will be changed every time setAll is called. the problem comes when someone call setAll and then set then get.

Edit: I changed the names of the variables so it would be clearer. Also, since you asked, get is suppose to return array[i], set(index, value) suppose to put the value value in array[index].

After setall(index, value) you should get (get(i) == get(j) == value) for every i,j in the array.

Answer 1

How about storing a "version number" with each variable, i.e.

 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

Keep a DateTime field ( or simply a counter ) with each element in the array, a setAllValue variable and setAllDateTime variable. With each set, update the DateTime/counter of the element. With SetAll, update the value and DateTime of setAllDateTime.

In get, compare the DateTime of SetAll with DateTime of the element, whichever is newer, return that.