|
| 1 | +//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}) |
| 2 | +classTimeMap{ |
| 3 | +publichash:{}; |
| 4 | + |
| 5 | +constructor(){ |
| 6 | +this.hash={}; |
| 7 | +} |
| 8 | + |
| 9 | +set(key:string,value:string,timestamp:number):void{ |
| 10 | +if(keyinthis.hash){ |
| 11 | +this.hash[key].push({ timestamp, value}); |
| 12 | +}elsethis.hash[key]=[{ timestamp, value}]; |
| 13 | +} |
| 14 | + |
| 15 | +get(key:string,timestamp:number):string{ |
| 16 | +//if key is not in the hashmap there are no timestamps nor values, return "" |
| 17 | +if(!(keyinthis.hash))return''; |
| 18 | +lettimestamps=this.hash[key]; |
| 19 | +//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 "" |
| 20 | +if(timestamps.length===0||timestamps[0].timestamp>timestamp) |
| 21 | +return''; |
| 22 | + |
| 23 | +//starts from the first timestamp as closest |
| 24 | +letclosest=timestamps[0]; |
| 25 | + |
| 26 | +let[l,r]=[0,timestamps.length-1]; |
| 27 | + |
| 28 | +//binary search, but |
| 29 | +while(l<=r){ |
| 30 | +letmid=Math.floor((l+r)/2); |
| 31 | + |
| 32 | +if(timestamps[mid].timestamp===timestamp) |
| 33 | +returntimestamps[mid].value; |
| 34 | +//update closest if mid element's timestamp is still less than target timestamp |
| 35 | +if(timestamps[mid].timestamp<timestamp) |
| 36 | +closest=timestamps[mid]; |
| 37 | + |
| 38 | +if(timestamps[mid].timestamp<timestamp)l=mid+1; |
| 39 | +if(timestamps[mid].timestamp>timestamp)r=mid-1; |
| 40 | +} |
| 41 | + |
| 42 | +returnclosest.value; |
| 43 | +} |
| 44 | +} |