How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Oracle.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Oracle during technical interviews.

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.

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

Expected Output: [None]

Explanation: X logs in twice, so it is no longer unique and there are no other users; firstUser() returns None.

Input: ([['login', 1], ['login', 2], ['login', 3], ['login', 1], ['login', 2], ['first', None]],)

Expected Output: [3]

Explanation: Users 1 and 2 each log in twice and drop out; only 3 remains unique, so it is the earliest (and only) qualifying user.

Input: ([['login', 'a'], ['login', 'b'], ['login', 'a'], ['login', 'b'], ['first', None], ['login', 'a'], ['first', None]],)

Expected Output: [None, None]

Explanation: Both a and b reach count 2 and leave the list. A third login of a (count 3) is a no-op, so no unique user ever returns.

Input: ([['login', 5], ['login', 5], ['login', 5], ['first', None], ['login', 7], ['first', None]],)

Expected Output: [None, 7]

Explanation: 5 reaches count 3 (never re-added once removed at count 2). After 7 logs in once it becomes the earliest unique user.

Input: ([['login', 'p'], ['login', 'q'], ['login', 'r'], ['login', 'q'], ['first', None], ['login', 'p'], ['first', None], ['login', 'r'], ['first', None]],)

Expected Output: ['p', 'r', None]

Explanation: q drops out first leaving p, q, r order -> p; then p's second login drops it leaving r; then r's second login empties the list -> None.

Hints

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

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.