Custom Data Store

We have a product problem to solve that requires us to implement a custom data store for key-value pairs

First, implement a Key-Value store with simple add, get, and delete functions.

We now want to add some advanced functionality to our key value store: keeping track of historical values. Modify the Key-Value Store to keep track of previous values for a given key. Specifically, we want to implement a function get_at_effective_date that takes a key and a specific time, and returns the value for the key at the specified point in time. Here is an example:

// At 7:00 AM, we initialize the key value store kvs = new KeyValueStore()

// At 7:30 AM, we add an entry for the key ‘a’ kvs.add(‘a’, 10)

// At 8:00 AM, we update the entry for the key ‘a’ kvs.add(‘a’, 20)

// At 8:30 AM, we ask for the current value of the key ‘a’ kvs.get(‘a’) // returns 20

// At 8:35 AM, we ask what the value was for the key ‘a’ at 7:35 AM kvs.get_at_effective_date(‘a’, DateTime.parse(‘7:35 AM’)) // returns 10

Here is one way to implement a key-value store with history tracking in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

from datetime import datetime

class KeyValueStore:

  def __init__(self):
    self.db = {}
    self.history = {}

  def add(self, key, value):
    self.db[key] = value
    self.history.setdefault(key, []).append((datetime.now(), value))

  def get(self, key):
    return self.db[key]

  def get_at_effective_date(self, key, date):
    entries = self.history.get(key, [])
    for timestamp, value in entries:
      if timestamp <= date:
        return value
     
    # No earlier entry found  
    return None 

# Example usage:

kvs = KeyValueStore()
kvs.add('a', 10)
kvs.add('a', 20)

print(kvs.get('a')) # 20 

date = datetime.strptime('7:35 AM', '%I:%M %p') 
print(kvs.get_at_effective_date('a', date)) # 10

The key addition is tracking timestamped historical values for each key, then binary searching to find the latest value on or before the requested effective date.

This allows reconstructing the state of the key-value store at any point in time.