Loading page…
Practice problem · medium
A social app logs one event for every like, comment or share. Each event holds the id of the user who did it.
Your team lead asks for a leaderboard of the three most active users of the day. A user's activity is the number of events with their id. If two users have the same activity, the user with the smaller id ranks higher.
Write top_three_users(events).
events[i] is the user id of the i-th event.Input: events = [3, 1, 3, 2, 1, 3, 2]
Output: [3, 1, 2]The trace counts the events, then ranks the users.
| Step | What happens | Table |
|---|---|---|
| 1 | Read 3, 1, 3 | 3: 2, 1: 1 |
| 2 | Read 2, 1, 3 | 3: 3, 1: 2, 2: 1 |
| 3 | Read 2 | 3: 3, 1: 2, 2: 2 |
| 4 | Rank by count, then id | 3 (3), 1 (2), 2 (2) |
| 5 | Keep the first three | 3, 1, 2 |
Users 1 and 2 both have 2 events, so the smaller id, 1, ranks first. The output is [3, 1, 2].
Input: events = [8, 8, 8, 8]
Output: [8]One user, so the leaderboard has one name.
Input: events = [5, 6, 7, 8]
Output: [5, 6, 7]Every user has one event, so the ties go by id: 5, 6, 7. User 8 is cut off.
0 ≤ events.length ≤ 100,000 (events in a day)1 ≤ events[i] ≤ 10^9 (user ids)Counting is one pass of about 100,000 steps. Sorting the d distinct users costs about d log d steps, and with d at most 100,000 that is under 2 million steps, well inside the budget. Picking the best user three times by a scan would also work, but the sort is easier to get right.
top_three_users · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.