Design structure for first unique login user

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:

1. login(userId) Record that userId has logged in one more time.

2. firstUser() Return the ID of the user who

   • has logged in exactly once so far, and
   • among all such users, is the earliest by login time (i.e., the one whose first login happened earliest in the stream), or return a special value (e.g., null or -1) if no such user exists.

Requirements:

• Both login and firstUser must run in O(1) worst-case time per operation.
• You can assume the number of distinct users fits in memory.
• You may choose any reasonable representation for 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:

• After login(A): firstUser() → A
• After login(B): firstUser() → A (A and B are unique, A is earlier)
• After login(A): firstUser() → B (A is no longer unique)
• After 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.

First Unique Login User (O(1) Design)

You are given an online stream of user login events. Design a data structure that supports two operations, each in O(1) worst-case time:

1. login(userId): record that userId has logged in one more time.
2. firstUser(): return the ID of the user who has logged in exactly once so far AND, among all such users, was the earliest to log in (by first-login time); return null/None/-1 if no such user exists.

Because the online interface cannot be exercised directly by the grader, implement a single driver function that replays a list of operations and returns the answer to every firstUser() call.

Input: operations is a list of [op, arg] pairs. op is either "login" or "first". For "login", arg is the userId. For "first", arg is ignored (pass null/None). Return a list with one entry per "first" operation, in order: the qualifying userId, or null/None when none exists.

Key idea: keep a doubly linked list of users who are currently unique (count == 1), ordered by first-login time, plus a hash map from userId to its list node and a hash map of login counts. On the first login of a user, append a node at the tail (O(1)). On the second login, unlink that user's node (O(1)). firstUser() returns the userId at the head of the list (O(1)). Subsequent logins (count >= 3) are no-ops for the list.

Example: stream login(A), login(B), login(A), login(C) with a firstUser() after each yields [A, A, B, B] — after A's second login A is no longer unique, so B (the next-earliest unique user) becomes the answer.

Constraints

• Each operation is either login(userId) or firstUser().
• login and firstUser must each run in O(1) worst-case time.
• userId may be an integer or a string; the number of distinct users fits in memory.
• firstUser() returns a sentinel (None / null / -1 / empty) when no user has logged in exactly once.

Hints

1. A user qualifies only while its login count is exactly 1, and 'earliest' means by first-login time — so you need an order-preserving collection of the currently-unique users.
2. A doubly linked list keeps unique users in arrival order and lets you delete an arbitrary user in O(1) when their count rises to 2 — store a hash map from userId to its node so you can find and unlink it instantly.
3. Track each user's login count in a hash map. On the first login, append a node at the tail; on the second login, unlink that node; firstUser() just reads the head node. Once a count reaches 3+, no further list work is needed.