Constraints

• 0 <= len(operations) <= 200000
• 1 <= len(key) <= 100
• 0 <= len(value) <= 100
• 1 <= int(timestamp) <= 10^9
• For each individual key, set operation timestamps appear in nondecreasing order in the input.
• If multiple set operations for the same key use the same timestamp, the latest one in operation order should be returned for that timestamp.

Examples

Solution

def solution(operations):
    from bisect import bisect_right

    # key -> (list of timestamps, list of values)
    store = {}
    results = []

    for op in operations:
        if op[0] == 'set':
            _, key, value, timestamp_str = op
            timestamp = int(timestamp_str)

            if key not in store:
                store[key] = ([], [])

            times, values = store[key]
            times.append(timestamp)
            values.append(value)

        elif op[0] == 'get':
            _, key, timestamp_str = op
            timestamp = int(timestamp_str)

            if key not in store:
                results.append('')
                continue

            times, values = store[key]
            idx = bisect_right(times, timestamp) - 1

            if idx < 0:
                results.append('')
            else:
                results.append(values[idx])

    return results

Time complexity: O(n log h), where n is the number of operations and h is the maximum number of stored timestamps for any single key. Each set is O(1), and each get uses binary search.. Space complexity: O(s), where s is the number of set operations stored..

Hints

1. Store a separate timestamp history for each key instead of scanning all operations for every get.
2. Because timestamps for each key are stored in sorted order, binary search can find the latest timestamp not greater than the query time.