First approach

class TimeMap {
    private HashMap<String, List<Pair>> map;

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

    public void set(String key, String value, int timestamp) {
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(new Pair(value, timestamp));
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }
        String res = "";
        var list = map.get(key);
        int l = 0, r = list.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;

            if (list.get(mid).time <= timestamp) {
                l = mid + 1;
                res = list.get(mid).value;
            } else {
                r = mid - 1;
            }
        }

        return res;
    }

    private class Pair {
        String value;
        int time;

        public Pair(String value, int time) {
            this.value = value;
            this.time = time;
        }
    }
}