Algorithms & Data Structuresmedium

Access-Log Query System

You receive access-log records (userId, action, timestamp), appended in non-decreasing timestamp order. Design AccessLog:

add(userId, action, ts)
getUserActions(userId, start, end)  // that user's actions with
                                    // start <= ts <= end, in time order
countUniqueUsers(start, end)        // distinct users with at least one
                                    // record in [start, end]

add: (u1,"view",1) (u2,"click",2) (u1,"save",5) (u3,"view",5) (u1,"view",9)
getUserActions("u1", 2, 9)  => ["save", "view"]
countUniqueUsers(2, 5)      => 3     (u2@2, u1@5, u3@5)
countUniqueUsers(6, 8)      => 0

Both bounds are inclusive. Aim for logarithmic query time in the number of records, and write the binary searches yourself rather than reaching for a library.

Hints

Hint 1

Keep two indexes: per-user lists of (ts, action), and one global timestamp-sorted list of (ts, userId). Appends stay O(1) amortized because input arrives in time order.

Hint 2

getUserActions is lowerBound(start) to upperBound(end) on that user's timestamps — first index with ts >= start, first index with ts > end.

Hint 3

countUniqueUsers: bisect the global list to the window, then count distinct userIds in it with a set.

Hints

Asked at