Server load scores from a day of requests

The score is a sum of three independent contributions per server, so compute each category on its own and add them up. The work is in the details: parsing, ordering, the sliding window and the tie rule for the peak hour.

Brute force. For each request, scan every earlier request to count how many came from the same client to the same server in the last 10 minutes. Then, for each server, count requests per hour by scanning the whole list. That is O(n^2) for the window and O(S * n) for the peak hours. It is fine as a first pass, but the window scan is the obvious bottleneck.

Optimal: one pass in time order.

1. Load servers into a map server_id -> score, starting at the base score.
2. Parse each request line. Drop malformed lines and requests for unknown servers. Sort the rest by (minute, input position), because the log is not in time order and the window depends on order.
3. Walk the sorted requests once:
   • Volume stress (category 1): look up the request's rule (default STANDARD) and add 1, 2, or max(1, ceil(payload_kb / 100)).
   • Repeat-client stress (category 2): keep a deque of timestamps per (client_id, server_id). Pop timestamps that are <= t - 10 (outside [t-9, t]), push t, and add 5 if the deque now holds more than 3 entries. Each timestamp is pushed and popped once, so the window is amortized O(1).
   • Count the request in per_hour[server][t // 60].
4. Peak-hour stress (category 3): after the pass, find each server's busiest hour (earliest on ties) and add 2 for every request in that hour. This needs the whole day, so it runs after the loop.
5. Sort by score descending, then server id ascending.

Invariants. After processing a request at minute t, each deque holds exactly the timestamps of that pair inside [t-9, t], including t. The categories never read each other's results, so their order does not matter. Only the window needs sorted input.

from collections import defaultdict, deque
from math import ceil
from typing import Deque, Dict, List, Tuple

WINDOW_MINUTES = 10
REPEAT_LIMIT = 3
REPEAT_PENALTY = 5
PEAK_PENALTY = 2


def volume_stress(rule: str, payload_kb: int) -> int:
    if rule == "PRIORITY":
        return 2
    if rule == "BATCH":
        return max(1, ceil(payload_kb / 100))
    return 1  # STANDARD, and the default for a missing or unknown rule


def parse_request(line: str):
    parts = [p.strip() for p in line.split(",")]
    if len(parts) != 5 or not all(parts[:2]) or not parts[3]:
        return None
    request_id, minute, server_id, client_id, payload = parts
    try:
        t, kb = int(minute), int(payload)
    except ValueError:
        return None
    if not 0 <= t < 24 * 60 or kb < 0:
        return None
    return request_id, t, server_id, client_id, kb


def compute_load_scores(
    servers: List[str], requests: List[str], rules: Dict[str, str]
) -> List[Tuple[str, int]]:
    scores: Dict[str, int] = {}
    for line in servers:
        server_id, base = (p.strip() for p in line.split(","))
        scores[server_id] = int(base)

    parsed = []
    for order, line in enumerate(requests):
        req = parse_request(line)
        if req and req[2] in scores:
            parsed.append((req[1], order, req))
    parsed.sort()  # by minute, then by input order

    recent: Dict[Tuple[str, str], Deque[int]] = defaultdict(deque)
    per_hour: Dict[str, List[int]] = defaultdict(lambda: [0] * 24)

    for t, _, (request_id, _, server_id, client_id, kb) in parsed:
        # Category 1: volume stress from the request's own rule.
        scores[server_id] += volume_stress(rules.get(request_id, "STANDARD"), kb)

        # Category 2: repeat-client stress in a trailing 10-minute window.
        window = recent[(client_id, server_id)]
        while window and window[0] <= t - WINDOW_MINUTES:
            window.popleft()
        window.append(t)
        if len(window) > REPEAT_LIMIT:
            scores[server_id] += REPEAT_PENALTY

        per_hour[server_id][t // 60] += 1

    # Category 3: peak-hour stress, needs the whole day first.
    for server_id, counts in per_hour.items():
        peak = max(counts)  # list.index picks the earliest tied hour
        scores[server_id] += PEAK_PENALTY * counts[counts.index(peak)]

    return sorted(scores.items(), key=lambda kv: (-kv[1], kv[0]))

Let n be the number of request lines and S the number of servers.

• Parsing and filtering: O(n) time.
• Sorting by time: O(n log n) time. This dominates. If timestamps are minutes in one day, a counting sort over 1,440 buckets makes it O(n + 1440).
• Main pass: O(n) amortized. Each timestamp enters and leaves its deque once.
• Peak hour: O(24 * S) time.
• Final sort: O(S log S).
• Space: O(n + S) for the parsed requests, deques, and hour counters (24 per server).

Servers ["s1,10", "s2,4", "s3,0"], rules {"r2": "BATCH", "r5": "PRIORITY"}:

• Requests r1,60,s1,alice,0, r2,62,s1,alice,250, r3,65,s1,alice,0, r4,68,s1,alice,0, r5,130,s2,bob,0, r6,61,s1,carol,0, a request for unknown server s9, and a malformed line give [("s1", 32), ("s2", 8), ("s3", 0)]. For s1: base 10, volume 1+3+1+1+1 = 7, repeat +5 (alice's 4th request at minute 68), peak hour 1 has 5 requests for +10. For s2: 4 + 2 + 2.
• Window boundary: requests from one client at minutes 0, 3, 6, 10 to server s (base 0) score 12. Minute 0 has left the window by minute 10, so there is no repeat penalty.
• Inside the window: minutes 0, 3, 6, 9 score 17 (4 volume + 5 repeat + 8 peak).
• The same requests in reverse input order also score 17, because sorting restores time order.
• Peak tie: one request at minute 0 and one at minute 61 score 4. The earliest tied hour counts once, for +2.
• BATCH with 101 KB adds 2. BATCH with 0 KB still adds 1.
• A server with no requests keeps its base score and still appears in the output.
• A request id with no rule is treated as STANDARD.

• Configurable rules. Move the weights, window length, repeat limit and penalties into a config object, or a list of Rule objects with apply(request, state). Each category becomes a pluggable class, and adding a fourth category does not touch the loop.
• Streaming requests. Requests arrive one at a time, roughly in order. Keep the deques and hour counts live, and return scores on demand. The peak-hour term is computed on read from the 24 counters. Late events within a bounded skew can be buffered and released in order with a min-heap.
• Decay instead of a hard window. Each request's stress halves every h minutes. Store (score, last_update) per server and multiply by 2 ** (-(t - last)/h) before each update. Each update is still O(1).
• Route the next request. Given the current scores, send a new request to the lowest-scoring server (ties by id). Keep a heap of (score, server_id) with lazy deletion, or a sorted container, so each route is O(log S).
• Scale to many days or many machines. Shard by server_id so each shard owns its servers' deques and counters. The repeat window is keyed by (client, server), so it never crosses shards.

Mid-level (L4)

• Parses the input correctly, skips bad lines and unknown servers, and applies the default rule.
• Gets all three categories right, including the window boundary and the earliest-hour tie.
• Code runs on the given example. Tests at least one edge case without being asked.

Senior (L5)

• Sorts by time, explains why the window needs it, and uses a per-pair deque for amortized O(1) windows.
• Sees that the peak hour needs the whole day and computes it after the pass.
• Structures the categories so a new part (config, new rule) changes little code. States complexity for each step.

Staff (L6+)

• Asks about the ambiguous cases up front: inclusive window bounds, ties, unknown rules, duplicate request ids.
• Turns the batch job into a streaming design with bounded memory and late-event handling.
• Discusses decay versus fixed windows, sharding by server, and how the score feeds an actual routing decision.