← 返回 uber 的题目列表Visitors Visited Exactly Once As Of a Timestamp (OOD / Time-indexed design)
类型：online_judge
Problem
Design a class/interface to record visitor events. Each visit event contains visitorName (string) and timestamp (integer).
Support:
addVisit(visitorName, timestamp): record one visit event.
queryOnceVisitors(timestamp): given a timestamp, return the set of visitors whose total number of visits in all events with time <= timestamp is exactly 1 (any order).
Constraints / Requirements
Timestamps may arrive out of order; clarify how your design handles this.
A visitor can visit multiple times.
Consider large scale and aim for efficient queries and reasonable storage.
Example
Calls:
addVisit("alice", 1)
addVisit("bob", 2)
addVisit("alice", 3)
addVisit("cathy", 4)
Results:
queryOnceVisitors(2) -> {"alice","bob"}
queryOnceVisitors(3) -> {"bob"}
queryOnceVisitors(10) -> {"bob","cathy"}
Example
Input
addVisit(alice,1)
addVisit(bob,2)
addVisit(alice,3)
addVisit(cathy,4)
queryOnceVisitors(2)
Output
{alice,bob}