CODEWITHSUNDEEP
javaalgorithmkotlindata-structures
Ma Long
Ma Long

Reputation: 145

HashMap with O(log(N)) time complexity operations

I took a test on CodeSignal but couldn't solve this problem.

Create a data structure that allows the following operations.
insert x y - insert an object with key x and value y.
get x - return the value of an object with key x.
addToKey x - add x to all keys in map
addToValue y -add y to all values in map.
Time complexity of each operation should be O(log(N))

I was able to make a hash map using array and LinkedList in Java. But I wasn't able to make the time complexity to O(log(N)). In my implementation, the time complexity of insert and get was O(1) (O(N) in worst cases). And the time complexity of addToKey and addToValue was O(N) as I had to iterate all elements to modify keys and values.
What would be a proper data structure for this problem?

Upvotes: 5

Views: 4093

Answers (1)

Eran
Eran

Reputation: 393956

Edited to correct the answer after the helpful comments of The Vee and Tom Elias.

You can't implement addToKey and addToValue by iterating over all the elements, since that requires, as you realized, linear time.

Instead, you can keep a keyDelta and valueDelta int instance variables that hold the value (or the sum of all values) that should be added to each key and value respectively. This is assuming addToKey and addToValue are supposed to add a numeric value to the keys or values.

addToKey and addToValue will only need to update those instance variables, which would take O(1).

The get(x) operation will search for the key x - keyDelta and return its corresponding value after adding valueDelta to it.

Note that add(x,y) also requires a change, since key-value pairs added to the Map should not be affected by previous calls to addToKey or addToValue. This can be achieved if insert(x,y) will actually insert the pair x - keyDelta, y - valueDelta to the map.

If you use a TreeMap to implement the mapping of keys to values, get and insert would take O(logN).

Upvotes: 4

Related Questions