Track the user with the most distinct contacts
Stream of (user, contact) pairs; answer top-1 in O(1) and top-k for a changing k.
- Hash map plus linked list (LRU) — O(1) lookup and O(1) recency with two structures that point at each other.
- Heaps and priority queues in object design — Scheduling, ranking and timers with a heap behind a clean interface.
- Designing method signatures — Inputs, outputs, errors and names that make misuse hard.
- Sliding windows and counters — Rate limiters and hit counters as objects with bounded memory.
01The design, in the six-step framework
1. Requirements and use cases
A PhD new-grad phone screen that the candidate failed for picking lists where sets were needed: a stream of (user, contact) events, and the question "who has talked to the most distinct people" answered instantly, then for the top k.
- The system records an event: user u contacted contact c.
- A caller asks for the user with the most distinct contacts in O(1).
- A caller asks for the top k users for a k that changes between calls.
- Repeated contacts between the same pair do not count twice.
- Follow-up: contacts expire after a window, so distinct counts can fall.
Out of scope: persistence, exact behaviour on ties beyond a stated rule, and distribution. Non-functional constraints: record in O(1) average; top-1 in O(1); top-k in O(k) over a small number of distinct count levels; memory proportional to the number of distinct pairs, which is the honest lower bound for exact answers.
2. Core entities and relationships
- ContactTracker: the public object; owns the per-user contact sets and the ranking by distinct count.
- contacts[u]: a set of contacts for user u; its size is the user's distinct count.
- levels[c]: the set of users whose distinct count is c, kept as an ordered dictionary so ties break by who reached that count first.
- max_level: the largest non-empty level.
The tracker composes everything; the sets are private. The design is a frequency container (the same bucket device) where the thing being counted is the size of a set rather than a raw tally. That one difference is the whole trick: a set makes duplicate detection O(1) and makes the count exact, where a list would need an O(n) membership scan or would over-count.
3. Interfaces and key methods
from typing import Generic, Hashable, List, Optional, TypeVar
U = TypeVar("U", bound=Hashable)
C = TypeVar("C", bound=Hashable)
class ContactTracker(Generic[U, C]):
def record(self, user: U, contact: C) -> bool:
"""True if this pair is new; a repeat changes nothing. O(1) average."""
def distinct(self, user: U) -> int:
"""Number of distinct contacts for user; 0 if unknown."""
def top(self) -> Optional[U]:
"""User with the most distinct contacts; ties go to whoever reached that count first."""
def top_k(self, k: int) -> List[U]:
"""Up to k users by distinct count descending with the same tie rule."""
Invariants: level_of[u] == len(contacts[u]) for every known user; u is in levels[c] exactly when level_of[u] == c; max_level is the largest key with a non-empty level; and a user with zero contacts is not tracked at all.
4. Design patterns and the choices behind them
Sets for distinctness, not lists
The force is the word "distinct". A list of contacts per user makes every record an O(n) scan to avoid double counting, or silently over-counts if you skip the scan; this is exactly where the reported candidate lost the round. A set gives O(1) membership and its length is the answer. When asked about memory, the set per user is the lower bound for an exact answer; the approximate alternative (a HyperLogLog per user) is worth naming for very large fan-outs and is a system-design detour, see approximate counting.
Levels indexed by count for O(1) top
The force is "who is first" without sorting. Because a distinct count rises by exactly one per new pair, the user moves from level c to c + 1 and max_level can only rise by one. A max-heap would make record O(log n) and top-1 O(1) but cannot tolerate the expiry follow-up without decrease-key. Heaps are reserved for the case where k is tiny and the levels are many.
Top-k that tolerates a changing k
The force is that k is not known in advance, so precomputing a fixed top list is out. Walking levels from the top collects users in order and stops after k; cost O(k + levels visited). If k were fixed, a bounded heap maintained on every record would answer in O(1), and saying that trade-off shows you listened to the phrase "changing k".
5. Core flow and code
Flow for record("u1", "c9") when u1 has 2 distinct contacts and c9 is new:
- Add
c9tocontacts["u1"]; the set grew, so the pair is new. - Remove
u1from level 2; if level 2 is now empty, delete it. - Append
u1to level 3 and setlevel_of["u1"] = 3; raisemax_levelto 3 if needed. - Return true. A repeated pair returns false at step 1 and touches nothing else.
from collections import OrderedDict
from typing import Dict, Generic, Hashable, List, Optional, Set, TypeVar
U = TypeVar("U", bound=Hashable)
C = TypeVar("C", bound=Hashable)
class ContactTracker(Generic[U, C]):
def __init__(self) -> None:
self.contacts: Dict[U, Set[C]] = {}
self.levels: Dict[int, "OrderedDict[U, None]"] = {}
self.level_of: Dict[U, int] = {}
self.max_level = 0
def record(self, user: U, contact: C) -> bool:
bucket = self.contacts.setdefault(user, set())
if contact in bucket:
return False
bucket.add(contact)
self._move(user, len(bucket) - 1, len(bucket))
return True
def forget(self, user: U, contact: C) -> bool:
"""Expiry hook: drop one pair; the user's level falls by one."""
bucket = self.contacts.get(user)
if not bucket or contact not in bucket:
return False
bucket.remove(contact)
self._move(user, len(bucket) + 1, len(bucket))
if not bucket:
del self.contacts[user]
return True
def _move(self, user: U, old: int, new: int) -> None:
if old:
del self.levels[old][user]
if not self.levels[old]:
del self.levels[old]
if self.max_level == old:
self.max_level = max(self.levels) if self.levels else 0
if new:
self.levels.setdefault(new, OrderedDict())[user] = None
self.level_of[user] = new
self.max_level = max(self.max_level, new)
else:
self.level_of.pop(user, None)
def distinct(self, user: U) -> int:
return self.level_of.get(user, 0)
def top(self) -> Optional[U]:
if not self.max_level:
return None
return next(iter(self.levels[self.max_level]))
def top_k(self, k: int) -> List[U]:
out: List[U] = []
for level in sorted(self.levels, reverse=True):
for user in self.levels[level]:
if len(out) == k:
return out
out.append(user)
return out
class WindowedContactTracker(ContactTracker[U, C]):
"""Expiry follow-up: pairs older than `window` events are forgotten (count-based window)."""
def __init__(self, window: int) -> None:
super().__init__()
self.window = window
self.history: List[tuple] = [] # (user, contact) in arrival order
self.last_seen: Dict[tuple, int] = {}
self.tick = 0
def record(self, user: U, contact: C) -> bool:
self.tick += 1
self.last_seen[(user, contact)] = self.tick
self.history.append((user, contact))
fresh = super().record(user, contact)
while len(self.history) > self.window:
old_user, old_contact = self.history.pop(0)
if self.last_seen.get((old_user, old_contact), 0) <= self.tick - self.window:
self.forget(old_user, old_contact)
return fresh
if __name__ == "__main__":
t: ContactTracker[str, str] = ContactTracker()
for u, c in [("a", "x"), ("a", "y"), ("b", "x"), ("a", "x"), ("c", "x"), ("c", "y"), ("c", "z")]:
t.record(u, c)
assert t.distinct("a") == 2 and t.top() == "c" and t.top_k(2) == ["c", "a"]
assert t.top_k(10) == ["c", "a", "b"]
assert t.forget("c", "z") and t.forget("c", "y") and t.top() == "a" # a reached 2 before c
6. Extensions, concurrency and what interviewers probe
- Why not a list. Be explicit: duplicates would count twice, or cost O(n) to detect. This is the question the real interviewer asked.
- Expiry. With a window, counts can fall; the bucket design handles a decrease symmetrically through
_move, which a heap could not without decrease-key. The count-based window in the code generalises to a time window by replacing the tick with a clock. - Memory. O(distinct pairs). If users have millions of contacts each, name HyperLogLog and accept approximate top-k.
- Tie rule. First to reach the count wins here; say it before coding, then keep the insertion order in the level dictionary.
- Thread safety. One lock around
recordandforget; reads can share a read lock because they only walk structures. - Complexity at every stage. The interviewer asked for it after each phase; have the three numbers ready: record O(1), top O(1), top-k O(k + levels).