Amazon: Kindle Reading Sessions That Ended Behind the Last One
The Kindle team studies re-reading. Each reading session records the furthest location the reader was at when it ended; a session that ends behind the…
- Difficulty: Medium
- Topics: Window Functions
- Dialect: MySQL
- Problem: #585
Problem statement
The Kindle team studies re-reading. Each reading session records the furthest location the reader was at when it ended; a session that ends behind the previous session of the same reader in the same book means the reader went back.
For each reader and book, take the sessions in order of ended_at. Return every session whose last_location is strictly lower than that of the previous session of the same reader and book, with session_id, reader_id, book_id and locations_back (previous location minus this one). A reader's first session in a book has no previous session and is never returned. Return the rows in any order.
A practice scenario set at Amazon: the tables and data are invented, and this is not a question from, or endorsed by, Amazon.
Tables
Table: ReadingSession
| Column | Type |
|---|---|
| session_id | int |
| reader_id | int |
| book_id | varchar |
| ended_at | datetime |
| last_location | int |
Primary key: session_id.
One row per reading session; no two sessions of one reader in one book end at the same moment.
Examples
Example 1
ReadingSession
| session_id | reader_id | book_id | ended_at | last_location |
|---|---|---|---|---|
| 1 | 7 | B0NOVEL001 | 2025-02-01 22:00:00 | 1200 |
| 2 | 7 | B0NOVEL001 | 2025-02-02 22:10:00 | 2500 |
| 3 | 7 | B0NOVEL001 | 2025-02-03 21:40:00 | 1800 |
| 4 | 7 | B0NOVEL001 | 2025-02-04 22:30:00 | 1800 |
| 5 | 7 | B0STUDY002 | 2025-02-02 08:00:00 | 300 |
| 6 | 8 | B0NOVEL001 | 2025-02-01 23:00:00 | 2600 |
| 7 | 8 | B0NOVEL001 | 2025-02-05 23:00:00 | 900 |
| 8 | 7 | B0STUDY002 | 2025-02-03 08:00:00 | 250 |
Output
| session_id | reader_id | book_id | locations_back |
|---|---|---|---|
| 3 | 7 | B0NOVEL001 | 700 |
| 8 | 7 | B0STUDY002 | 50 |
| 7 | 8 | B0NOVEL001 | 1700 |
How to solve Amazon: Kindle Reading Sessions That Ended Behind the Last One
"Previous session of the same reader in the same book" is a window: partition by (reader_id, book_id) and order by ended_at. LAG(last_location) over that window puts the previous session's location on each row, after which the question is a row filter: keep sessions where last_location < prev_location, and report the difference.
The filter cannot go in the same SELECT as the window function, because WHERE runs before windows are computed — hence the CTE. A reader's first session in a book has prev_location NULL; x < NULL is NULL, so it is filtered out without any special case. A session that ends at the same location as the previous one did not go back, so the comparison is strict. Sessions of other books by the same reader are in other partitions and never interfere.
The alternative finds the previous session with a correlated subquery — the latest earlier ended_at for the same reader and book, via ORDER BY … DESC LIMIT 1. It is correct because end times within a partition are distinct, but it probes the table once per row, while LAG needs one sort of the partition.
Reference solution (MySQL)
WITH s AS (
SELECT session_id, reader_id, book_id, last_location,
LAG(last_location) OVER (PARTITION BY reader_id, book_id ORDER BY ended_at) AS prev_location
FROM ReadingSession
)
SELECT session_id, reader_id, book_id, prev_location - last_location AS locations_back
FROM s
WHERE last_location < prev_locationAnother way
SELECT session_id, reader_id, book_id, prev_location - last_location AS locations_back FROM (
SELECT s.session_id, s.reader_id, s.book_id, s.last_location,
(SELECT p.last_location FROM ReadingSession p WHERE p.reader_id = s.reader_id AND p.book_id = s.book_id AND p.ended_at < s.ended_at
ORDER BY p.ended_at DESC LIMIT 1) AS prev_location
FROM ReadingSession s) t
WHERE last_location < prev_location← Amazon: Warehouse Bins Shared by Several Sellers · Amazon: Savings Plan Coverage of Each AWS Account →