Time Based Key-Value Store
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Store values with timestamps; get(key, t) returns the value set at the latest time not after t.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What structure maps a key to its history?
- Hint 2Within one key's history you need the last timestamp that is not after t.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A diary where you note your phone's wallpaper with the date each time you change it. Someone asks "what was your wallpaper on 14 March?". You do not read every entry. You flip to the middle of the diary, see if that date is before or after 14 March and keep halving, ending on the last entry dated on or before 14 March.
- The obvious way
Scan the whole history for the best match: O(n) per get.
- The key insight
Keep, for each key, a list of (time, value) appended in time order, so it is always sorted. For a get, binary search for the last time that is not after t. Setting is a plain append, getting is O(log n).
- The algorithm
- set: add (time, value) to the end of that key's list.
- get: take that key's list of times (none? answer empty).
- Binary search for the number of times that are <= t; the entry just before that count is the answer.
- Count is 0? Nothing was set by then: answer empty.
Watch it run
Exampleset(foo, bar, 1); set(foo, bar2, 4); get(foo, 3); get(foo, 5); get(foo, 0)
Two sets: foo's diary now has entries at times 1 and 4.
foo: [(1, bar), (4, bar2)]
Where people slip
- "Not after t" includes t itself: count the times <= t (bisect_right), not < t.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from bisect import bisect_right
class TimeMap:
def __init__(self):
self.times = {} # key -> list of times (increasing)
self.values = {} # key -> list of values, same order
def set(self, key, value, timestamp):
self.times.setdefault(key, []).append(timestamp)
self.values.setdefault(key, []).append(value)
def get(self, key, timestamp):
times = self.times.get(key, [])
count = bisect_right(times, timestamp) # how many times are <= timestamp
return self.values[key][count - 1] if count > 0 else ""Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.