Definition
- Time-Based Key-Value Store – set a value for a key at a given timestamp; get the value that was current at or before a query timestamp.
- Internal structure – a HashMap from each key to a list of (timestamp, value) pairs in increasing timestamp order.
- Set operation – appends a new entry in O(1) amortized because timestamps arrive in increasing order.
- Get operation – binary-searches the list for the largest timestamp not exceeding the query (a floor search).
- Complexity – O(1) amortized set, O(log n) get for a key with n entries.
The National Bank of India records the published interest rate for each product every time it changes, stamped with the date and time. Later, an auditor asks what the rate was as of last Tuesday noon. The clerk flips to the product's history, which is sorted by time, and quickly jumps to the latest entry on or before Tuesday noon rather than reading the whole history.
Understanding the Concepts
What is a Time-Based Key-Value Store?
- A time-based key-value store supports two operations:
- set(key, value, timestamp): store the value for the key at the given timestamp.
- get(key, timestamp): return the value for the key with the largest timestamp that is less than or equal to the given timestamp.
This is a point-in-time lookup over a versioned history.
package com.bank.service;
import java.util.*;
public class TimeBasedKVStore {
private Map<String, List<int[]>> store; // key -> list of [timestamp, value]
public TimeBasedKVStore() {
store = new HashMap<>();
}
public void set(String key, int value, int timestamp) {
store.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp, value});
}
public int get(String key, int timestamp) {
List<int[]> history = store.get(key);
if (history == null) return -1; // no history for this key
int lo = 0, hi = history.size() - 1;
int result = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (history.get(mid)[0] <= timestamp) {
result = history.get(mid)[1]; // candidate
lo = mid + 1; // try to find a later one
} else {
hi = mid - 1; // too late, look earlier
}
}
return result;
}
public static void main(String[] args) {
TimeBasedKVStore store = new TimeBasedKVStore();
store.set("savings_rate", 350, 100); // 3.50% at time 100
store.set("savings_rate", 400, 200); // 4.00% at time 200
store.set("savings_rate", 375, 300); // 3.75% at time 300
System.out.println("Rate at time 150: " + store.get("savings_rate", 150)); // 350
System.out.println("Rate at time 250: " + store.get("savings_rate", 250)); // 400
System.out.println("Rate at time 350: " + store.get("savings_rate", 350)); // 375
System.out.println("Rate at time 50: " + store.get("savings_rate", 50)); // -1
}
}
Rate at time 150: 350
Rate at time 250: 400
Rate at time 350: 375
Rate at time 50: -1
Why does the list stay sorted automatically?
In the classic interview framing, timestamps for a given key arrive in strictly increasing order. Since set() always appends to the end of the list, the list stays sorted without any extra work.
// Timestamps arrive in order: 100, 200, 300
// set("rate", 350, 100) -> history: [[100,350]]
// set("rate", 400, 200) -> history: [[100,350],[200,400]]
// set("rate", 375, 300) -> history: [[100,350],[200,400],[300,375]]
// Always sorted by timestamp because appending in order
How does the floor binary search work?
The get() operation finds the largest timestamp <= the query. This is a floor search. When the midpoint timestamp is <= the query, it is a valid candidate, so you record it and move right to look for an even later valid entry. When the midpoint exceeds the query, move left.
// Floor search walkthrough: history timestamps = [100, 200, 300], query = 250
// lo=0, hi=2
// mid=1: timestamp=200 <= 250 -> result=400, lo=2
// mid=2: timestamp=300 > 250 -> hi=1
// lo=2 > hi=1 -> stop
// result = 400 (value at timestamp 200)
How is this different from a standard binary search?
A standard binary search looks for an exact match. The floor search looks for the largest value that does not exceed the query. The key difference is that on a match (<= query), you record it as a candidate and continue searching right, because there might be a later entry that is also valid.
| Aspect | Exact Binary Search | Floor Binary Search | |---|---|---| | Goal | Find exact value | Find largest value <= query | | On match | Return immediately | Record candidate, continue right | | On miss (too large) | Move left | Move left | | No match | Return -1 | Return last recorded candidate |
// Exact search: if (arr[mid] == target) return mid;
// Floor search: if (arr[mid] <= target) { result = mid; lo = mid + 1; }
What if timestamps arrive out of order?
If timestamps can arrive out of order, appending does not keep the list sorted. You would need to insert at the correct position (binary search for insertion point) or use a TreeMap
// Out-of-order handling option 1: insertion sort
// Binary search for the insertion point and insert there
// set becomes O(n) in the worst case
// Out-of-order handling option 2: TreeMap per key
// TreeMap<Integer, Integer> history = new TreeMap<>();
// history.put(timestamp, value);
// get: history.floorEntry(queryTimestamp)
// Both set and get are O(log n)
What are the edge cases?
If no value exists for the key at all, return -1 (or empty string). If every stored timestamp is later than the query, no valid entry exists and the result is -1. If the query exactly matches a stored timestamp, that entry's value is returned.
package com.bank.service;
public class TimeKVEdgeCases {
public static void main(String[] args) {
TimeBasedKVStore store = new TimeBasedKVStore();
// No history
System.out.println(store.get("unknown", 100)); // -1
store.set("rate", 500, 10);
// Query before first entry
System.out.println(store.get("rate", 5)); // -1
// Exact match
System.out.println(store.get("rate", 10)); // 500
}
}
-1
-1
500
What are common mistakes?
The most common mistake is getting the floor boundary logic wrong: using strict < instead of <= in the comparison, which misses exact matches.
// WRONG: strict less-than misses exact matches
if (history.get(mid)[0] < timestamp) { ... } // query=200, entry=200 is missed
// CORRECT: less-than-or-equal catches exact matches
if (history.get(mid)[0] <= timestamp) { result = ...; lo = mid + 1; }
Another mistake is returning the last entry unconditionally instead of initializing result to -1, which gives a wrong answer when all entries are after the query.
When should you use this technique?
Use a time-based key-value store for any versioned data that needs point-in-time queries. In banking, this applies to interest-rate histories, exchange-rate histories, account balance snapshots, and any audit trail where you need to know what value was in effect at a specific moment.
package com.bank.service;
public class InterestRateAudit {
public static void main(String[] args) {
TimeBasedKVStore rateStore = new TimeBasedKVStore();
rateStore.set("home_loan", 850, 20230101); // 8.50%
rateStore.set("home_loan", 825, 20230401); // 8.25%
rateStore.set("home_loan", 800, 20230701); // 8.00%
// Auditor asks: what was the rate on June 15, 2023?
int rateOnJune15 = rateStore.get("home_loan", 20230615);
System.out.println("Home loan rate on 2023-06-15: " + rateOnJune15 + " bps");
}
}
Home loan rate on 2023-06-15: 825 bps
What should a senior engineer know?
A senior engineer should explain the floor-search boundary logic precisely, the assumption that timestamps arrive in order, and the TreeMap alternative for out-of-order timestamps. They should also note that in production, versioned data often uses event sourcing or temporal database features (like PostgreSQL's temporal tables) rather than a hand-rolled store.
What are common interview follow-up questions?
- Interviewers commonly ask:
- What if timestamps arrive out of order? (Use insertion sort or TreeMap.)
- Time complexity? (O(1) set, O(log n) get.)
- How do you handle the case where no value exists before the query time? (Return empty or -1.)
- What if you need to delete values? (Mark entries as deleted and handle during floor search.)
Visual Overview
Time-Based Key-Value Store:
HashMap<String, List<[timestamp, value]>>
┌──────────────────────────────────┐
│ "savings_rate" → [ │
│ [100, 350], │
│ [200, 400], │
│ [300, 375] │
│ ] │
└──────────────────────────────────┘
get("savings_rate", 250):
Floor binary search on [100, 200, 300]
┌─────────────────────────────────┐
│ lo=0, hi=2 │
│ mid=1: ts=200 <= 250 │
│ result=400, lo=2 │
│ mid=2: ts=300 > 250 │
│ hi=1 │
│ lo > hi → stop │
│ Return 400 (rate at ts=200) │
└─────────────────────────────────┘
Key Takeaway
A time-based key-value store lets you set a value for a key at a specific timestamp and later query the value that was in effect at or before any given time. Internally it is a HashMap from each key to a list of (timestamp, value) pairs kept in increasing timestamp order. Set appends in O(1), and get binary-searches the list for the largest timestamp not exceeding the query.
The floor binary search is the core of the get operation. When the midpoint timestamp is at most the query, you record it as a candidate and move right to look for a later valid entry. When it exceeds the query, you move left. Getting this boundary logic wrong by even one comparison returns the wrong historical value, which in an audit context is unacceptable.
The assumption that timestamps arrive in increasing order is what makes appending keep the list sorted for free. If timestamps can arrive out of order, use a TreeMap per key instead, which keeps entries sorted automatically with O(log n) set and floorEntry for the get.
At the National Bank of India, interest rates for products change over time, and the full history is retained for dispute resolution. Modeling each product's rate history as a time-sorted list and binary-searching it turns what would be a long scan into a fast logarithmic jump. This keeps auditor tooling responsive even when thousands of point-in-time checks run against long histories.
Remember one sentence: store each key's history sorted by time and binary-search for the floor entry to answer point-in-time lookups in O(log n).
---