Design a phone book with concurrent access

01The design, in the six-step framework

1. Requirements and use cases

Reported as an extra round after a shaky system-design interview: an object-oriented phone book, followed quickly by "now many threads use it". The first half is about choosing structures; the second about letting readers through while writers are rare.

• A user adds a contact with a name and one or more numbers.
• A user looks up a contact by exact name in O(1).
• A user searches by prefix of a name and gets matching names in alphabetical order, bounded by a limit.
• A user reverse-looks-up a number to find who owns it.
• A user removes a contact, and every index forgets it.
• Many threads read and a few write concurrently without corrupt results.

Out of scope: fuzzy matching, persistence, and multi-process sharing. Non-functional constraints: exact lookups O(1); prefix search O(length of prefix + results); readers must not block each other; and the three indexes must never disagree, which means one object owns all three.

2. Core entities and relationships

• PhoneBook: the public object; owns the three indexes and the lock; every mutation updates all three under the lock.
• Contact: an immutable value with a name and a tuple of numbers.
• Trie: names by prefix; each node holds children and whether a name ends there.
• ReadWriteLock: readers share, a writer excludes; built from two primitives since the standard library has none.

The phone book composes the dictionary by name, the dictionary by number and the trie: all three exist only to serve it, and only it may write them. Contact is a value object because two contacts with the same fields are the same contact for every purpose here; it also makes the "return a copy" question moot, since callers cannot mutate what they receive (value objects and immutability). The trie is the trie behind a prefix API: nothing outside the phone book knows it exists.

3. Interfaces and key methods

from typing import List, Optional, Tuple


class Contact:
    name: str
    numbers: Tuple[str, ...]


class PhoneBook:
    def add(self, contact: Contact) -> None:
        """Insert or replace by name; rejects a number already owned by a different name."""

    def get(self, name: str) -> Optional[Contact]:
        """Exact-name lookup, O(1)."""

    def search(self, prefix: str, limit: int = 10) -> List[str]:
        """Names starting with prefix, alphabetical, at most limit."""

    def owner_of(self, number: str) -> Optional[str]:
        """Reverse lookup by number."""

    def remove(self, name: str) -> bool:
        """Removes the contact from all three indexes; True if it existed."""

Invariants: a name in by_name is in the trie and every one of its numbers is in by_number pointing back to it; a number maps to at most one name; and the trie contains exactly the names in by_name. These are checked by one private method that tests call after every operation.

4. Design patterns and the choices behind them

Three indexes, one owner

The force is three access patterns: by name, by prefix, by number. Each wants a different structure, and no single structure gives all three their best complexity. The cost is consistency, which is why the phone book is the only writer and every mutation goes through add or remove. Deriving the number index on demand is rejected because reverse lookup would become O(n); a sorted list for prefix search is rejected because inserts become O(n), although it is a fine answer if the interviewer says the book is built once and never changes.

A read-write lock, built honestly

The force is the concurrency follow-up. Phone books are read far more than written, so a mutex that serialises readers wastes the common case. A read-write lock lets any number of readers in and gives a writer exclusive access. Python's standard library does not ship one, so the design includes a small one made from a Condition: a reader count and a writer flag. The version shown prefers writers (new readers wait once a writer is waiting) to avoid starving the rare write. The rejected alternative is copy-on-write (publish a new immutable book on every write); it is elegant and lock-free for readers but copies the trie on every add, which is wrong for frequent writes.

Immutable contacts

The force is safe sharing across threads. If a Contact were mutable, a reader could observe a half-updated list of numbers while a writer changes it. Freezing Contact means a reader either sees the old object or the new one, never a mix, and the book can hand out references without copying. That is the encapsulation boundary that makes the locking story simple.

5. Core flow and code

Flow for add(Contact("Asha", ("98", "77"))) when a different Asha already exists:

1. Acquire the write lock; no readers or writers are inside.
2. Check each number: if one is owned by another name, raise before touching anything.
3. Remove the old Asha's numbers from by_number (the trie already has the name).
4. Write the new contact into by_name, its numbers into by_number, ensure the trie has the name; release the lock.

import threading
from contextlib import contextmanager
from dataclasses import dataclass
from typing import Dict, Iterator, List, Optional, Tuple


@dataclass(frozen=True)
class Contact:
    name: str
    numbers: Tuple[str, ...]


