Ola: Scooters Behind Their Model's Newest Firmware

Hard
841.

Ola: Scooters Behind Their Model's Newest Firmware

Scooters do not report their software in neat columns: every telemetry report carries one header string such as S1PRO/BLR/fw=4.10.2/bms=2.1 — model, city code, firmware version and battery-management version, always in that order and separated by /. The software-quality team wants the scooters that are behind the rest of their model.

A scooter's current firmware is the fw= version in its latest report (by reported_at) — a scooter that was rolled back reports the older version. A model's newest firmware is the highest current firmware among that model's scooters. Versions are major.minor.patch and compare numerically, part by part (4.10.0 is newer than 4.9.1); each part is below 100. Return every scooter whose current firmware is lower than its model's newest, as scooter_id, model, current_fw and newest_fw (the versions as written after fw=), ordered by model, then scooter_id.

A practice scenario set at Ola: the tables and data are invented, and this is not a question from, or endorsed by, Ola.

Tables

Table: TelemetryHeader

ColumnType
report_idint
scooter_idint
reported_atdatetime
headervarchar

Primary key: report_id.

One row per telemetry report. A scooter never sends two reports at the same second, and its model never changes.

Example

The rows must come back in the order shown.

TelemetryHeader

report_idscooter_idreported_atheader
17012024-10-01 08:00:00S1PRO/BLR/fw=4.9.1/bms=2.0
27012024-10-05 09:00:00S1PRO/BLR/fw=4.10.0/bms=2.1
37022024-10-04 10:00:00S1PRO/PNQ/fw=4.10.2/bms=2.1
47032024-10-06 11:00:00S1PRO/HYD/fw=4.9.1/bms=2.0
57042024-10-02 07:00:00S1X/BLR/fw=5.0.0/bms=2.1
67042024-10-07 07:30:00S1X/BLR/fw=4.2.0/bms=2.0
77052024-10-03 12:00:00S1X/PNQ/fw=4.2.0/bms=2.0
87062024-10-03 12:00:00S1AIR/HYD/fw=3.9.4/bms=2.0

Output

scooter_idmodelcurrent_fwnewest_fw
701S1PRO4.10.04.10.2
703S1PRO4.9.14.10.2
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

Ola: Scooters Behind Their Model's Newest Firmware

Scooters do not report their software in neat columns: every telemetry report carries one header string such as S1PRO/BLR/fw=4.10.2/bms=2.1 — model, city…

  • Difficulty: Hard
  • Topics: Strings, Window Functions, Subqueries
  • Dialect: MySQL
  • Problem: #841

Problem statement

Scooters do not report their software in neat columns: every telemetry report carries one header string such as S1PRO/BLR/fw=4.10.2/bms=2.1 — model, city code, firmware version and battery-management version, always in that order and separated by /. The software-quality team wants the scooters that are behind the rest of their model.

A scooter's current firmware is the fw= version in its latest report (by reported_at) — a scooter that was rolled back reports the older version. A model's newest firmware is the highest current firmware among that model's scooters. Versions are major.minor.patch and compare numerically, part by part (4.10.0 is newer than 4.9.1); each part is below 100. Return every scooter whose current firmware is lower than its model's newest, as scooter_id, model, current_fw and newest_fw (the versions as written after fw=), ordered by model, then scooter_id.

A practice scenario set at Ola: the tables and data are invented, and this is not a question from, or endorsed by, Ola.

Tables

Table: TelemetryHeader

ColumnType
report_idint
scooter_idint
reported_atdatetime
headervarchar

Primary key: report_id.

One row per telemetry report. A scooter never sends two reports at the same second, and its model never changes.

Examples

Example 1

TelemetryHeader

report_idscooter_idreported_atheader
17012024-10-01 08:00:00S1PRO/BLR/fw=4.9.1/bms=2.0
27012024-10-05 09:00:00S1PRO/BLR/fw=4.10.0/bms=2.1
37022024-10-04 10:00:00S1PRO/PNQ/fw=4.10.2/bms=2.1
47032024-10-06 11:00:00S1PRO/HYD/fw=4.9.1/bms=2.0
57042024-10-02 07:00:00S1X/BLR/fw=5.0.0/bms=2.1
67042024-10-07 07:30:00S1X/BLR/fw=4.2.0/bms=2.0
77052024-10-03 12:00:00S1X/PNQ/fw=4.2.0/bms=2.0
87062024-10-03 12:00:00S1AIR/HYD/fw=3.9.4/bms=2.0

