This question evaluates a candidate's ability to design an efficient online data structure that maintains a stream of login events and supports constant-time updates and queries for the earliest user with exactly one login.
You are given an online stream of user login events. Each event is a user ID (e.g., an integer or string) indicating that this user has just logged in.
You need to design a data structure that supports two operations:
login(userId)
userId
has logged in
one more time
.
firstUser()
null
or
-1
) if no such user exists.
Requirements:
login
and
firstUser
must run in
O(1) worst-case time per operation
.
userId
(e.g., integer or string), but specify your assumptions.
Example:
Suppose the login stream is:
login(A)
// A has logged in once
login(B)
// B has logged in once; A is still first unique
login(A)
// A now has logged in twice
login(C)
// C has logged in once
Then the sequence of firstUser() calls should return:
login(A)
:
firstUser()
→
A
login(B)
:
firstUser()
→
A
(A and B are unique, A is earlier)
login(A)
:
firstUser()
→
B
(A is no longer unique)
login(C)
:
firstUser()
→
B
(B is still the earliest unique user)
Design the data structure and its operations to meet the time complexity guarantees. You do not need to handle persistence or multi-threading; focus on the core algorithm and data organization.