Implementing a specific key-value store in O(1)

TL;DR: The code

Seeking for an internship, I stumbled upon thumbtack. To get an interview, I had to solve on of these problems.

To summarize the database problem:
You have a database of (string,integer) (<=> (key,value) )
You need to do all of these operations in less than O(log(N)):

  • Access, insert, update and remove by key
  • Count all the occurrence of a value

Also, you have to support a database transaction system with nested transactions and a optimum memory-consumption.

So, how to do GET,SET,UNSET and NUMEQUALTO with the optimal complexity ?

  1. a dictionary ? All in O(1)…except NUMEQUALTO is in O(N)
  2. a balanced binary search tree ? Nope, it’s worse actually

So I came up with a solution I find worth sharing (and discussing):

  • a dictionary as the database
  • a dictionary as an occurrence counter of each value

The idea to have two structure maintained in sync is, I think, a great solution to this specific problem. But I don’t know if there is a better solution.

So, here is the code, let me know what you think about it: