Solution For Time Based Key Value Store

Problem: Time Based Key Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the value of the key at a certain time.

Implement the TimeMap class:

TimeMap() Initializes the object of the data structure.
void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
String get(String key, int timestamp) Returns a value such that set was called previously with the key key and the timestamp timestamp. If there are multiple such values, it returns the one with the largest timestamp that is less than or equal to timestamp. If there are no values, it returns “”.

Example 1:

Input
[“TimeMap”, “set”, “get”, “get”, “set”, “get”, “get”] [[], [“foo”, “bar”, 1], [“foo”, 1], [“foo”, 3], [“foo”, “bar2”, 4], [“foo”, 4], [“foo”, 5]] Output
[null, null, “bar”, “bar”, null, “bar2”, “bar2”]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set(“foo”, “bar”, 1); // store the key “foo” and value “bar” along with timestamp = 1
timeMap.get(“foo”, 1); // return “bar”
timeMap.get(“foo”, 3); // return “bar”, since there is no value corresponding to “foo” at timestamp 3 and the closest previous value is at timestamp 1
timeMap.set(“foo”, “bar2”, 4); // store the key “foo” and value “bar2” along with timestamp = 4
timeMap.get(“foo”, 4); // return “bar2”
timeMap.get(“foo”, 5); // return “bar2”

Constraints:

1 <= key.length, value.length <= 100
1 <= timestamp <= 10^7
All the strings of key and value and the timestamp will be lowercase English letters and integers in the range [a-z, 0-9].

Solution:

The approach to solve this problem is to create a hashmap where each key will point to a list of pairs where each pair will have two values – value and timestamp.

During set operation, we will create a new timestamp-value pair and append it to the corresponding key in the hashmap.

During get operation, we will take each pair corresponding to the key and traverse them to find the most significant pair that has a timestamp less than or equal to the required timestamp.

Below is the implementation of the TimeMap class:

class TimeMap {

Map<String, List<Pair<Integer, String>>> map;

/** Initialize your data structure here. */
public TimeMap() {
    map = new HashMap<>();
}

public void set(String key, String value, int timestamp) {
    if(!map.containsKey(key)) {
        map.put(key, new ArrayList<>());
    }
    map.get(key).add(new Pair<>(timestamp, value));
}

public String get(String key, int timestamp) {
    List<Pair<Integer, String>> list = map.get(key);
    if(list == null) {
        return "";
    }
    int left = 0;
    int right = list.size() - 1;
    while(left <= right) {
        int mid = (left + right) / 2;
        Pair<Integer, String> pair = list.get(mid);
        if(pair.getKey() == timestamp) {
            return pair.getValue();
        }
        if(pair.getKey() < timestamp) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if(right < 0) {
        return "";
    }
    return list.get(right).getValue();
}

}

Complexity Analysis:

Time Complexity: The set operation will take O(1) time to insert a new key-value pair in the hashmap. The get operation will take O(logn) time to find the required value, where n is the total number of pairs corresponding to the key in the hashmap.

Space Complexity: The space required to store the hashmap will be O(nm), where n is the number of keys and m is the average number of pairs corresponding to each key.

Step by Step Implementation For Time Based Key Value Store

import java.util.HashMap;
import java.util.Map;

// This class implements a time-based key-value store.
// All keys and values are stored in a HashMap.
// The key is a String, and the value is an Integer.
public class TimeBasedKeyValueStore {
    
    private Map map;
    
    public TimeBasedKeyValueStore() {
        map = new HashMap<>();
    }
    
    // This method sets the value for the key at the given timestamp.
    public void set(String key, Integer value, Integer timestamp) {
        map.put(key + "-" + timestamp, value);
    }
    
    // This method returns the value for the key at or before the given timestamp.
    public Integer get(String key, Integer timestamp) {
        // We need to find the largest timestamp that is less than or equal to the given timestamp.
        // We can do this by iterating through the HashMap in reverse order.
        for (int i = timestamp; i >= 0; i--) {
            // If the map contains the key at this timestamp, return the value.
            if (map.containsKey(key + "-" + i)) {
                return map.get(key + "-" + i);
            }
        }
        
        // If we reach this point, it means that the key does not exist at any timestamp <= the given timestamp.
        return null;
    }
}

class TimeMap:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.time_map = collections.defaultdict(list)
        

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.time_map[key].append((timestamp, value))
        

