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 newidat 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 aget()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)..
I was just asked this question very recently in an Interview. I came up with a hash table implementation. It would solve the problem of running out of the timestamp values but the thread safety feature needs to be implemented (probably using lazy initialization techniques)
Let's say in our class we have a private variable _defaultValue to hold a default value and we also have a private hashtable or dictionary _hashtable. SetAllValues could just set _defaultValue equal to the value passed and _hashtable initialized/set to a new hashtable and discard any reference to the old hash table. SetValue should just add a new value to _hashtable or update the value if the key ( or index) is already present in the _hashtable. GetValue should check whether the key (or index) is present in _hashtable, then return it, else return the value stored in _defaultValue.
This is my first answer on StackOverflow. I am a little lazy in writing up the code. Will probably edit the answer soon.
The interviewer nodded yes to this solution but insisted to implement it without using a hashtable. I guess, he was asking me to give a similar approach as Timothy's answer. And I wasn't able to get it at that moment :(. Anyways, Cheers!
EDIT: Posting the code (in C#)
class MyDataStruct
{
private int _defaultValue;
private Dictionary<int,int> _hashtable;
public MyDataStruct()
{
_defaultValue = 0; // initialize default with some value
_hashtable = new Dictionary<int, int>();
}
public void SetAllValues(int val)
{
_defaultValue = val;
_hashtable = new Dictionary<int, int>();
}
public void SetValue(int index, int val)
{
if (_hashtable.ContainsKey(index))
{
_hashtable.Add(index, val);
}
else
{
_hashtable[index] = val;
}
}
public int GetValue(int index)
{
if (_hashtable.ContainsKey(index))
{
return _hashtable[index];
}
else
{
return _defaultValue;
}
}
}