3 · Hash maps, sets, counting and grouping Code

dict/set/Counter/defaultdict · frequency maps · group-by keys · the pattern behind most NPE coding questions

Why it matters for NPE. Firsthand reports of the NPE coding screen describe grouping and counting over records (hosts, logs, users). A dictionary keyed by the right thing solves most of them in O(n).

Primer: the question is always "what is the key?"

Almost every NPE coding problem reduces to: pick a key, map each record to it, aggregate. Count failures per host (key = host). Group anagrams (key = sorted letters). Find duplicates (key = the value itself, store in a set). Two Sum (key = the complement you still need). Group IPs by subnet (key = the /24). Once you can name the key in the first 30 seconds, the code is five lines and the interviewer moves on to follow-ups you can handle.

Watch

The toolbox

from collections import Counter, defaultdict

seen = set()                       # membership / dedup
if x in seen: ...                  # O(1) expected
seen.add(x)

count = {}                         # manual count
count[k] = count.get(k, 0) + 1

count = Counter(items)             # same thing in one line; missing key → 0
count.most_common(3)               # [(k, n), ...] sorted by n desc (ties: insertion order)
count.total()                      # 3.10+; sum(count.values()) otherwise

groups = defaultdict(list)         # group-by
groups[key].append(item)           # never KeyError; creates the list on first touch

index = {rec.id: rec for rec in records}   # build a lookup table once, O(n), then O(1) per query

a & b, a | b, a - b, a ^ b         # set intersection, union, difference, symmetric difference
set(a).issubset(b)                 # "is every needed item available"

Choosing a canonical key

Two records belong together when their keys are equal, so the key must be the same for every member of the group and hashable.

• Anagrams: ''.join(sorted(word)) (O(L log L) per word) or a 26-count tuple (O(L)). Both are hashable; a list is not.
• Case/whitespace variants: normalise first: host.strip().lower(). Decide and say whether web-01 and WEB-01 are the same host.
• IP by subnet: ipaddress.ip_network(f'{ip}/24', strict=False) or, for /24 only, ip.rsplit('.', 1)[0]. Mention the library; it is standard.
• Composite keys: a tuple (host, interface). Never a concatenated string with a separator that could appear in the data.
• Floats as keys are a smell (0.1 + 0.2); round or use ints.

Worked examples

Two Sum (lookup before insert)

def two_sum(nums, target):
    need = {}                         # value → index
    for i, x in enumerate(nums):
        if target - x in need:        # look first…
            return [need[target - x], i]
        need[x] = i                   # …then record
    return []

O(n) time, O(n) space. The brute force is O(n²) with two loops; say it, then say why the dict kills the inner loop: it answers "have I seen target − x" in O(1).

Group Anagrams

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        groups[''.join(sorted(w))].append(w)
    return list(groups.values())

O(n · L log L). With a count tuple key it is O(n · L). Output order follows first appearance because dicts keep insertion order.

Longest Consecutive Sequence (set + "only start from a run's head")

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:                       # iterate the set, not the list: duplicates would repeat work
        if x - 1 not in s:            # x is the start of a run
            n = 1
            while x + n in s:
                n += 1
            best = max(best, n)
    return best

O(n): every element is visited by the while loop at most once overall, because only run heads start a walk. Without the x − 1 check it degrades to O(n²).

Isomorphic Strings (two-way mapping, not frequency counts)

def isomorphic(s, t):
    if len(s) != len(t): return False
    fwd, back = {}, {}
    for a, b in zip(s, t):
        if fwd.setdefault(a, b) != b or back.setdefault(b, a) != a:
            return False
    return True

Comparing sorted frequency counts fails (bbbaabaa vs aaabbbba have equal counts but different positions). The mapping must be consistent at every index and one-to-one in both directions.

Group IPs by subnet (the reported NPE question shape)

import ipaddress
from collections import defaultdict

def by_subnet(ips, prefix=24):
    groups = defaultdict(list)
    bad = []
    for raw in ips:
        try:
            ip = ipaddress.ip_address(raw.strip())
        except ValueError:
            bad.append(raw); continue
        net = ipaddress.ip_network(f'{ip}/{prefix}', strict=False)
        groups[str(net)].append(str(ip))
    return groups, bad

Follow-ups to expect: "sort subnets by size" (sorted(groups.items(), key=lambda kv: -len(kv[1]))), "top 10 busiest" (heap, topic 7), "what if the list has 10⁹ entries" (stream it; the dict holds at most one entry per distinct subnet).

Cost model you must say out loud

Interview questions

Traps

• Using a list for membership inside a loop: an invisible O(n²).
• Normalising keys inconsistently (lowercasing on insert but not on lookup).
• Mutating a dict while iterating over it. Iterate list(d.items()) if you must delete.
• Assuming most_common breaks ties alphabetically. It keeps insertion order; sort explicitly when the output order is specified.
• Comparing frequency counts when the question is about positions (isomorphic strings, pattern matching).
• Saying O(1) memory for a dict that has one entry per distinct key.
• Forgetting that defaultdict reads create entries, which breaks "how many distinct hosts did we see" counts.

Do before marking this topic done

1. Without looking: Two Sum, Group Anagrams, Longest Consecutive Sequence. Explain each key choice and complexity out loud.
2. Write by_subnet from memory, then add "return the 3 largest subnets" using sorted and then using a heap.
3. Given events = [(host, status), …], return hosts that were ever DOWN but are currently UP (latest status wins). State the structure before coding.
4. Isomorphic strings with two dicts; then explain why one dict is not enough with a counter-example.

Practice: linked problems

Logged attempts feed the tracker. Open the problem in a new tab, solve in a blank editor, then log honestly.

• LC 1Two SumEasy
• LC 205Isomorphic StringsEasy
• LC 217Contains DuplicateEasy
• LC 242Valid AnagramEasy
• LC 349Intersection of Two ArraysEasy
• LC 350Intersection of Two Arrays IIEasy
• LC 383Ransom NoteEasy
• LC 387First Unique Character in a StringEasy
• LC 1207Unique Number of OccurrencesEasy
• LC 49Group AnagramsMedium
• LC 128Longest Consecutive SequenceMedium
• LC 1657Determine if Two Strings Are CloseMedium

← 2 · How a packet gets from A to B · all topics · 4 · IPv4, CIDR and subnetting →