Microsoft Interview Question: Describe a data structure for which getValue(int index), setValue(int index, int value), and setAllValues(int value) are all O(1).

Notifications

Microsoft

Describe a data structure for which getValue(int index), setValue(int index, int value), and setAllValues(int value) are all O(1).

Anonymous

Mar 15, 2012

You end up having to build 3 arrays, 1 for the normal array and 2 to track which values have and have not been set since the last setAll().

Anonymous

Apr 8, 2012

It would be more efficient to use a dictionary, which for integers has O(1) insertion and retrieval