Track Customer Visits and First-Time Visitors
Millions of customers visit our website every day. For each customer we have a unique identifier that is the same every time they visit. We have 2 kinds of customers: Recurrent Visitors that visit more than once and OneTime Visitors, who so far have visited the website only once.
We want to implement a service that has 2 functionalities:
postCustomerVisit(customerId)getFirstOneTimeVisitor()
postCustomerVisit(customerId) records a visit from the given customer.
getFirstOneTimeVisitor() returns the first customer who has visited exactly once so far.
If there is no such customer, return null / None.
网站每天都会有很多用户访问。每个用户都有一个固定不变的唯一 customerId。
目前我们把用户分成两类：
一类是 Recurrent Visitors，也就是访问过不止一次的用户。
另一类是 OneTime Visitors，也就是到当前为止只访问过一次的用户。
现在要你设计一个服务，支持两个操作：
postCustomerVisit(customerId)：记录某个用户又来访问了一次。getFirstOneTimeVisitor()：返回“当前只访问过一次的用户里，最早出现的那个”。
如果当前已经没有只访问过一次的用户了，就返回空。
这道题的重点有两个：
第一，用户访问是不断进来的，说明这是一个动态更新问题。
第二，返回的不是任意一个只访问过一次的用户，而是最早那个，说明还要维护顺序。
我们可以准备两个数据结构：
一个 HashMap，记录每个 customerId 的访问次数。
一个 Queue，按第一次出现的顺序，把用户放进去。
处理逻辑是这样的：
当 postCustomerVisit(customerId) 被调用时：
- 先把这个用户的计数加一
- 如果这是他第一次出现，就把他加入队列尾部
当 getFirstOneTimeVisitor() 被调用时：
- 看队首是不是当前计数为 1
- 如果不是，说明这个人后来又访问过，已经不再是 one-time visitor 了，就把他从队列里弹出去
- 一直弹到队首满足“计数为 1”为止
- 队首就是答案
- 如果队列空了，就返回
None
队列里确实可能会留下“过期用户”，也就是曾经第一次访问时入队，后来又访问过的人。
我们不需要在他第二次访问时，专门跑去队列中间删除他。
因为队列中间删除很麻烦。
我们只要在查询时，懒惰地把这些失效元素从队首清掉就行。
这也是为什么越来越多人开始用 面试辅助。
我们也有代面试，面试辅助，OA代写等服务助您早日上岸~
