Problem Statement

Design a data structure that stores multiple values for the same key, each associated with a timestamp, and returns the value for a key at the largest timestamp less than or equal to the given timestamp.

You must implement two operations:

1. set(String key, String value, int timestamp)
   Stores the key–value pair with the given timestamp.
2. get(String key, int timestamp)
   Returns the value associated with key at the largest timestamp ≤ given timestamp.
   If there is none, return an empty string.

Example

set("love", "high", 10)
set("love", "low", 20)

get("love", 5)   -> ""
get("love", 10)  -> "high"
get("love", 15)  -> "high"
get("love", 20)  -> "low"
get("love", 25)  -> "low"

Constraints

• Timestamps for each key are strictly increasing (important!).
• Number of operations can be quite large (up to 100k).
• We must answer get queries efficiently.

---

Approach (Simple English)

The main requirement is:
Given a key and a timestamp, quickly retrieve the value whose timestamp is the closest but not greater than the given timestamp.

Key insight
For each key, timestamps increase strictly.
So for each key, we can store (timestamp, value) pairs in a sorted list.

When calling get(key, timestamp):

• Access the list for that key.
• Perform binary search to find the largest timestamp ≤ target.
• Return the associated value.

Why binary search?
Because searching linearly would be too slow (O(n)), while binary search gives O(log n).
Since there can be many operations, binary search is ideal.

Data structure
Use a HashMap:

Map<String, List<Pair(timestamp, value)>>

• set() → append to the list of that key. Since timestamps are strictly increasing, the list is always sorted.
• get() → perform binary search on the list.

Time complexity

• set: O(1) (amortized) since we simply append.
• get: O(log n) due to binary search.
• Total very efficient.

Alternate approach
You can also use TreeMap<Integer, String> for each key (ordered map).
Then floorEntry(timestamp) gives the result directly.
This is simpler but less memory-efficient and slightly slower due to tree overhead.
Backed solutions usually prefer ArrayList + binary search.

---

Java Code (Binary Search Approach)

import java.util.*;

class TimeMap {

    private static class Pair {
        int timestamp;
        String value;
        Pair(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }
    }

    private Map<String, List<Pair>> map;

    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new ArrayList<>())
            .add(new Pair(timestamp, value));
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) return "";

        List<Pair> list = map.get(key);

        int left = 0;
        int right = list.size() - 1;
        String result = "";

        // Binary search for largest timestamp <= target
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid).timestamp <= timestamp) {
                result = list.get(mid).value;
                left = mid + 1;  // try to find a closer timestamp
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
}

This version is optimal and exactly what interviewers expect.

---

Dry Run (Step-by-Step Example)

Let’s walk through the example:

set("love", "high", 10)
set("love", "low", 20)

The internal map:

"love" → [ (10, "high"), (20, "low") ]

Query 1

get("love", 5)

• List = [(10, “high”), (20, “low”)]
• Binary search → both timestamps > 5
• No candidate found → return “”

Query 2

get("love", 10)
Binary search steps:

• mid = 0 → timestamp=10 (<=10) → result=”high”
• move left to search better candidate
• final answer = “high”

Query 3

get("love", 15)
Binary search:

• mid = 0 → 10 <=15 → result=”high”
• mid = 1 → 20 >15 → search left
  Final result remains “high”

Query 4

get("love", 20)

• mid = 1 → 20 <=20 → result=”low”
  Result = “low”

Query 5

get("love", 25)

• mid = 1 → 20 <=25 → result=”low”
  Output = “low”

The binary search identifies the closest valid timestamp every time.

---

Complexity

Time

• set: O(1)
• get: O(log n) per query
• n = values stored per key

Space

• O(n) to store all timestamp-value pairs.

---

Edge Cases

• Key not present → return “”
• Key present but earliest timestamp > target → return “”
• Multiple calls to set with growing timestamps → list remains sorted
• Large number of timestamps for same key → binary search still efficient