Design a map with constant-time putAll

01The design, in the six-step framework

1. Requirements and use cases

A new-grad phone-screen prompt that looks trivial and is not: a map with a putAll(value) that overwrites every stored key in constant time, which must then interact correctly with later single puts.

• A caller puts a key and value in O(1).
• A caller gets a key in O(1).
• A caller calls putAll(value) and afterwards every key present at that moment reads as value, in O(1) regardless of size.
• A put after a putAll for one key overrides the putAll for that key only; other keys keep the putAll value.
• A key inserted after a putAll is not affected by that earlier putAll.

Out of scope: deletion ordering subtleties beyond a plain remove, iteration, and thread safety unless asked. Non-functional constraints: all three operations O(1); memory O(number of keys) with a constant per key; and the semantics must be stated precisely before coding, because the whole difficulty is the interaction rule in the last two bullets.

2. Core entities and relationships

• VersionedMap: the public object; owns the entries, a global write counter, and the record of the last putAll.
• Entry: a value plus the version (counter value) at which it was written.
• Broadcast: the last putAll as a value plus the version at which it happened.

The map composes its entries and its single Broadcast. The trick is to make time explicit: every write, single or broadcast, takes the next number from one counter. A get then compares two numbers: the entry's own version and the broadcast's version. Whichever is larger is the write that happened last, so its value wins. Nothing is ever rewritten in bulk; the "overwrite everything" is a comparison deferred to read time. This is versioning in its smallest form.

3. Interfaces and key methods

from typing import Generic, Hashable, Optional, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


class VersionedMap(Generic[K, V]):
    def put(self, key: K, value: V) -> None:
        """Set one key; stamps it with the next version."""

    def put_all(self, value: V) -> None:
        """Every key present right now reads as value until individually overwritten. O(1)."""

    def get(self, key: K) -> Optional[V]:
        """The value of the most recent write affecting key: its own put or a later put_all."""

    def remove(self, key: K) -> bool:
        """Forget the key entirely; a later put re-creates it fresh."""

    def __len__(self) -> int: ...

Invariants: versions are strictly increasing across all writes; an entry's version is the version of the last single put to that key; the broadcast version is the version of the last put_all; and get returns the broadcast value exactly when the broadcast version is greater than the entry's version. Keys created after the broadcast automatically have a larger version, which gives the fifth requirement for free.

4. Design patterns and the choices behind them

A logical clock instead of a bulk rewrite

The force is an O(1) operation that semantically touches every key. The only way to touch n things in constant time is to not touch them: record the broadcast once and resolve on read. The rejected alternative, iterating entries in put_all, is O(n) and fails the requirement outright. A second rejected alternative, a "dirty flag" on the map, cannot express "this key was put after the broadcast", which is the interaction the interviewer is really asking about. The monotonically increasing counter is a one-process cousin of the ordering ideas in clocks and ordering.

Resolve at read, not at write

The force is where to pay. Writes are O(1) and never look at other keys; reads do one comparison. Both are O(1), so the choice is about simplicity: a read-time rule is one if-statement in one method, which keeps the class easy to test with a four-line table of scenarios. A write-time rule would need the broadcast to be applied lazily on every subsequent put, which is the same comparison in a less obvious place.

Remove means forget

The force is an ambiguity: should a removed key that is re-inserted after a broadcast see the broadcast? With remove as a true deletion, the re-inserted entry gets a fresh, larger version and does not. State this in the docstring, as method design asks, and the interviewer's follow-up becomes a confirmation instead of a trap.

5. Core flow and code

Flow for put("a", 1); put("b", 2); put_all(9); put("a", 3); get("a"); get("b"):

1. a gets version 1, b version 2.
2. put_all(9) records Broadcast(9, version 3) without visiting entries.
3. put("a", 3) stamps a with version 4.
4. get("a"): entry version 4 is newer than broadcast version 3, so 3 is returned.
5. get("b"): entry version 2 is older than broadcast version 3, so 9 is returned.

from dataclasses import dataclass
from typing import Dict, Generic, Hashable, Optional, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


@dataclass
class Entry(Generic[V]):
    value: V
    version: int


@dataclass(frozen=True)
class Broadcast(Generic[V]):
    value: V
    version: int


class VersionedMap(Generic[K, V]):
    def __init__(self) -> None:
        self.entries: Dict[K, Entry[V]] = {}
        self.broadcast: Optional[Broadcast[V]] = None
        self.clock = 0

    def _tick(self) -> int:
        self.clock += 1
        return self.clock

    def put(self, key: K, value: V) -> None:
        self.entries[key] = Entry(value, self._tick())

    def put_all(self, value: V) -> None:
        self.broadcast = Broadcast(value, self._tick())

    def get(self, key: K) -> Optional[V]:
        entry = self.entries.get(key)
        if entry is None:
            return None
        if self.broadcast is not None and self.broadcast.version > entry.version:
            return self.broadcast.value
        return entry.value

    def remove(self, key: K) -> bool:
        return self.entries.pop(key, None) is not None

    def __contains__(self, key: object) -> bool:
        return key in self.entries

    def __len__(self) -> int:
        return len(self.entries)


class CompactingVersionedMap(VersionedMap[K, V]):
    """Optional extension: fold the broadcast into entries lazily when a key is read,
    so repeated reads of the same key skip the comparison. Same semantics, same big-O."""

    def get(self, key: K) -> Optional[V]:
        entry = self.entries.get(key)
        if entry is None:
            return None
        if self.broadcast is not None and self.broadcast.version > entry.version:
            entry.value = self.broadcast.value
            entry.version = self.broadcast.version
        return entry.value


if __name__ == "__main__":
    m: VersionedMap[str, int] = VersionedMap()
    m.put("a", 1); m.put("b", 2)
    m.put_all(9)
    m.put("a", 3)
    assert m.get("a") == 3 and m.get("b") == 9
    m.put("c", 5)                       # inserted after the broadcast: unaffected
    assert m.get("c") == 5
    m.put_all(0)                        # a second broadcast supersedes the first
    assert m.get("a") == 0 and m.get("c") == 0
    assert m.remove("b") and m.get("b") is None
    cm: CompactingVersionedMap[str, int] = CompactingVersionedMap()
    cm.put("x", 1); cm.put_all(7)
    assert cm.get("x") == 7 and cm.entries["x"].version == cm.broadcast.version  # folded in

6. Extensions, concurrency and what interviewers probe

• The interaction rule. Put after put_all overrides for that key; insert after put_all is unaffected. Write these two cases as the first two tests; they are the whole question.
• Multiple broadcasts. Only the latest matters, because a newer broadcast has a larger version than every entry the older one covered. One field suffices; a history is unnecessary.
• Counter overflow. Python integers do not overflow; in a fixed-width language, say that a 64-bit counter at a billion writes a second lasts about 292 years, so it is not a practical concern.
• Thread safety. The counter increment plus the dictionary write must be atomic together; one lock around put, put_all and remove, and reads can go lock-free only if the interviewer accepts a stale-by-one read.
• Memory. One integer per entry; no copies on broadcast. If the interviewer asks for a bulk operation that is not a constant (for example, add 1 to all), the same trick works with a pending delta applied at read time.
• Common mistake. Storing a boolean "covered by broadcast" on each entry; it cannot distinguish a put before the broadcast from a put after it, which is exactly the case the follow-up tests.

02Where this question was reported

• FastPrep · put/get/putAll class API; interaction of later puts with earlier putAll