Loading page…
Practice problem · easy
A gateway writes one log line for every request it handles. A line records the second it was written, as Unix time (seconds since 1 January 1970), and its size in bytes.
The operations dashboard shows one row for each hour that had traffic, with the number of lines and the bytes written in that hour. Hours with no lines get no row. The lines are not in time order, and an export can cover one busy hour or a sample from years of traffic.
Write hourly_report(times, sizes).
times[i] is the Unix time, in seconds, when the i-th line was written. sizes[i] is the size of that line in bytes.h covers the seconds from 3600 * h to 3600 * h + 3599.[hour, lines, bytes] for each hour that has at least one line, in increasing order of hour.lines is the number of lines in that hour, and bytes is their total size.Input: times = [100, 4000, 250, 3700, 7300], sizes = [10, 20, 5, 7, 3]
Output: [[0, 2, 15], [1, 2, 27], [2, 1, 3]]The trace finds the hour of each line, then adds the line to that hour's row.
| Step | Read | Hour | Rows after (hour: lines, bytes) |
|---|---|---|---|
| 1 | second 100, 10 bytes | 0 | 0: 1, 10 |
| 2 | second 4000, 20 bytes | 1 | 0: 1, 10 and 1: 1, 20 |
| 3 | second 250, 5 bytes | 0 | 0: 2, 15 and 1: 1, 20 |
| 4 | second 3700, 7 bytes | 1 | 0: 2, 15 and 1: 2, 27 |
| 5 | second 7300, 3 bytes | 2 | 0: 2, 15 and 1: 2, 27 and 2: 1, 3 |
| 6 | sort the hours | rows in order of hour 0, 1, 2 |
Input: times = [], sizes = []
Output: []There are no lines, so there are no rows.
Input: times = [7200, 3599, 3600], sizes = [1, 2, 3]
Output: [[0, 1, 2], [1, 1, 3], [2, 1, 1]]Second 3599 is the last second of hour 0, and second 3600 is the first second of hour 1. The lines arrive in the order of hours 2, 0, 1, but the rows come out in increasing order of hour.
0 ≤ times.length = sizes.length ≤ 100,000 (lines in the log)0 ≤ times[i] ≤ 2,000,000,000 (Unix time, up to the year 2033, so hours run up to 555,555)1 ≤ sizes[i] ≤ 10,000 (bytes in one line)Looking for each line's row by searching a list of rows costs up to one step for every hour that has a row. When every line falls in its own hour, the list grows to 100,000 rows. The searches then cost about 100,000 × 100,000 / 2 = 5 × 10^9 steps, far over the budget of about 10^8 a second. A table keyed by hour finds a row in one step.
hourly_report · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.