Loading page…
Practice problem · medium
A monitoring system logs the client id of every request that reaches a service. A client that sends more than a third of all requests may be a runaway script, and the on-call engineer wants a list of them.
You get the log of one hour as a list of client ids. You return every client id that appears more than one third of the time.
Write values_above_a_third(requests).
requests[i] is the client id of the i-th request.requests.length / 3, with integer division rounded down.Input: requests = [4, 9, 4, 4, 9, 9, 5]
Output: [4, 9]The trace counts every id. With n = 7 the bar is 7 / 3 = 2 rounded down, so a count of 3 or more qualifies.
| Step | Read | Counts after | Qualifies now |
|---|---|---|---|
| 1 | 4 | 4: 1 | none |
| 2 | 9 | 4: 1, 9: 1 | none |
| 3 | 4 | 4: 2, 9: 1 | none |
| 4 | 4 | 4: 3, 9: 1 | 4 |
| 5 | 9 | 4: 3, 9: 2 | 4 |
| 6 | 9 | 4: 3, 9: 3 | 4, 9 |
| 7 | 5 | 4: 3, 9: 3, 5: 1 | 4, 9 |
Ids 4 and 9 have 3 requests each, which is above 2, so the output is [4, 9].
Input: requests = [6, 6, 6]
Output: [6]The bar for n = 3 is 1. The id 6 appears 3 times, and the other counts are too small.
Input: requests = [1, 2, 3, 1, 2, 3]
Output: []No id appears more than twice out of 6, so the list is empty.
1 ≤ requests.length ≤ 100,000 (requests in one hour)1 ≤ requests[i] ≤ 10^9 (client ids)A table of counts is built in one pass, about 100,000 steps. Sorting the distinct ids at the end costs very little, because at most two ids can qualify. Three ids above a third would need more than the whole log, so the answer never has more than 2 ids.
values_above_a_third · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.