Deduplicate account sign-ups by email and phone

Process the accounts in order and keep two sets: emails already claimed and phones already claimed. Only accounts that register put anything into these sets.

Brute force. For account i, scan every earlier account that registered and compare its email and phone. That is O(n²) comparisons in the worst case. It is correct, and it is a fine thing to say out loud before you improve it.

Optimal. Replace the scan with two hash sets:

1. Normalize the email and phone (Part 2). An empty value means "not given".
2. If the email is given and is in claimed_emails, the account is a duplicate.
3. If the phone is given and is in claimed_phones, the account is a duplicate.
4. Otherwise the account registers. Add its email and phone (those that are given) to the sets.

Why it works: the rule is defined only against previously registered accounts. The sets hold exactly the emails and phones of registered accounts, so a set lookup answers the same question as the scan. A rejected account never touches the sets, so it cannot block anyone later.

Invariants:

• After step i, claimed_emails and claimed_phones hold exactly the identifiers of the registered accounts among 0..i.
• Emails and phones are separate namespaces. The string "123" as an email does not collide with "123" as a phone.
• The check runs fully before any insert. That matters when one account has the same value in both fields, and it keeps the decision atomic.

names is carried along for the output but plays no part in the decision. Two different people may share a name, and that is fine.

from typing import Optional


def normalize_email(email: Optional[str]) -> str:
    """Trim and lowercase. Empty string means 'not given'."""
    return (email or "").strip().lower()


def normalize_phone(phone: Optional[str]) -> str:
    """Keep digits only, so '+1 (415) 555-0100' == '14155550100'."""
    return "".join(ch for ch in (phone or "") if ch.isdigit())


def register_accounts(
    names: list[str],
    emails: list[Optional[str]],
    phones: list[Optional[str]],
    normalize: bool = True,
) -> list[bool]:
    """Return accepted[i] == True when account i registers successfully."""
    if not (len(names) == len(emails) == len(phones)):
        raise ValueError("names, emails and phones must have the same length")

    claimed_emails: set[str] = set()
    claimed_phones: set[str] = set()
    accepted: list[bool] = []

    for email, phone in zip(emails, phones):
        if normalize:
            e, p = normalize_email(email), normalize_phone(phone)
        else:
            e, p = email or "", phone or ""

        duplicate = (e != "" and e in claimed_emails) or (
            p != "" and p in claimed_phones
        )
        if duplicate:
            accepted.append(False)
            continue

        if e:
            claimed_emails.add(e)
        if p:
            claimed_phones.add(p)
        accepted.append(True)

    return accepted


def split_accounts(
    names: list[str], emails: list[Optional[str]], phones: list[Optional[str]]
) -> tuple[list[str], list[str]]:
    """Convenience: (registered names, duplicate names), in input order."""
    flags = register_accounts(names, emails, phones)
    ok = [n for n, f in zip(names, flags) if f]
    dup = [n for n, f in zip(names, flags) if not f]
    return ok, dup


if __name__ == "__main__":
    names = ["Ana", "Ben", "Cy", "Dee", "Eli"]
    emails = ["ana@x.io", "ben@x.io", "ana@x.io", "dee@x.io", "cy@x.io"]
    phones = ["111", "222", "333", "222", "333"]
    # Cy reuses Ana's email -> rejected; Dee reuses Ben's phone -> rejected.
    # Eli reuses Cy's phone, but Cy never registered -> accepted.
    assert register_accounts(names, emails, phones) == [True, True, False, False, True]
    assert split_accounts(names, emails, phones) == (["Ana", "Ben", "Eli"], ["Cy", "Dee"])

    assert register_accounts([], [], []) == []
    # Same value in both fields of one account is not a self-collision.
    assert register_accounts(["A"], ["5"], ["5"]) == [True]
    # Missing phone never collides.
    assert register_accounts(["A", "B"], ["a@x", "b@x"], ["", None]) == [True, True]
    # Normalization: case, spaces and phone formatting.
    assert register_accounts(
        ["A", "B", "C"],
        ["Ann@X.io", " ann@x.io ", "c@x.io"],
        ["+1 (415) 555-0100", "999", "14155550100"],
    ) == [True, False, False]
    # Raw mode keeps exact matching.
    assert register_accounts(["A", "B"], ["A@x", "a@x"], ["1", "2"], normalize=False) == [True, True]
    print("all tests pass")

• register_accounts: O(n · L) time, where L is the longest email or phone (hashing and normalizing each string). With bounded string length this is O(n). Each lookup and insert is O(1) on average.
• Space: O(n · L) for the two sets plus O(n) for the output.
• The brute force is O(n² · L) time and O(n) space.

• emails = ["ana@x.io", "ben@x.io", "ana@x.io", "dee@x.io", "cy@x.io"], phones = ["111", "222", "333", "222", "333"] → [True, True, False, False, True]. The last account reuses a phone that only a rejected account had, so it registers.
• Empty input → [].
• One account → [True].
• All accounts share one email → [True, False, False, ...].
• Same value in an account's email and phone ("5", "5") → [True]. The namespaces are separate.
• Phone missing ("" or None) on several accounts → none of them collide on phone.
• Case and whitespace: "Ann@X.io" then " ann@x.io " → [True, False] with normalization.
• Phone formatting: "+1 (415) 555-0100" then "14155550100" → [True, False].
• Same names, different email and phone → both register.
• Lists of different lengths → ValueError.

1. Stricter email normalization. Some providers ignore dots and +tag in the local part (a.b+x@gmail.com is ab@gmail.com). Make normalization a per-domain function passed in. The core loop does not change; only the key does. Discuss the risk of false merges for providers that do not follow that rule.
2. Streaming / online API. Turn the function into a class with register(name, email, phone) -> bool. The two sets become instance state. To be safe under concurrency, the check and the insert must be atomic: a lock in-process, or unique indexes on email and phone in the database with the insert as the check (catch the unique-violation error).
3. Deletion. Support delete(account_id) that frees the email and phone. Store email -> account_id and phone -> account_id maps instead of sets so you know what to remove. Ask whether a freed identifier can be reclaimed at once or after a cooling-off period (then store a release timestamp).
4. Group the duplicates (merge accounts). Instead of rejecting, report which registered account each duplicate collided with, or cluster all accounts that are linked by any shared email or phone, transitively. Use the maps from follow-up 3 for the direct case; use union-find over account indices for the transitive case (LeetCode "Accounts Merge" style), O(n · α(n)).
5. More identifiers / scale. Add more fields (device id, payment fingerprint). Generalize to a dict of field -> set. At large scale, shard each set by a hash of the key, or use a Bloom filter as a fast negative check before an exact lookup.

Mid-level (L4)

• Reads the rule correctly: rejected accounts do not claim their email or phone.
• Uses two hash sets, gets O(n), and writes clean code without bugs.
• Tests the "rejected account frees nothing" case and empty input.

Senior (L5)

• Asks clarifying questions: missing values, case sensitivity, phone formatting, what to return.
• Separates normalization from the dedup loop and keeps the namespaces separate.
• Handles follow-ups 2 and 3 cleanly: a class API, maps instead of sets, atomic check-then-insert.

Staff (L6+)

• Connects the toy to production: unique constraints in the database as the real source of truth, race conditions between two signups, idempotent retries.
• Discusses the product trade-off of aggressive normalization (fraud prevention versus false merges blocking real users) and how to roll out a rule change over existing data.
• Moves to identity clustering with union-find and explains how it scales and how to explain a merge decision to support staff.