Constraints

• 0 <= len(operations) <= 200000
• key and value are non-empty strings; value is never the empty string
• clockTime and wallTime fit in a signed 64-bit integer
• The system clock readings on set operations may be equal to or less than earlier readings
• Only set operations create new versions; get operations do not change the store timestamp

Examples

Solution

def solution(operations):
    from bisect import bisect_right

    histories = {}
    outputs = []

    last_wall = None
    last_counter = 0
    inf_counter = len(operations) + 1

    for op in operations:
        kind = op[0]

        if kind == 'set':
            key = op[1]
            value = op[2]
            clock_time = int(op[3])

            if last_wall is None or clock_time > last_wall:
                wall = clock_time
                counter = 0
            else:
                wall = last_wall
                counter = last_counter + 1

            last_wall = wall
            last_counter = counter

            if key not in histories:
                histories[key] = ([], [])
            stamps, values = histories[key]
            stamps.append((wall, counter))
            values.append(value)

        elif kind == 'getLatest':
            key = op[1]
            if key in histories and histories[key][1]:
                outputs.append(histories[key][1][-1])
            else:
                outputs.append('')

        elif kind == 'getAtOrBefore':
            key = op[1]
            wall_time = int(op[2])

            if key not in histories:
                outputs.append('')
                continue

            stamps, values = histories[key]
            idx = bisect_right(stamps, (wall_time, inf_counter)) - 1
            if idx >= 0:
                outputs.append(values[idx])
            else:
                outputs.append('')

        else:
            raise ValueError('unknown operation type')

    return outputs

Time complexity: Per operation: set is O(1), getLatest is O(1), and getAtOrBefore is O(log m), where m is the number of versions for that key. Over n operations, the worst case is O(n log n).. Space complexity: O(w), where w is the number of set operations stored as historical versions..

Hints

1. Keep every key's versions in timestamp order. Since global assigned timestamps are increasing as operations are processed, each key's history can be appended to directly.
2. To handle repeated or backwards clock readings, combine the wall-clock component with a logical counter, then binary search for the upper bound (wallTime, infinity).