Constraints

• 1 <= ttl <= 10^9
• 0 <= node_id, timestamp, t, cutoff <= 10^9
• 1 <= len(operations) <= 2 * 10^4
• Status strings are non-empty and never equal to 'OFFLINE'
• A node is counted in a summary at time t only if it has at least one update with timestamp <= t

Examples

Solution

def solution(ttl, operations):
    from bisect import bisect_left, bisect_right

    histories = {}
    valid_from = -10**30
    answers = []

    for op in operations:
        kind = op[0]

        if kind == 'update':
            node, status, ts = op[1], op[2], op[3]
            times, statuses = histories.setdefault(node, [[], []])
            i = bisect_left(times, ts)
            if i < len(times) and times[i] == ts:
                statuses[i] = status
            else:
                times.insert(i, ts)
                statuses.insert(i, status)

        elif kind == 'getCurrent':
            node = op[1]
            if node not in histories or not histories[node][0]:
                answers.append(None)
            else:
                answers.append(histories[node][1][-1])

        elif kind == 'getAt':
            node, t = op[1], op[2]
            if t < valid_from or node not in histories or not histories[node][0]:
                answers.append(None)
                continue
            times, statuses = histories[node]
            i = bisect_right(times, t) - 1
            if i < 0:
                answers.append(None)
            elif t - times[i] > ttl:
                answers.append('OFFLINE')
            else:
                answers.append(statuses[i])

        elif kind == 'getClusterSummaryAt':
            t = op[1]
            if t < valid_from:
                answers.append(None)
                continue
            summary = {}
            for times, statuses in histories.values():
                i = bisect_right(times, t) - 1
                if i < 0:
                    continue
                state = 'OFFLINE' if t - times[i] > ttl else statuses[i]
                summary[state] = summary.get(state, 0) + 1
            answers.append(dict(sorted(summary.items())))

        elif kind == 'compact':
            cutoff = op[1]
            if cutoff <= valid_from:
                continue
            valid_from = cutoff
            new_histories = {}
            for node, value in histories.items():
                times, statuses = value
                if not times:
                    continue
                idx = bisect_left(times, cutoff)
                if idx == 0:
                    kept_times = times[:]
                    kept_statuses = statuses[:]
                elif idx == len(times):
                    kept_times = [times[-1]]
                    kept_statuses = [statuses[-1]]
                else:
                    kept_times = [times[idx - 1]] + times[idx:]
                    kept_statuses = [statuses[idx - 1]] + statuses[idx:]
                new_histories[node] = [kept_times, kept_statuses]
            histories = new_histories

    return answers

Time complexity: update: O(m) for one node's history because Python list insertion may shift elements; getCurrent: O(1); getAt: O(log m); getClusterSummaryAt: O(u log m) across u known nodes; compact: O(total retained updates). Space complexity: O(total retained updates).

Hints

1. For each node, keep timestamps sorted so you can binary-search the latest update not after t.
2. During compaction, keeping the last update before the cutoff plus all updates at or after the cutoff is enough to answer future queries for times >= cutoff.

Constraints

• 1 <= ttl <= 10^5
• 0 <= minute <= 2 * 10^5
• 1 <= len(events) + len(queries) <= 2 * 10^5
• The number of distinct non-OFFLINE statuses is at most 20
• Status strings are non-empty and never equal to 'OFFLINE'
• For every query, 0 <= end_minute - k + 1 <= end_minute <= 2 * 10^5

Examples

Solution

def solution(ttl, events, queries):
    if not queries:
        return []

    max_time = max(end_minute for end_minute, _ in queries)

    if not events:
        return [[{} for _ in range(k)] for end_minute, k in queries]

    latest = {}
    for node, status, minute in events:
        latest[(node, minute)] = status

    by_node = {}
    statuses = set()
    for (node, minute), status in latest.items():
        by_node.setdefault(node, []).append((minute, status))
        statuses.add(status)

    statuses = sorted(statuses)
    known_diff = [0] * (max_time + 2)
    status_diff = {status: [0] * (max_time + 2) for status in statuses}

    for updates in by_node.values():
        updates.sort()
        first_minute = updates[0][0]
        if first_minute <= max_time:
            known_diff[first_minute] += 1
            known_diff[max_time + 1] -= 1

        for i, (minute, status) in enumerate(updates):
            if minute > max_time:
                break
            end = min(max_time, minute + ttl)
            if i + 1 < len(updates):
                end = min(end, updates[i + 1][0] - 1)
            if minute <= end:
                diff = status_diff[status]
                diff[minute] += 1
                diff[end + 1] -= 1

    current_counts = {status: 0 for status in statuses}
    summaries = [{} for _ in range(max_time + 1)]
    known_nodes = 0

    for minute in range(max_time + 1):
        known_nodes += known_diff[minute]
        summary = {}
        online_nodes = 0
        for status in statuses:
            current_counts[status] += status_diff[status][minute]
            if current_counts[status] > 0:
                summary[status] = current_counts[status]
                online_nodes += current_counts[status]
        offline = known_nodes - online_nodes
        if offline > 0:
            summary['OFFLINE'] = offline
        summaries[minute] = dict(sorted(summary.items()))

    result = []
    for end_minute, k in queries:
        start = end_minute - k + 1
        window = []
        for minute in range(start, end_minute + 1):
            window.append(dict(summaries[minute]))
        result.append(window)

    return result

Time complexity: Preprocessing: O(e log e + M * s), where e is the number of events after deduplication, M is the maximum queried minute, and s is the number of distinct statuses. Answering all queries costs O(total number of returned minute summaries).. Space complexity: O(e + M * s).

Hints

1. For one node, each update creates a time interval during which that status is active: from its minute until the earlier of TTL expiry or the next update.
2. Difference arrays plus prefix sums let you build every minute's cluster summary once, then each query becomes a slice of the precomputed timeline.

Constraints

• 1 <= num_shards <= 10^4
• 0 <= node_id <= 10^9
• 0 <= len(requests) <= 2 * 10^4
• Each request mode is either 'R' or 'W'
• Each request may list the same node more than once, but a shard should only be locked once per request

Examples

Solution

def solution(num_shards, requests):
    waves = []
    plan = []

    for mode, nodes in requests:
        shard_list = sorted({node % num_shards for node in nodes})
        shard_set = set(shard_list)

        placed_wave = None
        for wave_index, wave in enumerate(waves):
            if mode == 'R':
                if wave['write'].isdisjoint(shard_set):
                    wave['read'].update(shard_set)
                    placed_wave = wave_index
                    break
            else:
                if wave['write'].isdisjoint(shard_set) and wave['read'].isdisjoint(shard_set):
                    wave['write'].update(shard_set)
                    placed_wave = wave_index
                    break

        if placed_wave is None:
            placed_wave = len(waves)
            new_wave = {'read': set(), 'write': set()}
            if mode == 'R':
                new_wave['read'].update(shard_set)
            else:
                new_wave['write'].update(shard_set)
            waves.append(new_wave)

        plan.append([shard_list, placed_wave])

    return {'waves': len(waves), 'plan': plan}

Time complexity: O(r * w * d), where r is the number of requests, w is the number of waves created by the greedy policy, and d is the number of distinct shards touched by a request. Space complexity: O(r + w * d).

Hints

1. Convert each request to the set of shards it touches first. The deadlock-free lock order is just the sorted list of those shards.
2. For every wave, track which shards already have readers and which already have writers. Reads only need to avoid writers; writes need both sets to be disjoint.