Oldest one-time visitor in a login stream

This is "first unique element in a stream" in product clothing. Logins arrive one at a time; at any moment we must answer: of the users who have logged in exactly once, which one logged in earliest?

Brute force. Append every login to a list and keep a Counter. To answer a query, scan the list from the front and return the first name whose count is 1. Logins are O(1), but every query is O(n) in the total number of logins. That is worth saying first, because it shows the two things we need: counts, and arrival order of first logins.

Better but leaky: queue + lazy deletion. Keep a Counter and a queue of first logins. On a query, pop from the front while the front user's count is above 1, then return the front. Each name is popped at most once, so queries are amortized O(1). It works, but the queue holds stale names until a query happens to clean them up, and a single query can take O(n) in the worst case. Good to mention; interviewers often accept it, then ask for strict O(1).

Optimal: hash map + insertion-ordered set of one-time visitors.

• seen: every username that has ever logged in. A user never leaves this set.
• once: an insertion-ordered structure (a doubly linked list plus a dict, or Python's OrderedDict) holding exactly the users with one login, in the order of that login.

Operations:

• login(user):
  • If user is not in seen: add it to seen and append it to the end of once.
  • Else if user is in once: this is the second login, so remove it from once in O(1).
  • Else: third or later login, nothing changes.
• oldest_one_time_visitor(): return the first key of once, or None if it is empty.

Why it works: a user enters once exactly at their first login, so the order of once is the order of first logins. A user leaves at their second login and can never come back, because seen remembers them. So the head of once is always the earliest user whose count is exactly 1.

Writing the linked list by hand is what most interviewers want to see once you mention OrderedDict, so the code below does that, with sentinel nodes to avoid None checks.

Invariants.

• user in self.nodes if and only if the user has exactly one login.
• The list between the sentinels holds those users in order of their first (and only) login.
• self.seen is a superset of self.nodes.

from __future__ import annotations

from typing import Optional


class _Node:
    __slots__ = ("user", "prev", "next")

    def __init__(self, user: str = "") -> None:
        self.user = user
        self.prev: Optional[_Node] = None
        self.next: Optional[_Node] = None


class OneTimeVisitorTracker:
    """Tracks logins and returns the earliest user who has logged in exactly once."""

    def __init__(self) -> None:
        self.seen: set[str] = set()          # everyone who ever logged in
        self.nodes: dict[str, _Node] = {}     # users with exactly one login
        self.head = _Node()                   # sentinel: before the oldest
        self.tail = _Node()                   # sentinel: after the newest
        self.head.next = self.tail
        self.tail.prev = self.head

    def _append(self, node: _Node) -> None:
        last = self.tail.prev
        assert last is not None
        last.next = node
        node.prev = last
        node.next = self.tail
        self.tail.prev = node

    @staticmethod
    def _unlink(node: _Node) -> None:
        assert node.prev is not None and node.next is not None
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None

    def login(self, user: str) -> None:
        if user not in self.seen:
            self.seen.add(user)
            node = _Node(user)
            self.nodes[user] = node
            self._append(node)
        elif user in self.nodes:
            # Second login: no longer a one-time visitor, and never will be again.
            self._unlink(self.nodes.pop(user))
        # Third or later login: nothing to do.

    def oldest_one_time_visitor(self) -> Optional[str]:
        first = self.head.next
        return None if first is self.tail else first.user  # type: ignore[union-attr]

    def one_time_visitor_count(self) -> int:
        return len(self.nodes)


if __name__ == "__main__":
    t = OneTimeVisitorTracker()
    assert t.oldest_one_time_visitor() is None
    for u in ["ana", "ben", "cy"]:
        t.login(u)
    assert t.oldest_one_time_visitor() == "ana"
    t.login("ana")
    assert t.oldest_one_time_visitor() == "ben"
    t.login("ana")  # third login changes nothing
    t.login("ben")
    assert t.oldest_one_time_visitor() == "cy"
    t.login("cy")
    assert t.oldest_one_time_visitor() is None
    t.login("dee")
    assert t.oldest_one_time_visitor() == "dee"
    t.login("ana")  # repeat user never comes back
    assert t.oldest_one_time_visitor() == "dee"
    assert t.one_time_visitor_count() == 1
    print("ok")

• login: O(1) average time (one or two hash operations plus constant pointer updates).
• oldest_one_time_visitor: O(1) time, worst case, not amortized.
• Space: O(U), where U is the number of distinct usernames ever seen. seen must keep every user forever; the linked list holds only current one-time visitors.

For comparison: the scan-the-log brute force is O(n) per query with O(n) space for the full log; the lazy-deletion queue is amortized O(1) per query but O(n) worst case for a single query.

• No logins, then query: None.
• login("ana"), query: "ana".
• login("ana"), login("ben"), login("ana"), query: "ben".
• ana, ben, cy, then ana, ben, query: "cy".
• ana, ana, query: None (the only user is a repeat visitor).
• ana, ana, ana, ben, query: "ben" (a third login does not put ana back).
• ana, ana, ben, ana, query: "ben" (a repeat user logging in later is still not a one-time visitor).
• ana, ben, ana, ben, cy, dee, query: "cy"; then login("cy"), query: "dee".
• Usernames are case-sensitive unless the interviewer says otherwise: Ana and ana are different users.
• Large stream: 10^6 distinct users each logging in once, then the first user logs in again; query returns the second user in O(1).

1. Return the oldest k one-time visitors. Walk k nodes from the head: O(k). No change to the data structure.
2. Only count logins in the last T minutes (sliding window). Each login now carries a timestamp. Keep a deque of (timestamp, user) events and a per-user count within the window. On each call, expire old events from the deque and decrement counts. When a count drops from 2 to 1, the user becomes a one-time visitor again, but their remaining login is no longer their first, so the list is no longer append-only. Order the one-time visitors by the timestamp of their single in-window login, using a sorted container or a heap with lazy deletion: O(log n) per event.
3. Users can be deleted (GDPR, account closed). Remove from seen; if present in nodes, unlink it. Decide with the interviewer whether a deleted user who returns counts as new. With this structure, they do.
4. Memory: hundreds of millions of distinct users. seen dominates. Store hashed IDs (8 bytes) instead of strings, or use a Bloom filter for seen and accept a small false-positive rate (a true first-timer wrongly treated as a repeat, so they never become a one-time visitor). Say which error direction the product can tolerate.
5. Distributed: logins hit many servers. Shard by hash(username) so every login for one user goes to the same shard, and each shard keeps its own tracker. Each shard's head is its oldest one-time visitor; the global answer is the minimum first-login timestamp across shard heads, kept in a small heap or merged by an aggregator. Ordering across shards needs comparable timestamps (or an ingestion sequence number from a log like Kafka).

Mid-level (L4)

• States the brute force, then reaches hash map + ordered structure without much prompting.
• Handles the third-login case correctly (the user must not reappear).
• Writes working code and traces two or three examples by hand.

Senior (L5)

• Explains why seen and the one-time set must be separate, and states the invariants.
• Compares lazy-deletion queue (amortized) with linked list (worst-case O(1)), and can implement the list without OrderedDict.
• Handles one follow-up cleanly, such as top-k or user deletion, and notes the O(U) memory cost.

Staff (L6+)

• Drives the sliding-window version and explains why it breaks append-only ordering.
• Discusses memory at scale (hashed IDs, Bloom filters and their error direction) and sharding by user with a cross-shard merge on first-login time.
• Raises product questions: what counts as a visit (login vs. session), bots, time zones, and what the answer is used for.