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 ?
- a dictionary ? All in O(1)…except NUMEQUALTO is in O(N)
- 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: