LeetCode 981. Time Based Key-Value Store

原题链接在这里：https://leetcode.com/problems/time-based-key-value-store/

题目：

Create a timebased key-value store class <code>TimeMap</code>, that supports two operations.

1. <code>set(string key, string value, int timestamp)</code>

Stores the <code>key</code> and <code>value</code>, along with the given <code>timestamp</code>.

2. <code>get(string key, int timestamp)</code>

Returns a value such that <code>set(key, value, timestamp_prev)</code> was called previously, with <code>timestamp_prev &lt;= timestamp</code>.

If there are multiple such values, it returns the one with the largest <code>timestamp_prev</code>.

If there are no values, it returns the empty string (<code>""</code>).

Example 1:

Example 2:

Note:

All key/value strings are lowercase.

All key/value strings have length in the range <code>[1, 100]</code>

The <code>timestamps</code> for all <code>TimeMap.set</code> operations are strictly increasing.

<code>1 &lt;= timestamp &lt;= 10^7</code>

<code>TimeMap.set</code> and <code>TimeMap.get</code> functions will be called a total of <code>120000</code> times (combined) per test case.

题解：

For the same key, if timestamp is different, value could be different. 

There could be cases &lt;key, value1&gt; with timestamp1, &lt;key, value2&gt; with timestamp2. Both values are stored. The second value is NOT overriding first value.

Have a HashMap&lt;String, TreeMap&lt;Integer, String&gt;&gt; hm to store keys. The value is TreeMap sorted based on timestamp.

set, update hm. get, first get the TreeMap based on key, then use floorKey to find the largest key &lt;= timestamp. 

Time Complexity: set, O(logn). get, O(logn). n = max(TreeMap size).

Space: O(m*n). m = hm.size().

AC Java: