Coding Interview Quick Reference

15 Must-Know Problems

Click any card to reveal the solution, complexity, and key insights

#1 Two Sum

Easy Hash Map

Approach: Use dictionary to store seen numbers. For each num, check if complement (target - num) exists.

click to expand

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 []

Time

O(n)

Space

O(n)

Key: Dictionary lookup is O(1). Single pass with complement = target - num.

#2 Valid Anagram

Easy Frequency Count

Approach: Count chars in first string (+1), subtract for second (-1). If any count goes negative, not anagram.

click to expand

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        count[c] = count.get(c, 0) - 1
        if count[c] < 0:
            return False
    return True

Time

O(n)

Space

O(1)

Key: Use .get(key, default) to avoid KeyError. Space is O(1) since at most 26 letters.

#3 Group Anagrams

Medium Hash Map

Approach: Sort each word's characters as key. All anagrams share the same sorted key. Group by key.

click to expand

def group_anagrams(strs):
    groups = {}
    for word in strs:
        key = "".join(sorted(word))
        if key in groups:
            groups[key].append(word)
        else:
            groups[key] = [word]
    return list(groups.values())

Time

O(n × k log k)

Space

O(n × k)

Key: Sorting characters creates identical key for all anagrams. n = words, k = avg word length.

#4 Two Sum II (Sorted Array)

Medium Two Pointers

Approach: Pointers at start and end. Sum too small → move left right. Too large → move right left. Return 1-indexed.

click to expand

def two_sum_sorted(numbers, target):
    left = 0
    right = len(numbers) - 1
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

Time

O(n)

Space

O(1)

Key: Sorted array enables two-pointer approach. O(1) space vs O(n) for hash map. Return 1-indexed!

#5 Best Time to Buy & Sell Stock

Easy Greedy

Approach: Track minimum price seen so far. At each day, calculate profit if sold today. Track max profit.

click to expand

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)
    return max_profit

Time

O(n)

Space

O(1)

Key: Single pass. Track best minimum, calculate profit at each point. float('inf') for initial min.

#6 Valid Parentheses

Easy Stack

Approach: Stack for opening brackets. On closing bracket, pop and check match. Stack must be empty at end.

click to expand

def is_valid(s):
    matching = {')': '(', '}': '{', ']': '['}
    stack = []
    for char in s:
        if char in matching:
            if len(stack) == 0 or stack[-1] != matching[char]:
                return False
            stack.pop()
        else:
            stack.append(char)
    return len(stack) == 0

Time

O(n)

Space

O(n)

Key: stack[-1] accesses top. Dict maps closing→opening. Stack must be empty at end.

#7 Binary Search

Easy Binary Search

Approach: Eliminate half of search space each step. Use mid = (left + right) // 2. Floor division important.

click to expand

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Time

O(log n)

Space

O(1)

Key: Array MUST be sorted. Use // for floor division. left <= right (not just <).

#8 Climbing Stairs

Easy Dynamic Programming

Approach: ways(n) = ways(n-1) + ways(n-2). Fibonacci pattern — track only last two values.

click to expand

def climb_stairs(n):
    if n <= 2:
        return n
    prev2 = 1    # ways to reach step 1
    prev1 = 2    # ways to reach step 2
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1

Time

O(n)

Space

O(1)

Key: Fibonacci pattern. Rolling variables instead of array. Base: n=1→1, n=2→2.

#9 Contains Duplicate

Easy Hash Set

Approach: Loop through array. If number already in set → duplicate. Otherwise add to set.

click to expand

def contains_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

Time

O(n)

Space

O(n)

Key: Set has O(1) lookup. Return immediately on first duplicate. Set stores keys only (no values).

#10 Maximum Subarray

Medium Kadane's

Approach: At each position: extend previous sum or start fresh? If previous sum is negative, start fresh.

click to expand

def max_subarray(nums):
    current_sum = nums[0]
    max_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

Time

O(n)

Space

O(1)

Key: Kadane's algorithm. Decision: extend or restart. max(num, current_sum + num) is the core.

#11 Longest Substring Without Repeating

Medium Sliding Window

Approach: Expand right pointer adding to set. On duplicate, shrink from left. Track max window size.

