[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

9,808 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

  8595. Hi there, this weekend is pleasant for me, since this occasion i am reading this enormous informative piece of writing here at my home.

    Reply

  9034. Mike ve Tre adlı kardeşler, karanlık geçmişlerini geride bırakarak yaşamlarında temiz bir sayfa açmaya kararlıdır. Mike işlemediği bir suç yüzünden düştüğü hapisten yeni çıkmıştır ve tek istediği kızını öfkeli bir eski erkek arkadaşın hışmından korumaktır. Ağaney Tre ise kardeşini ve yeni kız arkadaşını tamamen temize çıkarabilmek için son bir “teslimat” yapmayı isteksizce kabul eder. Gavin Malm

    Reply

  9036. Kabilenin büyücüsü karanlık işlere bulaşınca, kabiledekiler kaybolmaya başlar, bundan kurtulmak için 3 delikanlı kutsal şehir sarilaya giderler. Ve macera başlar… 🙂 Vaughn Ahrenholz

    Reply

  9044. Ajan izle. 2015 yapımı Ajan (spy) filminin konusu: Susan Cooper CIA’de masa başı çalışan bir analisttir. Cooper aynı zamanda en kritik görevlerin başarıyla sonlandırılmasını sağlarken adı gizli kalan bir kahramandır. Partneri Bradley Fine ile iyi bir ikili olmuşlardır ancak son görevlerinde Bradley ile kurumun bir başka gözde ajanı olan Rick Ford’un kimliklerinin ifşa olur. Ölümcül silah ticareti yapan tehlikeli bir şebekenin dünyasına sızarak yol açacakları felaketi önleme görevi Susan Cooper’ın olur. Cooper masa başından ilk kez sahaya adım atacağı bu görevde, içindeki tüm potansiyeli açığa çıkaracak ve fark etmediği yeteneklerini keşfedecektir. Tyron Ciesielski

    Reply

  9072. Akıllı ve hırslı bir genç olan Balram Halwai, fakir bir köylüdür. Amerika’dan yeni dönen Ashok ve Pinky’nin şoförü olan Balram, işini en iyi şekilde yapmaya çalışır. Toplum Balram’ı hizmet etmek için eğitmiştir ve bu yüzden de zengin patronlarının vazgeçilmezi haline gelir. Patronu sayesinde bilmediği bir dünya ile tanışan Balram, bu dünyaya asla erişemeyeceğini düşünür. Bu adaletsiz sisteme isyan eden Balram, zengin olmak için bambaşka bir yol dener. Beyaz Kaplan – The White Tiger izle Manuel Hayword

    Reply

  9080. Yıllarca omuz omuza savaştığı Liu Bei’nin askeri iken imparatorun ordusuna esir düşen General Guan Yunchang, eski efendisinin ailesinin serbest bırakılması karşılığında, düşman safına geçmeyi kabul eder Blaine Tinnea

    Reply

  9637. Win big and win often at our Mexican casino platform. With generous payouts and thrilling bonuses, every spin is a chance to change your life. casi esto es lo que te diferencia de los demas.

    Reply

Leave a Reply to Charlosvup Cancel reply

Your email address will not be published. Required fields are marked *

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More