    def get(self, key: str, timestamp: int) -> str:
        A = self.time_map.get(key, None)
        if A is None: return ""
        i = bisect.bisect(A, (timestamp, chr(127)))
        return A[i-1][1] if i else ""

var TimeMap = function() {
    this.map = {};
};

/** 
 * @param {string} key 
 * @param {string} value 
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function(key, value, timestamp) {
    //if key not in map, set it equal to an empty array
    if (!(key in this.map)) {
        this.map[key] = [];
    }
    //push value and timestamp into array for that key
    this.map[key].push([value, timestamp]);
};

/** 
 * @param {string} key 
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function(key, timestamp) {
    //if key not in map, return empty string
    if (!(key in this.map)) {
        return "";
    }
    //get the array for that key
    let array = this.map[key];
    //binary search for the timestamp in the array
    let left = 0;
    let right = array.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        //if timestamp is equal to mid timestamp, return mid value
        if (array[mid][1] === timestamp) {
            return array[mid][0];
        //if timestamp is less than mid timestamp, search left side of array
        } else if (timestamp < array[mid][1]) {
            right = mid - 1;
        //if timestamp is greater than mid timestamp, search right side of array
        } else {
            left = mid + 1;
        }
    }
    //if timestamp not found, return value of greatest timestamp less than given timestamp
    return array[right][0];
};

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

class TimeMap {
public:
    /** Initialize your data structure here. */
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        // If key doesn't exist, create it.
        if (m.find(key) == m.end()) {
            m[key] = {};
        }
        // Add value to key's vector with given timestamp.
        m[key].push_back({timestamp, value});
    }
    
    string get(string key, int timestamp) {
        // If key doesn't exist, return empty string.
        if (m.find(key) == m.end()) {
            return "";
        }
        // Get reference to key's vector.
        auto& v = m[key];
        // Binary search timestamp in vector.
        int i = binarySearch(v, timestamp);
        // If timestamp isn't found, return empty string.
        if (i == -1) {
            return "";
        }
        // Otherwise, return value with largest timestamp <= given timestamp.
        return v[i].second;
    }
    
private:
    unordered_map>> m;
    
    // Binary search timestamp in vector. Returns index of largest timestamp <= given timestamp.
    int binarySearch(vector>& v, int timestamp) {
        int left = 0;
        int right = v.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (v[mid].first == timestamp) {
                return mid;
            }
            else if (v[mid].first < timestamp) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        // If timestamp isn't found, return index of largest timestamp <= given timestamp.
        return right;
    }
};

/**
 * 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);
 */

using System;
using System.Collections.Generic;

public class TimeMap {

    Dictionary> map;
    
    /** Initialize your data structure here. */
    public TimeMap() {
        map = new Dictionary>();
    }
    
    public void Set(string key, string value, int timestamp) {
        // check if key exists
        if (!map.ContainsKey(key)) {
            // if key does not exist, create key with empty list
            map.Add(key, new List());
        }
        
        // add new Pair to key's list
        map[key].Add(new Pair(value, timestamp));
    }
    
    public string Get(string key, int timestamp) {
        // check if key exists
        if (!map.ContainsKey(key)) {
            // if key does not exist, return empty string
            return "";
        }
        
        // get key's list
        List list = map[key];
        
        // check if list is empty
        if (list.Count == 0) {
            // if list is empty, return empty string
            return "";
        }
        
        // binary search list for timestamp
        int start = 0;
        int end = list.Count - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (list[mid].timestamp == timestamp) {
                // if timestamp is found, return value
                return list[mid].value;
            }
            else if (list[mid].timestamp < timestamp) {
                // if timestamp is greater than mid's timestamp, search right half of list
                start = mid + 1;
            }
            else {
                // if timestamp is less than mid's timestamp, search left half of list
                end = mid - 1;
            }
        }
        
        // timestamp not found, return value with greatest timestamp less than given timestamp
        return list[end].value;
    }
    
    // Pair class to store value and timestamp together
    private class Pair {
        public string value;
        public int timestamp;
        public Pair(string v, int t) {
            value = v;
            timestamp = t;
        }
    }
}

/**
 * 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);
 */