Time Based Key-Value Store

Thought Process

The Time-Based Key-Value Store problem requires efficiently storing and retrieving values based on timestamps. Here's the approach:

Using Nested Maps - Use a map to store keys, where each key maps to another map of timestamps and values. For the 'set' operation, directly insert the value into the nested map using the key and timestamp. For the 'get' operation, use upper_bound to find the first timestamp greater than the given timestamp. If such a timestamp exists, move the iterator back to get the closest timestamp less than or equal to the given timestamp. If no valid timestamp is found, return an empty string.

Approach 1: Binary Search Implementation

class Pair{

    String val;
    int timestamp;

    Pair(int timestamp,String val){
        this.val = val;
        this.timestamp = timestamp;
    }
}

class TimeMap {

    Map<String,ArrayList<Pair>> mp;
    public TimeMap() {
        mp = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        
        mp.putIfAbsent(key,new ArrayList<>());
        mp.get(key).add(new Pair(timestamp,value));
    }
    
    public String get(String key, int timestamp) {
        
        if(!mp.containsKey(key)){
            return "";
        }
        else{

            List<Pair> list = mp.get(key);
            int start = 0;
            int end = list.size()-1;
            String ans = "";
            while(start<=end){

                int mid = (start+end)/2;
                if(list.get(mid).timestamp == timestamp)
                    return list.get(mid).val;
                
                if(list.get(mid).timestamp < timestamp){
                    ans = list.get(mid).val;
                    start = mid+1;
                }
                else
                    end = mid-1;
            }
            return ans;
        }
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

Approach 2: Using Map of String & TreeMap

class TimeMap {

    Map<String,TreeMap<Integer,String>> mp;
    public TimeMap() {
        mp = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        
        mp.putIfAbsent(key,new TreeMap<>());
        mp.get(key).put(timestamp,value);
    }
    
    public String get(String key, int timestamp) {
        
        if(!mp.containsKey(key)){
            return "";
        }
        else{

            Integer floorKey = mp.get(key).floorKey(timestamp);
            if(floorKey != null)
                return mp.get(key).get(floorKey);
            else
                return "";
        }
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

Code Complexity

Time Complexity: O(log n) per operation

Both approaches achieve logarithmic time complexity for get operations due to binary search (Approach 1) or TreeMap operations (Approach 2).

Space Complexity: O(n)

Both approaches store all key-value pairs, requiring linear space proportional to the number of entries.