Interview question: data structure to set all values in O(1)

How about an array of tuples {timestamp, value}, with an additional {timestamp, value} called all. Since you only care about the relative time of insertions, you can use a monotonically increasing id for the values of timestamp:

type Entry {
  int timestamp, 
  int value
}

type structure {
    int     id
    Entry   all
    Entry[] array
}

Initialise all fields to 0. Then the following should work for you:

• setValue(index i, value v):

  array[i] = {id++, value}
  

• value getValue(index i)

  if(all.timestamp > array[i].timestamp) return all.value
  else return array[i].value
  

• setAll(value v)

  all = {id++, value}
  

A problem with this approach is that eventually you'll run out of ids for timestamp, and might wrap around. If you chose a 64 bit value to store timestamps, then this gives you 18,446,744,073,709,551,616 insertions or setAlls before this happens. Depending on the expected use of the datastructure, an O(n) cleanup phase might be appropriate, or you could just throw an exception.

Another issue that might need to be considered is multi-threading. Three obvious problems:

• if id++ isn't atomic and two threads obtained a new id at the same time then you could get two entries with the same id.
• if the incrementation of id and the assignment of the created tuple aren't atomic together (they're probably not) and there were two simultaneous inserts, then you could get a race condition where the older id wins.
• if the assignment of the tuple isn't atomic, and there's an insert() at the same time as a get() then you might end up in a position where you've got say {new_id, old_value} in the array, causing the wrong value to be returned.

If any of these are problems, the absolute easiest solution to this is to put "not thread safe" in the documentation (cheating). Alternatively, if you can't implement the methods atomically in your language of choice, you'd need to put some sort of synchronisation locks around them.

I got the same question in one of the technical interviews.
Here is my complete ready-to-use Java-implementation including the test cases.

The key idea is to keep the value of setAll() in special variable (e.g. joker) and then trace the change of this value in a proper way.

In order to keep the code clean, some access modifiers have been abolished.

Node class:

import java.time.LocalDate;

class Node {

    int value;
    LocalDate jokerSetTime;

    Node(int val, LocalDate jokSetTime) {
        value = val;
        jokerSetTime = jokSetTime;
    }
}

DS class:

class DS {

    Node[] arr;

    DS(int len) {
        arr = new Node[len];
    }
}

DataStructure class:

import java.time.LocalDate;

class DataStructure {

    private boolean isJokerChanged;
    private Integer joker;
    private LocalDate jokerSetTime;
    private DS myDS;

    DataStructure(int len) {
        myDS = new DS(len);
    }

    Integer get(int i) {

        Integer result;

        if (myDS.arr.length < i) {
            return null;
        }

        // setAll() has been just called
        if (isJokerChanged) {
            return joker;
        }

        if (myDS.arr[i] == null) {

            // setAll() has been previously called
            if (joker != null) {
                result = joker;
            } else {
                result = null;

            }

        } else if (myDS.arr[i].jokerSetTime == jokerSetTime) {
            // cell value has been overridden after setAll() call
            result = myDS.arr[i].value;
        } else {
            result = joker;
        }

        return result;
    }

    void setAll(int val) {
        isJokerChanged = true;
        joker = val;
        jokerSetTime = LocalDate.now();
    }

    void set(int i, int val) {
        isJokerChanged = false;
        myDS.arr[i] = new Node(val, jokerSetTime);
    }
}

Main class:

class Main {

    public static void main(String[] args) {

        DataStructure ds = new DataStructure(100);

        Integer res;

        res = ds.get(3);

        ds.set(3, 10);

        res = ds.get(3);

        ds.setAll(6);

        res = ds.get(3);

        res = ds.get(15);

        ds.set(4, 7);

        res = ds.get(4);

        res = ds.get(3);

        ds.setAll(6);

        ds.set(8, 2);

        res = ds.get(3);
    }
}

Update:
The code has been updated. The previous implementation didn't take into account the case when setAll() is called twice in a row with the same value and is followed by set(x), get(y), e.g.: setAll(100), set(3, 1), setAll(100), set(5, 3), get(3).

The use of timestamp approach has been added to allow distinguishing between different setAll() calls with identical values.

P.S. This implementation is not a thread safe.

How about an array of pointers to a single common value? Set the value, and all references will point to the single changed value in O(1)..