popsql interview question

2 files changed, 114 insertions, 0 deletions

diff --git a/misc/popsql/README.md b/misc/popsql/README.md
new file mode 100644
index 0000000..4106d13
--- /dev/null
+++ b/misc/popsql/README.md
@@ -0,0 +1,52 @@
+Challenge: Write an in-memory, key-value value store that can "time travel."
+
+## Basic operations
+
+You should be able to get and set values for arbitrary keys.
+In Ruby, this might look something like:
+
+```ruby
+kv = KV.new
+kv.set('foo', 'bar')
+kv.get('foo')
+=>  "bar"
+```
+
+## Advanced operations
+
+If a timestamp is provided for a given key,
+fetch the value for that key at that particular time.
+If no timestamp is supplied, fetch the most recently set value for that key.
+In Ruby, this might look like:
+
+```ruby
+kv = KV.new
+kv.set('foo', 'bar')
+now = Time.now.to_i
+sleep(1)
+kv.set('foo', 'bar2')
+
+# Fetch the key 'foo' with the 'now' timestamp
+kv.get('foo', now)
+=> "bar"
+
+# Fetch the key 'foo' without a timestamp
+kv.get('foo')
+=> "bar2" # returns the last set value
+```
+
+## Bonus points
+
+Support 'fuzzy' matching on a timestamp.
+
+```ruby
+kv = KV.new
+now = Time.now.to_i
+kv.set('foo', 'bar')
+sleep(3)
+kv.set('foo', 'bar2')
+
+# Fetch the key 'foo' with the 'now' timestamp, plus 2 seconds
+kv.get('foo', now + 2)
+=> "bar" # returns the closest set value to that timestamp, but always in the past
+```
diff --git a/misc/popsql/main.rb b/misc/popsql/main.rb
new file mode 100644
index 0000000..3884e4a
--- /dev/null
+++ b/misc/popsql/main.rb
@@ -0,0 +1,62 @@
+=begin
+O(1) -> key -> location -> bucket
+
+hash(x) -> int
+
+-------
+|     | [ [1, value], [4, value], [40, value] ]
+-------
+|     | [ [1, value] ]
+-------
+|     |
+-------
+=end
+
+def assert_equals(x, y)
+  raise [x, y].inspect unless x == y
+end
+
+class KV
+  def initialize
+    @items = Hash.new do |hash, key|
+      hash[key] = []
+    end
+  end
+
+  def set(key, value)
+    @items[key] << [Time.now.to_i, value]
+  end
+
+  def get(key, at = nil)
+    if at
+      @items[key].bsearch { |(timestamp, _value)| timestamp <= at }&.at(-1)
+    else
+      @items[key].last&.at(-1)
+    end
+  end
+end
+
+kv = KV.new
+kv.set('foo', 'bar')
+
+# challenge 1
+assert_equals(kv.get('foo'), 'bar')
+
+kv.set(42, 'forty two')
+assert_equals(kv.get(42), 'forty two')
+assert_equals(kv.get('baz'), nil)
+
+# challenge 2
+kv.set('foo', 'bar')
+now = Time.now.to_i
+
+sleep(3)
+kv.set('foo', 'bar2')
+
+assert_equals(kv.get('foo'), 'bar2')
+assert_equals(kv.get('foo', now), 'bar')
+
+# challenge 3
+assert_equals(kv.get('foo', now + 1), 'bar')
+assert_equals(kv.get('foo', now + 2), 'bar')
+puts 'yay!'