Time Based Key-Value Store

A dictionary maps each key to its list of (timestamp, value) pairs. Timestamps only grow, so each list is sorted and get binary searches it for the latest timestamp <= t.

The idea

Set only appends: the problem guarantees timestamps arrive in increasing order, so every key's list is already sorted by time and nothing is ever inserted in the middle. Get asks for the value at the latest timestamp that is <= t. In a sorted list that is a boundary: entries up to some index are <= t, entries after it are > t. Binary search finds the last index on the <= side, remembering the best candidate so far in ans.

Code

public class TimeMap {
    readonly Dictionary<string, List<(int t, string v)>> map = new();

    public void Set(string key, string value, int timestamp) {
        if (!map.TryGetValue(key, out var list)) map[key] = list = new();
        list.Add((timestamp, value)); // timestamps only grow, so the list stays sorted
    }

    public string Get(string key, int timestamp) {
        if (!map.TryGetValue(key, out var list)) return "";
        int lo = 0, hi = list.Count - 1, ans = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (list[mid].t <= timestamp) { ans = mid; lo = mid + 1; } // candidate: look for a later one
            else hi = mid - 1; // too late: look earlier
        }
        return ans < 0 ? "" : list[ans].v;
    }
}

Tips

• When list[mid].t <= t, mid is a valid answer, but a later one may also be: record ans = mid and keep searching right.
• No timestamp <= t (the query is before the first set for that key) leaves ans = -1, so get returns "".
• A SortedList per key would also work, but it has no built-in "largest key <= t"; a plain List plus binary search is simpler and faster.

In the .NET library

TryGetValue does the lookup once and hands back the list; map[key] = list = new() creates and stores the list in one line. Value tuples (int t, string v) keep each entry a struct with named fields.