Solution: Hash Table + Binary Search

This problem requires storing key-value pairs with associated timestamps and efficiently retrieving the value for a given key at a specific timestamp or the most recent value before that timestamp. A hash table combined with a sorted data structure (like a list or a sorted array) for each key provides an efficient solution.

Approach:

1. Data Structure: We use a hash table (dictionary in Python, HashMap in Java, unordered_map in C++) to store key-value pairs. The keys of the hash table are the strings, and the values are lists (or vectors) of (timestamp, value) pairs. These lists are kept sorted by timestamp in ascending order.

2. set(key, value, timestamp): This method adds a new (timestamp, value) pair to the list associated with the given key in the hash table. Since we maintain a sorted list, we can simply append and re-sort if necessary (though other insertion methods maintaining sorted order would work too).

3. get(key, timestamp): This method retrieves the value associated with key at or before the given timestamp. It performs the following steps:

   • Checks if the key exists in the hash table. If not, it returns an empty string.
   • Performs a binary search on the sorted list of (timestamp, value) pairs for the given key. This efficiently finds the largest timestamp less than or equal to the input timestamp.
   • Returns the value associated with that timestamp, or an empty string if no such timestamp exists.

Time Complexity Analysis:

• set(key, value, timestamp): The hash table lookup is O(1) on average. Appending to a list is O(1). If we maintain the sorted order using insertion into a sorted list or similar method, this will take O(n) in the worst case (if n is the number of past entries for the key, insertion into a sorted list), or O(log n) with an efficient balanced tree structure. In practice, with relatively small number of entries for a given key, the performance difference is negligible.
• get(key, timestamp): Hash table lookup is O(1) on average. The binary search on the sorted list is O(log n), where n is the number of (timestamp, value) pairs associated with the key.

Space Complexity Analysis:

The space complexity is O(N*M), where N is the number of unique keys and M is the average number of timestamp-value pairs per key.

Code Examples:

Python:

import bisect
from collections import defaultdict
 
class TimeMap:
    def __init__(self):
        self.data = defaultdict(list)  # Key: String, Value: List[(timestamp, value)]
 
    def set(self, key: str, value: str, timestamp: int) -> None:
        self.data[key].append((timestamp, value))
 
    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return ""
        
        items = self.data[key]
        i = bisect.bisect_right(items, (timestamp, chr(127))) # Find largest timestamp <= input
        return items[i-1][1] if i > 0 else ""

Java:

import java.util.*;
 
class TimeMap {
    Map<String, List<int[]>> map;
 
    public TimeMap() {
        map = new HashMap<>();
    }
 
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp, value.hashCode()});
    }
 
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) return "";
 
        List<int[]> list = map.get(key);
        int left = 0, right = list.size() -1;
        int ans = -1;
 
        while (left <= right){
            int mid = left + (right - left)/2;
            if (list.get(mid)[0] <= timestamp){
                ans = mid;
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }
 
        return ans == -1 ? "" : String.valueOf(list.get(ans)[1]);
    }
}

C++:

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
 
class TimeMap {
public:
    TimeMap() {}
 
    void set(string key, string value, int timestamp) {
        data[key].push_back({timestamp, value});
    }
 
    string get(string key, int timestamp) {
        auto it = data.find(key);
        if (it == data.end()) return "";
 
        auto& vec = it->second;
        auto it2 = upper_bound(vec.begin(), vec.end(), make_pair(timestamp, string(127, 'z'))); //Binary Search
 
        return (it2 == vec.begin()) ? "" : prev(it2)->second;
    }
 
private:
    unordered_map<string, vector<pair<int, string>>> data;
};

These examples demonstrate the core approach. The specific implementation details (e.g., how to handle sorting) might vary slightly depending on the programming language and libraries used. However, the fundamental algorithmic strategy of using a hash table and binary search remains the same.