Arrays & Hash Maps
The two data structures behind most interview problems — and when to use each
Knowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
Two s solve the majority of algorithmic problems. Knowing their tradeoffs is fundamental.
Arrays (Python lists):
Access by index: O(1) lst[i] Append: O(1)* lst.append(x) *amortized Insert at index: O(n) lst.insert(0, x) — shifts everything Delete at index: O(n) del lst[0] — shifts everything Search: O(n) x in lst
Hash Maps (Python dicts/sets):
Insert: O(1) average d[key] = val Lookup: O(1) average d[key] Delete: O(1) average del d[key] Search: O(1) average key in d
The swap: trade space for time
python # Problem: find if any two numbers in a list sum to target # O(n²) — check all pairs def two_sum_slow(nums, target): for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return (i, j) # O(n) — use a hash map to remember what we've seen def two_sum_fast(nums, target): seen = {} # value → index for i, n in enumerate(nums): complement = target - n if complement in seen: # O(1) lookup return (seen[complement], i) seen[n] = i
Two-pointer technique — works on sorted arrays, O(n): ``python def two_sum_sorted(nums, target): left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: return (left, right) elif s < target: left += 1 else: right -= 1 return None
Sliding window — find a subarray satisfying a condition: ``python def max_sum_subarray(nums, k): window = sum(nums[:k]) best = window for i in range(k, len(nums)): window += nums[i] - nums[i - k] # slide: add right, remove left best = max(best, window) return best
Examples
Frequency counting with dict
Counter is a dict subclass that makes frequency problems trivial
from collections import Counter
def most_common_words(text: str, n: int) -> list[tuple[str, int]]:
words = text.lower().split()
counts = Counter(words) # O(n) to build
return counts.most_common(n) # O(k log k) to sort
text = "the quick brown fox jumps over the lazy dog the fox"
print(most_common_words(text, 3))
# [('the', 3), ('fox', 2), ('quick', 1)]Group anagrams — hash map key design
Key insight: anagrams have the same characters — use sorted tuple as hash key
from collections import defaultdict
def group_anagrams(words: list[str]) -> list[list[str]]:
groups = defaultdict(list)
for word in words:
key = tuple(sorted(word)) # anagrams have same sorted letters
groups[key].append(word)
return list(groups.values())
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]How well did you understand this?
Next in Algorithms & Data Structures
Sorting Algorithms