Rollout rewind

A bike-share depot flashes new firmware onto bikes all day. When a bike falls over at 14:20, the investigator needs to know what it was running at 14:20.

The problem

Build the depot's rollout log. Two instructions arrive, one at a time:

• ("flash", bike, build, minute) — that bike was given that build at that minute, counted in minutes since the depot opened.
• ("running", bike, minute) — report the build the bike was running at that minute: the one from its newest flash at or before it.

A bike answers "" for any minute before its first flash, and for a bike the log has never seen. Flashes for a given bike arrive in non-decreasing minute order; two flashes may share a minute, and the later record wins.

Input. ops — a list of instruction tuples in the shapes above.

Output. A list of the answers, in order, one per running.

Example.

[("flash", "B14", "hub-2.0", 40), ("running", "B14", 40),
 ("running", "B14", 55), ("flash", "B14", "hub-2.4", 90),
 ("running", "B14", 89), ("running", "B14", 90), ("running", "B14", 400)]
  ->  ["hub-2.0", "hub-2.0", "hub-2.0", "hub-2.4", "hub-2.4"]

Minute 40 is the flash minute itself, so it already counts. Minute 89 is one minute short of the second flash and still reports the old build; minute 400 is long after it and reports the new one.

A second example, asking about minutes and bikes the log cannot cover:

[("flash", "B03", "hub-1.9", 120), ("running", "B03", 119),
 ("running", "B03", 120), ("running", "B77", 500)]
  ->  ["", "hub-1.9", ""]

Constraints.

• 1 <= len(ops) <= 10^5
• 0 <= minute <= 10^7
• A bike id is up to 12 characters; a build name is up to 20.

Hints

Approach

Brute force

Append every flash to one list and, on each query, walk the whole list keeping the best record for that bike. With 10⁵ instructions that is up to 10¹⁰ record inspections, most of them about bikes nobody asked for.

The insight

Each bike's history is already sorted by minute, so a query is a binary search inside that bike's own list, never a scan of the log.

Sortedness is the precondition, and here it is given rather than bought: records for a bike arrive in non-decreasing minute order, and appending to the end of a sorted list keeps it sorted. Splitting by bike is what makes the search possible at all — a single shared list is sorted by minute but interleaves bikes, so the neighbour of a minute is usually the wrong bike's record.

Algorithm

1. Keep two maps: bike to its list of minutes, bike to its list of builds, with matching positions.
2. On flash, append the minute and the build to that bike's lists.
3. On running, look up the bike; an unseen bike answers "".
4. Binary search its minutes for the first entry strictly after the asked minute; call that position cut.
5. If cut is 0 nothing had been flashed yet, so answer ""; otherwise answer the build at cut - 1.

Complexity

Time O(1) per flash and O(log m) per query, where m is that bike's number of flashes. Space O(f) for f flashes in total.

Solution

"""Rollout rewind — one sorted history per bike, answered with a binary search."""

from bisect import bisect_right


def solve(ops):
    stamps = {}     # bike -> minutes of its flashes, ascending by construction
    builds = {}     # bike -> the build written at the matching minute
    answers = []

    for op in ops:
        if op[0] == "flash":
            _, bike, build, minute = op
            stamps.setdefault(bike, []).append(minute)
            builds.setdefault(bike, []).append(build)
        else:                                   # ("running", bike, minute)
            _, bike, minute = op
            history = stamps.get(bike)
            if not history:
                answers.append("")
                continue
            # First flash strictly after the asked minute; the one before it is
            # the newest flash that had already happened.
            cut = bisect_right(history, minute)
            answers.append(builds[bike][cut - 1] if cut else "")

    return answers

TESTS = [
    (
        (
            [
                ("flash", "B14", "hub-2.0", 40),
                ("running", "B14", 40),
                ("running", "B14", 55),
                ("flash", "B14", "hub-2.4", 90),
                ("running", "B14", 89),
                ("running", "B14", 90),
                ("running", "B14", 400),
            ],
        ),
        ["hub-2.0", "hub-2.0", "hub-2.0", "hub-2.4", "hub-2.4"],
    ),
    # Asked before the bike was ever flashed, and asked about a bike in no log.
    (
        (
            [
                ("flash", "B03", "hub-1.9", 120),
                ("running", "B03", 119),
                ("running", "B03", 120),
                ("running", "B77", 500),
            ],
        ),
        ["", "hub-1.9", ""],
    ),
    # Two bikes must not share a history.
    (
        (
            [
                ("flash", "B01", "hub-1.0", 10),
                ("flash", "B02", "hub-3.0", 20),
                ("running", "B01", 25),
                ("running", "B02", 25),
                ("running", "B02", 19),
            ],
        ),
        ["hub-1.0", "hub-3.0", ""],
    ),
    # Two flashes in the same minute: the later record wins.
    (
        (
            [
                ("flash", "B08", "hub-4.0", 60),
                ("flash", "B08", "hub-4.1", 60),
                ("running", "B08", 60),
                ("running", "B08", 61),
            ],
        ),
        ["hub-4.1", "hub-4.1"],
    ),
    (
        ([("running", "B99", 1)],),
        [""],
    ),
]

Pitfalls

• Searching for the first entry not before the minute. A query at minute 90 then lands on the flash at 90 itself, and stepping back one reports hub-2.0 when hub-2.4 was already installed. You want the first entry strictly after.
• Skipping the cut == 0 check. Position -1 is the newest record in Python, so a question about minute 119 answers hub-1.9 — the build from the future — instead of "".
• Keeping one history for the whole depot. The search then finds the record nearest in time, which is usually another bike's, and B01 inherits B02's firmware.

Variants

• The callsign register — another structure shaped by the question it must answer, indexed by character instead of by minute.