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
| Column | Type |
|---|---|
| report_id | int |
| scooter_id | int |
| reported_at | datetime |
| header | varchar |
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_id | scooter_id | reported_at | header |
|---|---|---|---|
| 1 | 701 | 2024-10-01 08:00:00 | S1PRO/BLR/fw=4.9.1/bms=2.0 |
| 2 | 701 | 2024-10-05 09:00:00 | S1PRO/BLR/fw=4.10.0/bms=2.1 |
| 3 | 702 | 2024-10-04 10:00:00 | S1PRO/PNQ/fw=4.10.2/bms=2.1 |
| 4 | 703 | 2024-10-06 11:00:00 | S1PRO/HYD/fw=4.9.1/bms=2.0 |
| 5 | 704 | 2024-10-02 07:00:00 | S1X/BLR/fw=5.0.0/bms=2.1 |
| 6 | 704 | 2024-10-07 07:30:00 | S1X/BLR/fw=4.2.0/bms=2.0 |
| 7 | 705 | 2024-10-03 12:00:00 | S1X/PNQ/fw=4.2.0/bms=2.0 |
| 8 | 706 | 2024-10-03 12:00:00 | S1AIR/HYD/fw=3.9.4/bms=2.0 |
Output
| scooter_id | model | current_fw | newest_fw |
|---|---|---|---|
| 701 | S1PRO | 4.10.0 | 4.10.2 |
| 703 | S1PRO | 4.9.1 | 4.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_idAnother 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 →