Arrays, Strings & Hash Maps

These three data structures appear in over 60% of coding interview questions. Mastering them is non-negotiable.

Arrays

Arrays are the most fundamental data structure. In interviews, you need to know:

Operation	Time Complexity	When Used
Access by index	O(1)	Direct element lookup
Search (unsorted)	O(n)	Find an element
Insert at end	O(1) amortized	Append element
Insert at position	O(n)	Shift elements right
Delete at position	O(n)	Shift elements left

Key Array Patterns:

# Pattern 1: Two Sum (Hash Map + Array)
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Pattern 2: Reverse in-place
def reverse_array(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Strings

Strings are essentially arrays of characters, but with unique interview patterns:

• Immutability: In Python and Java, strings are immutable. Modifications create new strings (O(n) each time)
• Common operations: Reversal, palindrome check, anagram detection, substring search

# Anagram detection using frequency counting
from collections import Counter

def is_anagram(s, t):
    return Counter(s) == Counter(t)

# Palindrome check
def is_palindrome(s):
    s = s.lower()
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Hash Maps (Dictionaries)

Hash maps provide O(1) average-case lookup and are the most important tool for interview optimization.

When to Use a Hash Map:

• You need to count frequencies
• You need O(1) lookup by key
• You need to group elements
• You need to detect duplicates
• The brute force is O(n^2) and you want O(n)

# Group anagrams using hash map
def group_anagrams(strs):
    groups = {}
    for s in strs:
        key = tuple(sorted(s))
        if key not in groups:
            groups[key] = []
        groups[key].append(s)
    return list(groups.values())

# First non-repeating character
def first_unique_char(s):
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    for i, char in enumerate(s):
        if freq[char] == 1:
            return i
    return -1

Interview Tip: When a brute-force solution is O(n^2), ask yourself: "Can a hash map reduce this to O(n)?" The answer is usually yes.

Complexity Cheat Sheet

Data Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Hash Map	O(1)*	O(1)*	O(1)*	O(1)*	O(n)
String	O(1)	O(n)	O(n)	O(n)	O(n)

*Average case. Worst case for hash map operations is O(n) due to collisions.

---

Next, we'll cover linked lists, stacks, and queues -- structures that test your pointer manipulation skills. :::