Constraints

• 0 <= len(nodes) <= 10^4
• 0 <= requests <= 10^4
• start_index is -1, or 0 <= start_index < len(nodes)
• Node status is a string; only 'UP' counts as available

Examples

Solution

def solution(nodes, start_index, requests):
    n = len(nodes)
    current_index = start_index
    selected = []

    for _ in range(requests):
        if n == 0:
            selected.append(None)
            continue

        found = False
        for step in range(1, n + 1):
            idx = (current_index + step) % n
            if nodes[idx][1] == "UP":
                selected.append(nodes[idx][0])
                current_index = idx
                found = True
                break

        if not found:
            selected.append(None)

    return selected, current_index

Time complexity: O(requests * n), where n = len(nodes). Space complexity: O(requests).

Hints

1. Do not reset the index for every request; it should continue from the last successful selection.
2. For one request, you never need to inspect more than n nodes. If none are 'UP', append None.

Constraints

• 0 <= len(initial_nodes) <= 10^3
• 1 <= virtual_nodes <= 100
• 0 <= len(operations) <= 10^4
• Operation type is one of 'ADD', 'REMOVE', 'GET'
• Adding an existing node or removing a missing node should leave the ring unchanged

Examples

Solution

def solution(initial_nodes, virtual_nodes, operations):
    from bisect import bisect_left, insort

    def hash_value(text):
        text = str(text)
        return sum((i + 1) * ord(ch) for i, ch in enumerate(text))

    ring = []
    active = set()

    def add_node(node):
        if node in active:
            return
        active.add(node)
        for replica in range(virtual_nodes):
            insort(ring, (hash_value(f"{node}#{replica}"), node, replica))

    def remove_node(node):
        if node not in active:
            return
        active.remove(node)
        ring[:] = [entry for entry in ring if entry[1] != node]

    for node in initial_nodes:
        add_node(node)

    results = []

    for op in operations:
        kind = op[0]

        if kind == "ADD":
            add_node(op[1])
        elif kind == "REMOVE":
            remove_node(op[1])
        elif kind == "GET":
            key = op[1]
            down_nodes = set(op[2])

            if not ring:
                results.append(None)
                continue

            start = bisect_left(ring, (hash_value(key), "", -1))
            chosen = None

            for offset in range(len(ring)):
                node = ring[(start + offset) % len(ring)][1]
                if node not in down_nodes:
                    chosen = node
                    break

            results.append(chosen)

    return results

Time complexity: For ring size M: ADD is O(virtual_nodes * log M), REMOVE is O(M), and each GET is O(log M + M) in the worst case when many candidate nodes are down. Space complexity: O(M), where M is the number of virtual nodes currently on the ring.

Hints

1. Keep the ring sorted so you can binary-search the first virtual node whose position is >= the key hash.
2. If the first matching node is down, walk clockwise through the ring and stop after one full cycle.

Constraints

• 0 <= len(scenarios) <= 10^5
• 1 <= n, v <= 10^6
• 0 <= r, k, c, h, f <= 10^9
• a is either 0 or 1
• Use 64-bit integer arithmetic

Examples

Solution

def solution(scenarios):
    results = []

    for n, v, r, k, c, a, h, f in scenarios:
        ring_size = n * v
        lookup_ch = 0 if ring_size <= 1 else (ring_size - 1).bit_length()

        rr_cost = r + c * k + (r if a == 1 else 0) + f * n
        ch_cost = r * lookup_ch + c * ((k + n - 1) // n) + ring_size + h + f * lookup_ch

        if rr_cost < ch_cost:
            results.append("round_robin")
        elif ch_cost < rr_cost:
            results.append("consistent_hashing")
        else:
            results.append("either")

    return results

Time complexity: O(len(scenarios)). Space complexity: O(len(scenarios)) for the output list.

Hints

1. You can compute ceil(log2(x)) for x > 0 as (x - 1).bit_length().
2. Evaluate both formulas exactly for each scenario, then compare and handle the tie case.