Quick Overview

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.

Design structure for first unique login user

Company: Oracle

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

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.

Quick Answer: 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. 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.

Examples

Input: ([['login', 'A'], ['first', None], ['login', 'B'], ['first', None], ['login', 'A'], ['first', None], ['login', 'C'], ['first', None]],)

Expected Output: ['A', 'A', 'B', 'B']

Explanation: The worked example. After A logs in twice it stops being unique, so B (next-earliest unique) becomes the answer; C arriving later does not change the head.

Input: ([['first', None]],)

Expected Output: [None]

Explanation: No logins yet, so there is no user with exactly one login; firstUser() returns None.

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.

Loading coding console...