Pergunta de entrevista da empresa Microsoft: Describe a data structure for which getValue(int index), setValue(int index, int value), and setAllValues(int value) are all O(1).

Microsoft

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

Sigiloso

15 de mar. de 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().

Sigiloso

8 de abr. de 2012

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