1
class TimeMap {
2
  private Map<String, List<Entry>> map;
3
  private final String NOT_FOUND = "";
4

5
  public TimeMap() {
6
    map = new HashMap<>();
7
  }
8

9
  public void set(String key, String value, int timestamp) {
10
    List<Entry> entries = map.getOrDefault(key, new ArrayList<>());
11
    entries.add(new Entry(value, timestamp));
12
    map.put(key, entries);
13
  }
14

15
  public String get(String key, int timestamp) {
16
    List<Entry> entries = map.get(key);
17
    if (entries == null) {
18
      return NOT_FOUND;
19
    }
20
    return binarySearch(entries, timestamp);
21
  }
22

23
  private String binarySearch(List<Entry> entries, int timestamp) {
24
    int lo = 0, hi = entries.size() - 1, mid = -1;
25
    String ans = "";
26

27
    // Base cases - if value is not set, return empty
28
    if (entries.get(lo).timestamp > timestamp) {
29
      return NOT_FOUND;
30
    }
31
    // If timestamp is equal or greater, return the last value saved in map against this key, since
32
    // that will have the largest timestamp
33
    else if (entries.get(hi).timestamp <= timestamp) {
34
      return entries.get(hi).value;
35
    }
36

37
    // Else apply binary search to get correct value
38
    while (lo <= hi) {
39
      mid = lo + (hi - lo) / 2;
40
      Entry entry = entries.get(mid);
41
      // System.out.println("mid: "+mid);
42
      if (entry.timestamp == timestamp) {
43
        return entry.value;
44
      }
45
      // Save ans, and look for ans on right half to find greater timestamp
46
      else if (entry.timestamp < timestamp) {
47
        ans = entry.value;
48
        lo = mid + 1;
49
      } else {
50
        hi = mid - 1;
51
      }
52
    }
53
    return ans;
54
  }
55
}
56

57
class Entry {
58
  String value;
59
  int timestamp;
60

61
  public Entry(String value, int timestamp) {
62
    this.value = value;
63
    this.timestamp = timestamp;
64
  }
65
}