Time Based Key-Value Store

// Accepted solution for LeetCode #981: Time Based Key-Value Store
class TimeMap {
    private Map<String, TreeMap<Integer, String>> ktv = new HashMap<>();

    public TimeMap() {
    }

    public void set(String key, String value, int timestamp) {
        ktv.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        if (!ktv.containsKey(key)) {
            return "";
        }
        var tv = ktv.get(key);
        Integer t = tv.floorKey(timestamp);
        return t == null ? "" : tv.get(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);
 */

// Accepted solution for LeetCode #981: Time Based Key-Value Store
type TimeMap struct {
	ktv map[string][]pair
}

func Constructor() TimeMap {
	return TimeMap{map[string][]pair{}}
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	this.ktv[key] = append(this.ktv[key], pair{timestamp, value})
}

func (this *TimeMap) Get(key string, timestamp int) string {
	pairs := this.ktv[key]
	i := sort.Search(len(pairs), func(i int) bool { return pairs[i].t > timestamp })
	if i > 0 {
		return pairs[i-1].v
	}
	return ""
}

type pair struct {
	t int
	v string
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Set(key,value,timestamp);
 * param_2 := obj.Get(key,timestamp);
 */

# Accepted solution for LeetCode #981: Time Based Key-Value Store
class TimeMap:
    def __init__(self):
        self.ktv = defaultdict(list)

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

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.ktv:
            return ''
        tv = self.ktv[key]
        i = bisect_right(tv, (timestamp, chr(127)))
        return tv[i - 1][1] if i else ''


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

// Accepted solution for LeetCode #981: Time Based Key-Value Store
use std::collections::HashMap;

struct TimeMap {
    hm: HashMap::<String, Vec<(String, i32)>>
}

impl TimeMap {

    fn new() -> Self {
        Self {
            hm: HashMap::new()
        }
    }
    
    fn set(&mut self, key: String, value: String, timestamp: i32) {
        self.hm.entry(key).or_default().push((value, timestamp));
    }
    
    fn get(&self, key: String, timestamp: i32) -> String {
        let mut res = String::new();
        
        if let Some(t_list) = self.hm.get(&key) {
            let (mut l, mut r) = (0, t_list.len());

            while l < r {
                let m = l + (r - l) / 2;
                if timestamp < t_list[m].1 {
                    r = m;
                } else {
                    res = t_list[m].0.clone();
                    l = m + 1;
                }
            }
        }

        res
    }
}

// Accepted solution for LeetCode #981: Time Based Key-Value Store
//use an hashmap for keys, then each key will have an array (increasing order because of problem rules) of timestamps with values (represented as javascript objects {key, value})
class TimeMap {
    public hash: {};

    constructor() {
        this.hash = {};
    }

    set(key: string, value: string, timestamp: number): void {
        if (key in this.hash) {
            this.hash[key].push({ timestamp, value });
        } else this.hash[key] = [{ timestamp, value }];
    }

    get(key: string, timestamp: number): string {
        //if key is not in the hashmap there are no timestamps nor values, return ""
        if (!(key in this.hash)) return '';
        let timestamps = this.hash[key];
        //if there are no timestamps or the first timestamp is already bigger than target timestamp(they are sorted so all next ones will big too), return ""
        if (timestamps.length === 0 || timestamps[0].timestamp > timestamp)
            return '';

        //starts from the first timestamp as closest
        let closest = timestamps[0];

        let [l, r] = [0, timestamps.length - 1];

        //binary search, but
        while (l <= r) {
            let mid = Math.floor((l + r) / 2);

            if (timestamps[mid].timestamp === timestamp)
                return timestamps[mid].value;
            //update closest if mid element's timestamp is still less than target timestamp
            if (timestamps[mid].timestamp < timestamp)
                closest = timestamps[mid];

            if (timestamps[mid].timestamp < timestamp) l = mid + 1;
            if (timestamps[mid].timestamp > timestamp) r = mid - 1;
        }

        return closest.value;
    }
}