Code Logo

Time Based Key-Value Store

Published at24 Jul 2026
Created by
Medium 0 views
Like0

Design a time-based key-value data structure that can store multiple values for the same key at different timestamps and retrieve the value at a given timestamp. Implement the class with two methods: set(key, value, timestamp) stores the key with value at the given timestamp, and get(key, timestamp) returns the value for that key whose timestamp is the greatest less than or equal to the given timestamp. If no such value exists, return an empty string.

The naive approach stores all (timestamp, value) pairs for each key and does a linear scan on get. Binary search improves this to O(log n) per get operation by keeping the timestamps sorted (they are guaranteed to be inserted in increasing order as required by the problem constraints).

The internal data structure is a hash map from key to a list of (timestamp, value) pairs, naturally sorted because timestamps are strictly increasing during set operations. On get, perform binary search on the list to find the rightmost timestamp ≤ the given timestamp. If found, return its value; otherwise return empty string.

Edge cases include getting a timestamp that exactly matches a stored timestamp, getting a timestamp earlier than the earliest stored entry (return empty), and getting a key that was never set (return empty).

Example Input & Output

Example 1
Input
set("a","1",10), get("a",5)
Output
""
Explanation

No entry at or before timestamp 5.

Example 2
Input
set("a","1",10), get("a",15)
Output
"1"
Explanation

Largest timestamp <= 15 is 10.

Example 3
Input
get("nonexistent", 1)
Output
""
Explanation

Key never set.

Example 4
Input
set("a","1",10), get("a",10)
Output
"1"
Explanation

Exact match at timestamp 10.

Example 5
Input
set("a","1",10), set("a","2",20), get("a",15)
Output
"1"
Explanation

At 15, the value from timestamp 10 is valid.

Algorithm Flow

Recommendation Algorithm Flow for Time Based Key-Value Store
Recommendation Algorithm Flow for Time Based Key-Value Store

Solution Approach

Store in hash map key → sorted array of [timestamp, value]. Get uses binary search to find the index of the largest timestamp <= given.

function solution() {
  var store = {};
  return {
    set: function(key, value, timestamp) {
      if (!store[key]) store[key] = [];
      store[key].push([timestamp, value]);
    },
    get: function(key, timestamp) {
      var pairs = store[key];
      if (!pairs) return '';
      var lo = 0, hi = pairs.length - 1;
      while (lo <= hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (pairs[mid][0] === timestamp) return pairs[mid][1];
        if (pairs[mid][0] < timestamp) lo = mid + 1;
        else hi = mid - 1;
      }
      return hi >= 0 ? pairs[hi][1] : '';
    }
  };
}

Set O(1), Get O(log n). Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    private Map<String, List<int[]>> store = new HashMap<>();
    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp, 0});
        List<int[]> list = store.get(key);
        list.get(list.size() - 1)[1] = Integer.parseInt(value);
    }
    public String get(String key, int timestamp) {
        List<int[]> pairs = store.get(key);
        if (pairs == null) return "";
        int lo = 0, hi = pairs.size() - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (pairs.get(mid)[0] == timestamp) return String.valueOf(pairs.get(mid)[1]);
            if (pairs.get(mid)[0] < timestamp) lo = mid + 1;
            else hi = mid - 1;
        }
        return hi >= 0 ? String.valueOf(pairs.get(hi)[1]) : "";
    }
}