CareerCup

Same idea as dictionary but in addition to the key, record the time it was inserted. You can do this by either using a python tuple or using a separate list which keeps track of the times it inserted. I used the latter approach. I present my solution below.

Solution:

class HistoricalDict:
  def __init__(self):
    self._d = {}

  def set(self, time, key, value):
    if key not in self._d:
      self._d[key] = [[value], [time]]
    else:
      self._d[key][0].append(value)
      self._d[key][1].append(time)


  def get(self, key, time):
    valueList = self._d[key][0][::-1]
    timeList = self._d[key][1][::-1]
    if time < timeList[-1]: # HistoricalDict has not been created
      return None
    else:
      # Scan from latest creation date
      for ind, tempTime in enumerate(timeList):
        if time >= tempTime:
          return valueList[ind]
      return None

  def printHistorialDict(self):
    print(self._d)


hdict = HistoricalDict()
hdict.set(2, 'foo', 1)
hdict.set(4, 'foo', 2)
hdict.printHistorialDict() # {'foo': [[1, 2], [2, 4]]}
print(hdict.get('foo', 5)) # 2
print(hdict.get('foo', 4)) # 2
print(hdict.get('foo', 3)) # 1
print(hdict.get('foo', 2)) # 1
print(hdict.get('foo', 1)) # None
print(hdict.get('foo', 0)) # None

use a bst, each node has time, value.
when a get is called, just find the lower bound for that t value.
O(log n) cost if the bst is kept balanced

This is good solution. One optimization is that instead of searching all the values, we can do Binary search since the values are kept sorted by time.

Why not just write in a regular dictionary with "foo;;WEIRDSEPARATOR;;0" key and thats it :?