class TrieNode:
    __slots__ = ("children", "terminal")

    def __init__(self) -> None:
        self.children: Dict[str, "TrieNode"] = {}
        self.terminal = False


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.terminal = True

    def delete(self, word: str) -> None:
        path = [self.root]
        for ch in word:
            nxt = path[-1].children.get(ch)
            if nxt is None:
                return
            path.append(nxt)
        path[-1].terminal = False
        for i in range(len(word), 0, -1):          # prune empty branches upward
            if path[i].children or path[i].terminal:
                break
            del path[i - 1].children[word[i - 1]]

    def with_prefix(self, prefix: str, limit: int) -> List[str]:
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return []
        out: List[str] = []
        self._collect(node, prefix, limit, out)
        return out

    def _collect(self, node: TrieNode, acc: str, limit: int, out: List[str]) -> None:
        if len(out) >= limit:
            return
        if node.terminal:
            out.append(acc)
        for ch in sorted(node.children):            # alphabetical order
            self._collect(node.children[ch], acc + ch, limit, out)


class ReadWriteLock:
    """Writer-preferring: once a writer waits, new readers queue behind it."""

    def __init__(self) -> None:
        self.cond = threading.Condition()
        self.readers = 0
        self.writer = False
        self.waiting_writers = 0

    @contextmanager
    def read(self) -> Iterator[None]:
        with self.cond:
            while self.writer or self.waiting_writers:
                self.cond.wait()
            self.readers += 1
        try:
            yield
        finally:
            with self.cond:
                self.readers -= 1
                if self.readers == 0:
                    self.cond.notify_all()

    @contextmanager
    def write(self) -> Iterator[None]:
        with self.cond:
            self.waiting_writers += 1
            while self.writer or self.readers:
                self.cond.wait()
            self.waiting_writers -= 1
            self.writer = True
        try:
            yield
        finally:
            with self.cond:
                self.writer = False
                self.cond.notify_all()


class PhoneBook:
    def __init__(self) -> None:
        self.by_name: Dict[str, Contact] = {}
        self.by_number: Dict[str, str] = {}
        self.names = Trie()
        self.lock = ReadWriteLock()

    def add(self, contact: Contact) -> None:
        with self.lock.write():
            for n in contact.numbers:
                owner = self.by_number.get(n)
                if owner is not None and owner != contact.name:
                    raise ValueError(f"number {n} belongs to {owner}")
            old = self.by_name.get(contact.name)
            if old is not None:
                for n in old.numbers:
                    self.by_number.pop(n, None)
            self.by_name[contact.name] = contact
            for n in contact.numbers:
                self.by_number[n] = contact.name
            self.names.insert(contact.name)

    def get(self, name: str) -> Optional[Contact]:
        with self.lock.read():
            return self.by_name.get(name)

    def search(self, prefix: str, limit: int = 10) -> List[str]:
        with self.lock.read():
            return self.names.with_prefix(prefix, limit)

    def owner_of(self, number: str) -> Optional[str]:
        with self.lock.read():
            return self.by_number.get(number)

    def remove(self, name: str) -> bool:
        with self.lock.write():
            contact = self.by_name.pop(name, None)
            if contact is None:
                return False
            for n in contact.numbers:
                self.by_number.pop(n, None)
            self.names.delete(name)
            return True


if __name__ == "__main__":
    book = PhoneBook()
    book.add(Contact("Asha", ("98",)))
    book.add(Contact("Ashok", ("77", "66")))
    assert book.search("Ash") == ["Asha", "Ashok"] and book.owner_of("66") == "Ashok"
    book.add(Contact("Asha", ("55",)))            # replace: 98 is released
    assert book.owner_of("98") is None and book.owner_of("55") == "Asha"
    assert book.remove("Ashok") and book.search("Asho") == []

6. Extensions, concurrency and what interviewers probe

• Readers while a writer waits. Say which side your lock prefers and why; writer preference stops a stream of readers from starving the occasional add. Reader preference is right when writes happen once at startup.
• Lock granularity. One lock over all three indexes is correct because a write must update them atomically; per-index locks would let a reader see a name in the trie that is not yet in by_name.
• Case and normalisation. Store a normalised key (lower-case, trimmed) in the trie and the map, keep the display name on the Contact; mention it before the interviewer does.
• Prefix results ordering. Sorting children at each node keeps alphabetical order with no global sort; the cost is O(k log k) per node over a small alphabet.
• What to test first. The consistency invariant after add, replace and remove; then two threads adding the same number to different names, exactly one of which must fail.
• Common mistake. Returning the internal list from the trie or exposing by_name, which lets a caller mutate state outside the lock. Frozen contacts and fresh result lists close that door.

02Where this question was reported

• LeetCode Discuss · LeetCode 379 (Medium), Google-tagged, freq 16.6
• 1point3acres · OOD Phone Book; follow-ups on multithreading / concurrent access
• Glassdoor · LLD on hashmaps for a phone directory (snippet only)
• 1point3acres · Extra round: OOD Phone Book; follow-up on multithreading/concurrency (snippet only)