1=begin
 2O(1) -> key -> location -> bucket
 3
 4hash(x) -> int
 5
 6-------
 7|     | [ [1, value], [4, value], [40, value] ]
 8-------
 9|     | [ [1, value] ]
10-------
11|     |
12-------
13=end
14
15def assert_equals(x, y)
16  raise [x, y].inspect unless x == y
17end
18
19class KV
20  def initialize
21    @items = Hash.new do |hash, key|
22      hash[key] = []
23    end
24  end
25
26  def set(key, value)
27    @items[key] << [Time.now.to_i, value]
28  end
29
30  def get(key, at = nil)
31    if at
32      @items[key].bsearch { |(timestamp, _value)| timestamp <= at }&.at(-1)
33    else
34      @items[key].last&.at(-1)
35    end
36  end
37end
38
39kv = KV.new
40kv.set('foo', 'bar')
41
42# challenge 1
43assert_equals(kv.get('foo'), 'bar')
44
45kv.set(42, 'forty two')
46assert_equals(kv.get(42), 'forty two')
47assert_equals(kv.get('baz'), nil)
48
49# challenge 2
50kv.set('foo', 'bar')
51now = Time.now.to_i
52
53sleep(3)
54kv.set('foo', 'bar2')
55
56assert_equals(kv.get('foo'), 'bar2')
57assert_equals(kv.get('foo', now), 'bar')
58
59# challenge 3
60assert_equals(kv.get('foo', now + 1), 'bar')
61assert_equals(kv.get('foo', now + 2), 'bar')
62puts 'yay!'