The “Time Based Key-Value Store” problem requires creating a data structure where you can store multiple values for the same key but with different timestamps. Later, you can retrieve the value of a key at a specific timestamp, either exactly or the closest one before it. Think of it as a dictionary that not only keeps track of values for keys but also when those values were set.
Brute Force Approach
A brute force approach would use a simple HashMap to store a list of all values and their timestamps for each key. To find the value at a specific timestamp, you iterate through the list and look for the largest timestamp less than or equal to the given timestamp.
import java.util.*;
class TimeMap {
private Map<String, List<Pair>> map;
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
map.putIfAbsent(key, new ArrayList<>());
map.get(key).add(new Pair(timestamp, value));
}
public String get(String key, int timestamp) {
if (!map.containsKey(key)) return "";
String result = "";
for (Pair pair : map.get(key)) {
if (pair.timestamp <= timestamp) {
result = pair.value;
} else {
break;
}
}
return result;
}
private static class Pair {
int timestamp;
String value;
Pair(int timestamp, String value) {
this.timestamp = timestamp;
this.value = value;
}
}
}1. The set method adds a new Pair of timestamp and value to the list for the given key.
2. The get method iterates through the list of Pair objects for the key. It checks if each timestamp is less than or equal to the given timestamp and updates the result.
3. If no suitable timestamp is found, it returns an empty string.
This approach is simple but inefficient because searching through the list for each query takes linear time.
Optimal Algorithm and Data Structure
To solve this efficiently, we use a TreeMap. A TreeMap stores keys in sorted order and allows us to perform a binary search using its floorKey method. The TreeMap stores timestamps as keys and values as the corresponding values for those timestamps.
The problem involves finding the largest timestamp that is less than or equal to the given timestamp. This is a classic range query problem, which is efficiently solved using a TreeMap.
- The sorted nature of the TreeMap allows quick access to keys.
- Its floorKey function can find the largest key less than or equal to the target timestamp in log time.
• Efficiency: TreeMap’s logarithmic operations (put and floorKey) make it ideal for handling large datasets with multiple queries.
• Sorted Property: Since timestamps are inherently ordered, the sorted nature of TreeMap is leveraged.
• Scalability: Works well for dynamic datasets with frequent updates and lookups.
Algorithm Steps
1. Use a TreeMap to store timestamps and their corresponding values for each key.
2. For set, add the timestamp and value to the TreeMap for the given key.
3. For get, use floorKey to find the largest timestamp less than or equal to the target timestamp.
4. If floorKey returns null, return an empty string; otherwise, return the value.
import java.util.*;
class TimeMap {
private Map<String, TreeMap<Integer, String>> map;
public TimeMap() {
map = new HashMap<>();
}
// Add a value for a key at a specific timestamp
public void set(String key, String value, int timestamp) {
map.putIfAbsent(key, new TreeMap<>());
map.get(key).put(timestamp, value);
}
// Get the value of a key at a specific timestamp
public String get(String key, int timestamp) {
if (!map.containsKey(key)) return "";
Integer floorKey = map.get(key).floorKey(timestamp);
return floorKey == null ? "" : map.get(key).get(floorKey);
}
}- Create Definition For HashMap that contains a tree
Create HashMap where key is a string and value is a tree map. The tree map maintains its keys (timestamps) in sorted order, which is critical for efficiently finding the largest timestamp less than or equal to a given timestamp.
2. Design Set Method
public void set(String key, String value, int timestamp) {
map.putIfAbsent(key, new TreeMap<>());
map.get(key).put(timestamp, value);
}- If key is not already present in the map, this statement adds a new TreeMap for the key
- If key is already in the map, this does nothing (avoids overwriting the existing TreeMap).
- Retrieves the TreeMap associated with the given key.
- Adds the timestamp and value as a key-value pair to the TreeMap.
- Since TreeMap automatically keeps its keys sorted, the timestamp will be placed in the correct position.
3. Design Get Method
public String get(String key, int timestamp) {
if (!map.containsKey(key)) return "";
Integer floorKey = map.get(key).floorKey(timestamp);
return floorKey == null ? "" : map.get(key).get(floorKey);
}- If the key does not exist in the map, return an empty string (“”).
- This handles edge cases where queries are made for keys that were never set.
- Retrieves the TreeMap associated with the given key.
- Calls floorKey(timestamp) on the TreeMap
- Finds the largest timestamp that is less than or equal to the given timestamp
- If no such timestamp exists, floorKey returns null.
3. Return the Value:
return floorKey == null ? "" : map.get(key).get(floorKey);• If floorKey is null (no valid timestamp was found), return an empty string.
• Otherwise, use get(floorKey) to fetch the value associated with the found timestamp and return it.
Why the Code is Written This Way
• TreeMap for Sorted Access: Ensures timestamps are automatically sorted for efficient querying.
• HashMap for Constant-Time Key Lookup: Allows quick access to the TreeMap for a given key.
• Separation of Concerns: set and get operations are independently optimized to handle insertion and lookup efficiently.
This approach strikes a balance between simplicity and efficiency, making it a robust choice for the problem.
