# 981. Time Based Key-Value Store

<https://leetcode.com/problems/time-based-key-value-store/>

ask timestamp is ordered, increasing?

1. for the question, so we want the value ( timestamp <= query input's timestamp, closest one)

so can leverage treemap's floorKey() (treeMap\<timestmap, value> or&#x20;

2\. use BS to find the closest value (timestamp <= query input's timestamp)

## HashMap + list , Binary search

from constraint:

* **All the timestamps `timestamp` of `set` are strictly increasing.**

so in actually, we can use bs in List

```java
    protected String binarySearch(List<Data> list, int time) {
        int low = 0, high = list.size() - 1;
        while (low +1 < high) {
            int mid = (low + high) >> 1;
            if (list.get(mid).time <= time) {
                low = mid;
            } else {
                high = mid;
            }
        }
        // we want closest time, so compare end first
        if (list.get(high).time <= time) {
            return list.get(high).val;
        }
        if (list.get(low).time <= time) {
            return list.get(low).val;
        }
        return "";
    }
```

T: set: O(1), get: O(1) + O(nlogn), n is list len

S: O(m\*n), m  - hashmap size, n - each list size

```java
class TimeMap {

    class Data {
        String value;
        int time;
        Data(String value, int time) {
            this.value = value;
            this.time = time;
        }
    }

    Map<String, List<Data>> map;
    public TimeMap() {
        this.map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new ArrayList<>());
        map.get(key).add(new Data(value, timestamp));
    }
    
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }
        return binarySearch(map.get(key), timestamp);
    }

    private String binarySearch(List<Data> list, int timestamp) {
        int start = 0;
        int end = list.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            if (list.get(mid).time <= timestamp) {
                start = mid;
            } else {
                end = mid;
            }
        }
        // we want closest time, so compare end first
        if (list.get(end).time <= timestamp) {
            return list.get(end).value;
        }
        if (list.get(start).time <= timestamp) {
            return list.get(start).value;
        }
        return "";
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */
```

## HashMap + TreeMap

T: set: O(1), get: O(1) + O(nlogn), n is treemap size

S: O(m\*n), m  - hashmap size, n - each treemap size

```
floorKey()-> the first greatest number <= given key;
ceillingKey()_> the first smaller number >=given key;


String get(String key, int timestamp) 
Returns a value such that set was called previously, 
with timestamp_prev <= timestamp. (so use floorKey)
```

```java
class TimeMap {
    Map<String, TreeMap<Integer, String>> map;
    public TimeMap() {
        this.map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, m -> new TreeMap<>());
        map.get(key).put(timestamp, value);
    }
    
    public String get(String key, int timestamp) {
        TreeMap<Integer, String> data = map.get(key);
        if (data == null) {
            return "";
        }
        Integer floor = data.floorKey(timestamp);
        if (floor == null) {
            return "";
        }
        return data.get(floor);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/hashtable/981.-time-based-key-value-store.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.