[Programming Problem] Time Based Key-Value Store

Create a timebased key-value store class TimeMap, that supports two operations.

  1. set(string key, string value, int timestamp)
    Stores the key and value, along with the given timestamp.
  2. get(string key, int timestamp)
    Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the one with the largest timestamp_prev. If there are no values, it returns the empty string ("").

[Problem Link]

Note that key-values are inserted in timestamp order (meaning when we set multiple values for a key, we wont request timestamp 10 before timestamp 1-9). So, the timestamp’s for a key will be in sorted order.

The problem essentially boils down to running a binary search for a target (or next smallest target). At every step, we return value if it matches exactly, otherwise go left or right. When we get a return from the recursion, we have a choice between returning a.) returned value or b.) current (mid) value. We return the one lower than target. If both values are lower than target, we return the one closer to target.

/**
 * Initialize your data structure here.
 */
 
var closest = function(i, j, arr, val) {
    if ( i > j ) return {value: '', timestamp: Number.MAX_VALUE};
 
    let mid = i + Math.round((j-i)/2);
    if ( arr[mid].timestamp === val ) return arr[mid];
 
    let ret = Number.MAX_VALUE;
    if ( arr[mid].timestamp > val )
        ret = closest(i, mid-1, arr, val);
    else 
        ret = closest(mid+1, j, arr, val);
 
    if ( arr[mid].timestamp < val && ret.timestamp < val ) {
        return arr[mid].timestamp > val ? arr[mid] : ret;
    } else if ( arr[mid].timestamp < val ) {
        return arr[mid];
    } else {
        return ret;
    }
}
 
 
var TimeMap = function() {
    this.map = {};
};
 
/** 
 * @param {string} key 
 * @param {string} value 
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function(key, value, timestamp) {
    if (!this.map[key]) this.map[key] = [];
    this.map[key].push({value, timestamp});
};
 
/** 
 * @param {string} key 
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function(key, timestamp) {
    if (!this.map[key]) return "";
    let arr = this.map[key];
    let ret = closest(0, arr.length-1, arr, timestamp);
    return ret.value;
};
 
/** 
 * 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)
 */

softwareeveryday

8,828 thoughts on “[Programming Problem] Time Based Key-Value Store”

  82. Thanks a lot for providing individuals with an exceptionally terrific possiblity to read in detail from here. It can be so beneficial plus packed with a great time for me personally and my office acquaintances to search your site at the least thrice per week to find out the fresh secrets you have got. And definitely, we are always fascinated concerning the gorgeous ideas served by you. Certain 2 facts in this post are undeniably the most efficient we’ve ever had.

    Reply

  83. I would like to express my admiration for your kind-heartedness in support of individuals who require help with this one matter. Your very own dedication to getting the solution around appeared to be pretty functional and have consistently permitted some individuals just like me to realize their targets. Your own insightful recommendations means this much to me and a whole lot more to my fellow workers. Warm regards; from all of us.

    Reply

  85. I needed to compose you that little bit of remark to be able to say thanks a lot once again for your nice concepts you’ve provided in this article. It is incredibly generous of you to give easily precisely what a lot of folks could have offered for sale for an e-book to get some profit for themselves, most notably now that you might well have tried it in case you considered necessary. Those inspiring ideas likewise served as a easy way to realize that many people have the same eagerness similar to my very own to find out a little more regarding this matter. I’m sure there are several more fun sessions up front for people who go through your site.

    Reply

  95. Needed to put you this tiny note so as to say thank you the moment again about the awesome strategies you’ve discussed in this article. It is so tremendously open-handed with you to supply publicly what exactly many of us would have advertised for an electronic book to help with making some cash for themselves, notably considering the fact that you could possibly have done it if you wanted. These guidelines as well served to become a good way to comprehend other people online have the identical fervor like my own to know many more with reference to this matter. I know there are several more pleasurable moments up front for individuals that read your site.

    Reply

  122. Can I just say what a reduction to seek out somebody who really knows what theyre talking about on the internet. You positively know methods to bring an issue to gentle and make it important. More people have to read this and understand this aspect of the story. I cant consider youre not more well-liked because you undoubtedly have the gift.

    Reply