Output

scooter_idmodelcurrent_fwnewest_fw
701S1PRO4.10.04.10.2
703S1PRO4.9.14.10.2

How to solve Ola: Scooters Behind Their Model's Newest Firmware

Three steps, each a classic. Keep the latest row per group: ROW_NUMBER() per scooter, newest reported_at first, and keep row 1. This must happen before anything else, because a scooter that installed 5.0.0 and was rolled back to 4.2.0 currently runs 4.2.0; taking the highest version it ever reported would be wrong.

Parse the header: SUBSTRING_INDEX(header, '/', 1) is the model, and the nested SUBSTRING_INDEX(SUBSTRING_INDEX(header, '/', 3), '/', -1) cuts the first three fields and then keeps the last of them, fw=4.10.2; SUBSTRING(…, 4) drops the three-character prefix. The version's parts come out the same way with . as the separator.

Compare versions correctly: as text, '4.10.0' < '4.9.1' because '1' < '9'. Since every part is below 100, major * 10000 + minor * 100 + patch is a number that orders versions exactly as they should be ordered. A second ROW_NUMBER() per model on that key finds the newest version (any scooter at the top gives the same text), and the scooters with a smaller key are behind. A scooter at the newest version — even a lone scooter of its model — is never listed.

The alternative finds the latest report with NOT EXISTS (no later report from the same scooter), strips the prefix with REPLACE, and builds a sortable key by zero-padding each part with LPAD to two digits, so plain string MAX works. Both are linear after one sort per scooter.

Reference solution (MySQL)

WITH latest AS (
  SELECT scooter_id, header,
         ROW_NUMBER() OVER (PARTITION BY scooter_id ORDER BY reported_at DESC) AS rn
  FROM TelemetryHeader
), cur AS (
  SELECT scooter_id,
         SUBSTRING_INDEX(header, '/', 1) AS model,
         SUBSTRING(SUBSTRING_INDEX(SUBSTRING_INDEX(header, '/', 3), '/', -1), 4) AS fw
  FROM latest
  WHERE rn = 1
), keyed AS (
  SELECT scooter_id, model, fw,
         CAST(SUBSTRING_INDEX(fw, '.', 1) AS SIGNED) * 10000
           + CAST(SUBSTRING_INDEX(SUBSTRING_INDEX(fw, '.', 2), '.', -1) AS SIGNED) * 100
           + CAST(SUBSTRING_INDEX(fw, '.', -1) AS SIGNED) AS fw_key
  FROM cur
), best AS (
  SELECT model, fw AS newest_fw, fw_key AS top_key,
         ROW_NUMBER() OVER (PARTITION BY model ORDER BY fw_key DESC, scooter_id) AS rn
  FROM keyed
)
SELECT k.scooter_id, k.model, k.fw AS current_fw, b.newest_fw
FROM keyed k
JOIN best b ON b.model = k.model AND b.rn = 1
WHERE k.fw_key < b.top_key
ORDER BY k.model, k.scooter_id

Another way

WITH cur AS (
  SELECT t.scooter_id, SUBSTRING_INDEX(t.header, '/', 1) AS model,
         REPLACE(SUBSTRING_INDEX(SUBSTRING_INDEX(t.header, '/', 3), '/', -1), 'fw=', '') AS fw
  FROM TelemetryHeader t
  WHERE NOT EXISTS (SELECT 1 FROM TelemetryHeader u WHERE u.scooter_id = t.scooter_id AND u.reported_at > t.reported_at)
), padded AS (
  SELECT scooter_id, model, fw,
         CONCAT(LPAD(SUBSTRING_INDEX(fw, '.', 1), 2, '0'),
                LPAD(SUBSTRING_INDEX(SUBSTRING_INDEX(fw, '.', 2), '.', -1), 2, '0'),
                LPAD(SUBSTRING_INDEX(fw, '.', -1), 2, '0')) AS sort_key
  FROM cur
), top AS (SELECT model, MAX(sort_key) AS top_key FROM padded GROUP BY model)
SELECT p.scooter_id, p.model, p.fw AS current_fw,
       (SELECT MIN(q.fw) FROM padded q WHERE q.model = p.model AND q.sort_key = t.top_key) AS newest_fw
FROM padded p JOIN top t ON t.model = p.model
WHERE p.sort_key < t.top_key
ORDER BY p.model, p.scooter_id

← Ola: Auto, Mini and Prime Ride Mix in Each City · Ola: Each Scooter's Opening and Closing Readings per Day →