You are given a stream of customer visits. Each visit contains one positive integer customerId. A customer is a one-time visitor if they have appeared exactly once in the stream so far.
Design a data structure that records customer visits and returns the earliest customer who has visited exactly once. If more than one customer has visited exactly once, return the one whose only visit happened first. If no such customer exists, return -1.
Method Signatures
Record Customer Visit
void postCustomerVisit(int customerId)
- Records one new visit for
customerId.
- If the customer has already visited before, their total visit count increases by one.
Get First One-Time Visitor
int getFirstOneTimeVisitor()
- Returns the first customer who has visited exactly once so far.
- Returns
-1 if every visited customer has visited more than once or no customer has visited so far.
Return Order
- If multiple customers have visited exactly once, return the customer whose first and only visit appeared earliest in the stream.
Constraints
1 ≤ customerId ≤ 1,000,000,000- At most
100,000 total method calls will be made.
Examples
Example 1
postCustomerVisit(customerId = 10)
postCustomerVisit(customerId = 20)
postCustomerVisit(customerId = 10)
postCustomerVisit(customerId = 30)
getFirstOneTimeVisitor() returns 20
Customer 10 visited twice, while customers 20 and 30 visited once. Customer 20 is the earliest one-time visitor.
Example 2
Continuing from Example 1:
postCustomerVisit(customerId = 20)
postCustomerVisit(customerId = 40)
getFirstOneTimeVisitor() returns 30
Customer 20 is no longer a one-time visitor. Customer 30 is now the earliest customer with exactly one visit.
Example 3
postCustomerVisit(customerId = 7)
postCustomerVisit(customerId = 7)
postCustomerVisit(customerId = 8)
postCustomerVisit(customerId = 8)
getFirstOneTimeVisitor() returns -1
Both customers have visited more than once, so there is no one-time visitor.