Calculate Highway Tolls from Ordered Checkpoint Logs

## Problem A highway has checkpoints numbered `0` through `m - 1` in road order. `segmentFees[i]` is the toll for traveling between checkpoints `i` and `i + 1` in either direction. You receive one day's checkpoint records in chronological order. For every vehicle, charge the road distance between each pair of its consecutive records. A vehicle may reverse direction or report the same checkpoint repeatedly. Return the total toll across all vehicles for the day. ### Portable Function Contract Implement `totalDailyToll(segmentFees, records)` and return one integer. `segmentFees` is a list of nonnegative integers. `records` is a list of string rows. Each record has exactly two fields: ```text [license, checkpointText] ``` - `license` is a nonempty ASCII string. - `checkpointText` is the canonical nonnegative decimal encoding of the checkpoint: it is `"0"` or a nonzero digit followed by zero or more digits, with no sign, leading zero, whitespace, decimal point, or exponent. Parse `checkpointText` exactly as an integer before using it. The string-only record row is part of the portable console interface. ### Constraints & Assumptions - `1 <= m <= 200,000`; `len(segmentFees) == m - 1`. - `0 <= segmentFees[i] <= 225182`. - `0 <= len(records) <= 200,000`. - Every parsed checkpoint is in `[0, m - 1]` and each license is a nonempty ASCII string. - The answer may exceed signed 32-bit range, but every valid answer is at most `9,007,199,254,740,991`, so it is exactly representable as a JavaScript safe integer and fits in a signed 64-bit integer. - The records are already in the exact time order to process. ### Clarifying Questions to Ask - Is travel direction relevant to price? No, segment fees are symmetric. - Does the first record for a vehicle incur a charge? No. - What does a repeated record at the same checkpoint cost? Zero. - Why is the checkpoint encoded as text? A homogeneous string row maps directly to every supported console language without changing the integer meaning. ```hint Precompute distances from checkpoint zero A prefix sum of segment fees makes the toll between checkpoints `a` and `b` equal to `abs(prefix[a] - prefix[b])`. ``` ```hint Remember only each vehicle's last checkpoint Process the global record stream once. Charge from the stored checkpoint, then replace it with the current one. ``` ### Example ```text segmentFees = [5, 7, 2] records = [ ["A","0"], ["B","3"], ["A","2"], ["A","1"], ["B","1"], ["A","1"] ] A pays 12 + 7 + 0; B pays 9; return 28 ``` ### Evaluation Focus - Parses every canonical checkpoint string exactly. - Uses per-license chronological adjacency, not adjacency in the global log alone. - Handles forward, reverse, and zero-distance travel. - Uses prefix sums for constant-time pair cost. - Uses numeric types that preserve every valid total exactly. - Runs in `O(m + number of records)` expected time. ### Extensions to Discuss 1. How would you process records that arrive out of timestamp order? 2. How would daily caps or vehicle-specific rates change the state? 3. How could the calculation be partitioned across workers without splitting a vehicle's sequence incorrectly?