Skip to main content

19. Time Based Key-Value Store

mediumAsked at Redis

Implement a KV store that returns the most recent value with timestamp <= query; Redis loves it because it mirrors ZADD + ZREVRANGEBYSCORE patterns for time-series.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement TimeMap with set(key, value, timestamp) and get(key, timestamp) which returns the value associated with the key at the largest timestamp_prev <= timestamp, or empty string if none.

Constraints

  • 1 <= key.length, value.length <= 100
  • 1 <= timestamp <= 10^7
  • Timestamps are strictly increasing per key on set

Examples

Example 1

Input
set('foo','bar',1); get('foo',1)='bar'; get('foo',3)='bar'; set('foo','bar2',4); get('foo',4)='bar2'; get('foo',5)='bar2'
Output
see explanation

Approaches

1. Linear scan from tail

For each key store an array; on get walk from the end until ts <= target.

Time
O(n) per get
Space
O(n)
// Maintain Map<key, [{t, v}]>; on get scan from end.

Tradeoff:

2. Per-key array + binary search

Since set timestamps are strictly increasing, each key's array is already sorted. Binary search for the largest ts <= target. This is exactly the pattern Redis ZSETs serve with ZREVRANGEBYSCORE (-inf, target) WITHSCORES.

Time
O(log n) per get
Space
O(n)
class TimeMap {
  constructor() { this.m = new Map(); }
  set(k, v, t) {
    if (!this.m.has(k)) this.m.set(k, []);
    this.m.get(k).push({ t, v });
  }
  get(k, t) {
    const arr = this.m.get(k);
    if (!arr) return '';
    let lo = 0, hi = arr.length - 1, ans = '';
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid].t <= t) { ans = arr[mid].v; lo = mid + 1; } else hi = mid - 1;
    }
    return ans;
  }
}

Tradeoff:

Redis-specific tips

Redis interviewers want you to map this directly to ZADD key timestamp value + ZREVRANGEBYSCORE for the read; bonus points for mentioning Redis Streams XRANGE for append-only versioned values.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Time Based Key-Value Store and other Redis interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →