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.

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.

Read the full Oracle Software Engineer interview experience this question came from

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...