1
var TimeMap = function () {
2
  this.data = new Map();
3
};
4

5
/**
6
 * @param {string} key
7
 * @param {string} value
8
 * @param {number} timestamp
9
 * @return {void}
10
 */
11
TimeMap.prototype.set = function (key, value, timestamp) {
12
  if (!this.data.has(key)) {
13
    this.data.set(key, [{ timestamp: timestamp, value: value }]);
14
  } else {
15
    let temp_store = this.data.get(key);
16
    temp_store.push({ timestamp: timestamp, value: value });
17
    this.data.set(key, temp_store);
18
  }
19
};
20

21
/**
22
 * @param {string} key
23
 * @param {number} timestamp
24
 * @return {string}
25
 */
26
TimeMap.prototype.get = function (key, timestamp) {
27
  if (this.data.has(key)) {
28
    const keyArray = this.data.get(key);
29

30
    //Optimize with binary search - Ordered by insert time, O(log n) devide and conq method (Like searching a dictionary)
31
    const index = keyArray.binarySearch(timestamp);
32
    if (keyArray[index].timestamp > timestamp) {
33
      return "";
34
    }
35

36
    return keyArray[index].value || prev;
37
  }
38

39
  return "";
40
};
41

42
Array.prototype.binarySearch = function (key) {
43
  let left = 0;
44
  let right = this.length - 1;
45

46
  while (left < right) {
47
    const i = Math.floor((left + right + 1) / 2);
48
    if (this[i].timestamp > key) {
49
      right = i - 1;
50
    } else {
51
      left = i;
52
    }
53
  }
54

55
  return left;
56
};
57

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