click to expand

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.discard(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

Time

O(n)

Space

O(min(n, 26))

Key: Sliding window. Window size = right - left + 1. set.discard() won't error if missing.

#12 Reverse Linked List

Easy Linked List

Approach: Three pointers (prev, current, next_node). Reverse .next at each node. Move all forward.

click to expand

def reverse_list(head):
    prev = None
    current = head
    while current:
        next_node = current.next   # save next
        current.next = prev        # reverse link
        prev = current             # advance prev
        current = next_node        # advance current
    return prev

Time

O(n)

Space

O(1)

Key: Save next_node BEFORE reversing. Return prev (new head), not current (which is None).

#13 Merge Two Sorted Lists

Easy Linked List

Approach: Dummy node trick. Compare heads, attach smaller. At end, attach remaining list.

click to expand

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    current = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    current.next = list1 or list2
    return dummy.next

Time

O(n + m)

Space

O(1)

Key: Dummy node avoids edge cases. list1 or list2 picks whichever is not None. Return dummy.next.

#14 Number of Islands

Medium DFS / BFS

Approach: Scan every cell. When '1' found, count as island and DFS to sink all connected '1's to '0'.

click to expand

def dfs(grid, r, c):
    if r < 0 or r >= len(grid) or \
       c < 0 or c >= len(grid[0]) or \
       grid[r][c] == '0':
        return
    grid[r][c] = '0'         # mark visited
    dfs(grid, r-1, c)       # up
    dfs(grid, r+1, c)       # down
    dfs(grid, r, c-1)       # left
    dfs(grid, r, c+1)       # right

def num_islands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':
                count += 1
                dfs(grid, r, c)
    return count

Time

O(rows × cols)

Space

O(rows × cols)

Key: DFS connected components. Bounds checking essential. Mark visited by changing '1' → '0'.

#15 Coin Change

Medium Dynamic Programming

Approach: DP array from 0 to amount. For each amount, try each coin: dp[i] = min(dp[i], dp[i-coin]+1).

click to expand

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Time

O(amount × coins)

Space

O(amount)

Key: Initialize with float('inf'). Bottom-up DP. Try all coins for each sub-amount.

Pattern → Problem Map

Recognize the pattern, apply the template

Pattern	When to Use	Key Data Structure	Problems
Hash Map	Need O(1) lookup, counting, grouping	`dict`	Two Sum, Valid Anagram, Group Anagrams
Two Pointers	Sorted array, find pairs, palindromes	Pointer indices	Two Sum II, Merge Sorted Lists
Sliding Window	Contiguous subarray/substring optimization	`set` or `dict`	Longest Substring Without Repeating
Stack	Matching brackets, nested structure, undo	`list` as stack	Valid Parentheses
Binary Search	Sorted array, find target, minimize/maximize	Pointer indices	Binary Search
Dynamic Programming	Overlapping subproblems, optimal substructure	`list` (dp array)	Climbing Stairs, Coin Change, Max Subarray
DFS / BFS	Graph traversal, connected components, paths	Recursion / Queue	Number of Islands
Linked List	In-place reversal, merge, cycle detection	Node pointers	Reverse List, Merge Two Lists

Python Quick Reference

Essential syntax and patterns for coding interviews

📝 Strings

Length: len(s)
Slice: s[0:5] Reverse: s[::-1]
Split: s.split() Join: '-'.join(list)
Contains: 'hello' in s
F-string: f"Hi {name}"
Upper/Lower: s.upper(), s.lower()

📋 Lists

Create: [1, 2, 3] Last: arr[-1]
Slice: arr[1:3], arr[:3], arr[2:]
Add: .append(x) Remove last: .pop()
Insert: .insert(idx, val)
Sort: sorted(arr) (new) vs arr.sort() (in-place)
Check: 3 in arr

🗂️ Dictionaries

Create: {'a': 1, 'b': 2}
Safe get: d.get('key', 0) — avoids KeyError
Delete: del d['key']
Iterate: d.keys(), d.values(), d.items()
Check: 'key' in d
Counter: count[x] = count.get(x, 0) + 1

🔵 Sets

Create: {1, 2, 3} Empty: set()
Add: s.add(4) Remove: s.discard(3)
Check: 4 in s — O(1) lookup!
Union: s1 | s2 Intersect: s1 & s2
Difference: s1 - s2

🔄 Loops & Iteration

Range: range(5) → 0,1,2,3,4
With step: range(0, 10, 2) → 0,2,4,6,8
Enumerate: for i, val in enumerate(arr):
Zip: for a, b in zip(list1, list2):
Comprehension: [x*2 for x in range(5)]
Dict comp: {x: x*2 for x in range(5)}

⚡ Interview Must-Knows

float('inf') and float('-inf')
collections.Counter("hello") → freq map
collections.defaultdict(list)
collections.deque() → O(1) both ends
heapq.heappush(h, x) — min-heap
sorted(arr, key=lambda x: x[1])
Swap: a, b = b, a
Ternary: x if condition else y

AI Agent Architecture Patterns

6 progressive agent implementations — from basics to production

Level 1 Simple Agent (No API)

Functions as tools + keyword-based tool selection + agent loop

# Tools as Python functions
tools = {"calculator": calc, "weather": weather}

def simple_agent(question):
    tool = pick_tool(question)  # keyword match
    return tools[tool](question)

Core: Tool registry (dict) + tool picker (if/else) + agent loop

Level 2 Async Agent + Pydantic

Concurrent API calls + type-safe request/response models

# 3 API calls in 1s (parallel) vs 3s (serial)
results = await asyncio.gather(
    fetch_supplier("SUP-001"),
    fetch_inventory("ITEM-123"),
    fetch_price("ITEM-123")
)

Core: asyncio.gather() for parallel calls + Pydantic for validation

Level 3 MCP (Model Context Protocol)

Server exposes tools, client discovers and calls them dynamically

# Server registers tools
server.register_tool("search", desc, fn)
# Client discovers & calls
tools = client.discover_tools()
result = client.use_tool("search", args)

Core: register_tool → list_tools → call_tool (server/client pattern)

Level 4 DSPy Agent (LLM Programming)

Structured LLM programming — Signatures, Modules, auto-optimization

# ReAct loop
Step 1: THOUGHT  → decide what to do
Step 2: ACTION   → pick & call a tool
Step 3: OBSERVE  → see the result
Step 4: Repeat or return answer

Core: dspy.Signature → dspy.Predict → dspy.ChainOfThought → dspy.ReAct

Level 5 Real LLM Agent (Function Calling)

LLM decides which tool to use via OpenAI function calling

# LLM picks the tool (not keywords!)
response = openai.chat(
    messages=[{"role": "user", "content": q}],
    tools=tool_descriptions  # JSON schema
)
# Execute tool LLM chose → send result back

Core: Send tools as JSON schema → LLM decides → execute → return result to LLM

Level 6 Observable Agent (OpenTelemetry)

Traces + Metrics + Logs — understand what happens inside your agent

# Trace spans for each step
with tracer.start_span("agent_query") as span:
    span.set_attribute("question", q)
# Metrics: request count, latency p99, errors

Core: Trace (request journey) → Span (unit of work) → Metrics (counters, histograms)

Interview Day Cheat Sheet

Last-minute reminders before you walk in

Problem-Solving Framework

Clarify inputs, outputs, edge cases
Think out loud — share your approach
Start with brute force, then optimize
Write code, then trace through an example
Analyze time & space complexity

Pattern Recognition Triggers

"Find pair/complement" → Hash Map / Two Pointers
"Sorted array" → Binary Search / Two Pointers
"Subarray/substring" → Sliding Window
"Matching/nesting" → Stack
"Grid/graph traversal" → DFS / BFS
"Min/max ways" → Dynamic Programming
"Top K / Kth largest" → Heap

Complexity Quick Ref

O(1) — Hash lookup, array index
O(log n) — Binary search
O(n) — Single loop, hash map build
O(n log n) — Sorting (best general)
O(n²) — Nested loops (usually avoidable)
O(2ⁿ) — Recursion without memo

Common Edge Cases

Empty input: [], "", None
Single element: [1], "a"
All same: [5,5,5,5]
Already sorted / reverse sorted
Negative numbers
Integer overflow (Python handles, mention it)

Python Gotchas

// for integer division (not /)
True/False/None are capitalized
list.sort() returns None!
range(n) goes 0 to n-1
Mutable default args are shared
is vs == (identity vs equality)

Communication Tips

Ask "Can I assume..." before starting
Say "I'm considering X because..."
If stuck: "Let me think about a simpler version"
After coding: "Let me trace through this example"
Always state time/space complexity