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.

Follow-ups

• Write the binary searches by hand — a reported candidate lost this round to an off-by-one on the inclusive bounds.
• Millions of rows: is one index enough? Which query gets slower without a second?
• Many countUniqueUsers calls: offline sort plus sliding window, or approximate with HyperLogLog.