Apple: Devices That Moved to an Older iOS Version
Software-update engineers investigate devices that end up on an older iOS build than the one they had — usually a restore from an archived image.
- Difficulty: Hard
- Topics: Strings, Window Functions
- Dialect: MySQL
- Problem: #619
Problem statement
Software-update engineers investigate devices that end up on an older iOS build than the one they had — usually a restore from an archived image. Versions are major.minor or major.minor.patch; a missing patch counts as 0, and every part compares as a number (so 16.7.10 is newer than 16.7.9, and 17.4.1 is newer than 17.4).
For each device, order its installs by installed_on. Return every install whose version is strictly older than the version of the device's previous install, with device_id, from_version (the previous install's version), to_version and installed_on. Order the rows by device_id, then installed_on.
A practice scenario set at Apple: the tables and data are invented, and this is not a question from, or endorsed by, Apple.
Tables
Table: DeviceInstall
| Column | Type |
|---|---|
| install_id | int |
| device_id | int |
| installed_on | date |
| ios_version | varchar |
Primary key: install_id.
One row per OS install on a device; a device never has two installs on the same day.
Examples
Example 1
DeviceInstall
| install_id | device_id | installed_on | ios_version |
|---|---|---|---|
| 1 | 1 | 2024-07-01 | 16.7.9 |
| 2 | 1 | 2024-08-01 | 16.7.10 |
| 3 | 1 | 2024-09-20 | 18.0 |
| 4 | 2 | 2024-06-10 | 17.4.1 |
| 5 | 2 | 2024-06-12 | 17.4 |
| 6 | 2 | 2024-07-30 | 17.6.1 |
| 7 | 3 | 2024-05-02 | 17.5 |
| 8 | 3 | 2024-05-20 | 16.7.10 |
| 9 | 3 | 2024-06-01 | 16.7.10 |
Output
| device_id | from_version | to_version | installed_on |
|---|---|---|---|
| 2 | 17.4.1 | 17.4 | 2024-06-12 |
| 3 | 17.5 | 16.7.10 | 2024-05-20 |
How to solve Apple: Devices That Moved to an Older iOS Version
The heart of the problem is comparing versions. As text, 16.7.10 sorts before 16.7.9, so a plain string comparison would report an upgrade as a downgrade. Split the string instead: SUBSTRING_INDEX(v, '.', 1) is the major, SUBSTRING_INDEX(SUBSTRING_INDEX(v, '.', 2), '.', -1) the minor, and the last part is the patch only when the version has two dots (LIKE '%.%.%'), otherwise 0. Cast them to numbers and pack them into one key, major × 1,000,000 + minor × 1,000 + patch, which orders versions exactly like the part-by-part rule as long as minor and patch stay below 1,000.
With a numeric key per install, the rest is a LAG per device ordered by date: keep the rows whose key is strictly lower than the previous install's. Reinstalling the same version (device 3) is not a downgrade, and a device's first install has no previous row, so its NULL comparison drops it.
The alternative compares the three parts lexicographically and finds the previous install with a correlated MAX(installed_on) instead of a window. Both parse each version once; the window version sorts each device's installs once.
Reference solution (MySQL)
WITH parsed AS (
SELECT device_id, installed_on, ios_version,
CAST(SUBSTRING_INDEX(ios_version, '.', 1) AS SIGNED) * 1000000
+ CAST(SUBSTRING_INDEX(SUBSTRING_INDEX(ios_version, '.', 2), '.', -1) AS SIGNED) * 1000
+ CASE WHEN ios_version LIKE '%.%.%' THEN CAST(SUBSTRING_INDEX(ios_version, '.', -1) AS SIGNED) ELSE 0 END AS vkey
FROM DeviceInstall
), paired AS (
SELECT device_id, installed_on, ios_version, vkey,
LAG(ios_version) OVER (PARTITION BY device_id ORDER BY installed_on) AS prev_version,
LAG(vkey) OVER (PARTITION BY device_id ORDER BY installed_on) AS prev_key
FROM parsed
)
SELECT device_id, prev_version AS from_version, ios_version AS to_version, installed_on
FROM paired
WHERE vkey < prev_key
ORDER BY device_id, installed_onAnother way
WITH parts AS (
SELECT device_id, installed_on, ios_version,
SUBSTRING_INDEX(ios_version, '.', 1) + 0 AS ma,
SUBSTRING_INDEX(SUBSTRING_INDEX(ios_version, '.', 2), '.', -1) + 0 AS mi,
IF(LENGTH(ios_version) - LENGTH(REPLACE(ios_version, '.', '')) = 2, SUBSTRING_INDEX(ios_version, '.', -1) + 0, 0) AS pa
FROM DeviceInstall
)
SELECT c.device_id, p.ios_version AS from_version, c.ios_version AS to_version, c.installed_on
FROM parts c
JOIN parts p ON p.device_id = c.device_id
AND p.installed_on = (SELECT MAX(x.installed_on) FROM DeviceInstall x WHERE x.device_id = c.device_id AND x.installed_on < c.installed_on)
WHERE c.ma < p.ma OR (c.ma = p.ma AND (c.mi < p.mi OR (c.mi = p.mi AND c.pa < p.pa)))
ORDER BY c.device_id, c.installed_on← Apple: In-App Revenue at the Price in Effect on Each Day · Apple: Apps Breaking Into Their Category's Top Three →