Perfect.
DICTIONARY MASTERY – DAY 2 is the heart of dict interview problems.
If you master today, 50–60% of Python coding interviews become routine.

🔥 DICTIONARY MASTERY — DAY 2

Frequency Maps, Grouping, Prefix-Hash Patterns & Core Interview Problems

🧠 DAY 2 GOAL

By the end of today, you will:

• Instantly recognize frequency-map problems
• Use dicts to collapse O(n²) → O(n)
• Solve grouping & counting problems fluently
• Explain hash-based reasoning clearly (interview-critical)

🧩 CORE DICT PATTERNS (MEMORIZE)

If you identify the pattern → solution is mechanical.

1️⃣ FREQUENCY MAP PATTERN (MOST IMPORTANT)

Used when:

• Count occurrences
• First/last unique
• Majority element
• Constraints mention “frequency”, “count”, “unique”

🔥 Q1. Character Frequency Count

s = "banana"

Optimal

from collections import defaultdict

freq = defaultdict(int)
for ch in s:
    freq[ch] += 1

Why defaultdict?

• No key checks
• Cleaner
• Faster in loops

Interview line:

“I’ll use a frequency map with O(n) time.”

🔥 Q2. First Non-Repeating Character

"swiss" → 'w'

Pattern Solution

from collections import Counter

def first_unique(s):
    freq = Counter(s)
    for ch in s:
        if freq[ch] == 1:
            return ch
    return None

🧠 Dict preserves insertion order → single pass

🔥 Q3. Majority Element (> n/2)

[2,2,1,2,3,2,2] → 2

Dict Approach

def majority(nums):
    freq = {}
    n = len(nums)
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
        if freq[x] > n // 2:
            return x

Interview bonus:

• Mention Boyer–Moore as O(1) space alternative

2️⃣ GROUPING PATTERN (VERY COMMON)

Used when:

• “Group by…”
• Anagrams
• Bucketing values

🔥 Q4. Group Anagrams (CLASSIC)

["eat","tea","tan","ate","nat","bat"]
→ [["eat","tea","ate"],["tan","nat"],["bat"]]

Optimal

from collections import defaultdict

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

🧠 Key insight:

• Dict key must be hashable → tuple
• Sorted string groups anagrams

Interview note:

• Time: O(n·k log k)
• Space: O(n)

🔥 Alternative (Advanced, Faster)

Use character counts as key (O(k))
Mentioning this = senior signal.

3️⃣ PREFIX HASH PATTERN (CRITICAL)

Used when:

• Subarray problems
• Running totals
• “Sum equals k”
• Negative numbers allowed

🔥 Q5. Subarray Sum Equals K

nums = [1,2,3], k=3 → 2

Optimal

from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1
    curr = 0
    count = 0

    for x in nums:
        curr += x
        count += seen[curr - k]
        seen[curr] += 1

    return count

🧠 Interview explanation:

• Hash cumulative sums
• Look backward in O(1)

4️⃣ LAST-SEEN INDEX PATTERN

Used when:

• Longest substring
• Window without repetition
• Distance constraints

🔥 Q6. Longest Substring Without Repeating Characters

"abcabcbb" → 3

Dict-Based Sliding Window

def longest_unique(s):
    last = {}
    left = 0
    max_len = 0

    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1

        last[ch] = right
        max_len = max(max_len, right - left + 1)

    return max_len

Why dict instead of set?

• Jump window in O(1)
• No repeated shrinking

5️⃣ TWO-SUM & COMPLEMENTS (INTERVIEW STAPLE)

🔥 Q7. Two Sum

nums = [2,7,11,15], target=9 → [0,1]

Optimal

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i

🧠 Pattern:

• Store complements
• One pass
• O(n)

6️⃣ DICT AS STATE (ADVANCED THINKING)

Dicts are not just storage — they track state.

Examples:

• DP memoization
• Caching
• Visited states
• LRU cache (Day 3)

Mentioning this in interviews = strong signal.

🔥 COMMON DICT INTERVIEW TRAPS 🚨

❌ Using list instead of dict for frequency

if x in lst:   # O(n)

❌ Modifying dict during iteration

for k in d:
    d.pop(k)  # RuntimeError

❌ Forgetting tuple conversion for keys

d[list_key] = ...  # ❌

🧠 DICT INTERVIEW MENTAL MAP

When you see a problem:

1. Counting? → Frequency dict
2. Grouping? → Dict of lists
3. Subarray? → Prefix hash
4. Pair sum? → Complement map
5. Longest window? → Last seen index

Say this aloud → interviewer confidence boost.

📝 DAY 2 ASSIGNMENT (MANDATORY)

1️⃣ Predict output (NO RUNNING)

from collections import defaultdict

d = defaultdict(list)
d["a"].append(1)
print(d["b"])

2️⃣ Coding (IMPORTANT)

def longest_subarray_sum_equals_k(nums, k):
    """
    Works with negatives
    """

3️⃣ Explain (Interview style)

Why prefix-sum + hash map works even with negative numbers.

🔜 NEXT — DICTIONARY MASTERY DAY 3 🔥

DAY 3

• LRU cache (design + code)
• OrderedDict vs dict
• defaultdict vs Counter vs dict
• Real-world design questions
• 30+ rapid-fire dict interview drills

👉 Say “CONTINUE DICTIONARY MASTERY – DAY 3” when ready 🚀