Data Structures & Algorithms Review for Coding Interviews
Data Structures & Algorithms (DSA) form the foundation of technical interviews — understanding when and how to use each data structure is the difference between a working solution and an optimal one.
What You’ll Learn
By the end of this tutorial, you’ll have reviewed the essential data structures (arrays, linked lists, hash tables, trees, graphs) and algorithms (sorting, searching, BFS/DFS, dynamic programming) with code examples, time/space complexity, and common interview problem patterns.
Why DSA Review Matters
Most coding interviews test 2-3 DSA problems. Companies like Google, Meta, and Amazon explicitly assess algorithmic thinking because it correlates with strong engineering. Mastering DSA patterns — not memorizing solutions — unlocks any coding interview. At DodaTech, our Doda Browser rendering engine uses tree structures and graph algorithms for DOM layout.
DSA Learning Path
flowchart LR
A[Interview Strategies] --> B[DSA Review]
B --> C{You Are Here}
C --> D[System Design]
B --> E[Practice Problems]
style C fill:#f90,color:#fff
Essential Data Structures
Arrays and Strings
The most fundamental data structure — contiguous memory, index-based access.
Time complexity: Access O(1), Search O(n), Insert/Delete O(n)
Key patterns:
- Two pointers (left/right moving toward center)
- Sliding window (contiguous subarray problems)
- Prefix sums (range sum queries)
# Two Sum II — Two-pointer pattern
def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
"""Find two numbers that sum to target in sorted array."""
left, right = 0, len(numbers) - 1
while left < right:
current = numbers[left] + numbers[right]
if current == target:
return [left + 1, right + 1]
elif current < target:
left += 1
else:
right -= 1
return []
# Example
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]Hash Tables (Hash Maps / Dictionaries)
Key-value storage with O(1) average access.
Time complexity: Insert O(1), Lookup O(1), Delete O(1)
Key patterns:
- Frequency counting (character/word counts)
- Caching/memoization (store computed results)
- Lookup table (check existence fast)
# Contains Duplicate — Hash set pattern
def contains_duplicate(nums: list[int]) -> bool:
"""Check if any value appears more than once."""
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
# Example
print(contains_duplicate([1, 2, 3, 1])) # True
print(contains_duplicate([1, 2, 3, 4])) # FalseLinked Lists
Sequential nodes where each node points to the next (singly) or both directions (doubly).
Time complexity: Access O(n), Insert at head O(1), Delete with reference O(1)
Key patterns:
- Fast and slow pointers (cycle detection, find middle)
- Reversal (reverse in place)
- Merge two sorted lists
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode) -> bool:
"""Detect cycle using Floyd's algorithm (fast/slow pointers)."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def reverse_list(head: ListNode) -> ListNode:
"""Reverse a linked list in place."""
prev, current = None, head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prevStacks and Queues
- Stack: LIFO (Last In, First Out) — undo, parsing, DFS
- Queue: FIFO (First In, First Out) — BFS, task scheduling
Time complexity: All operations O(1)
# Valid Parentheses — Stack pattern
def is_valid(s: str) -> bool:
"""Check if brackets are properly matched."""
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in pairs.values():
stack.append(char)
elif char in pairs:
if not stack or stack.pop() != pairs[char]:
return False
else:
return False # Invalid character
return len(stack) == 0
# Example
print(is_valid("()[]{}")) # True
print(is_valid("([)]")) # FalseTrees (Binary Trees, BST, Heaps)
Hierarchical data structures with parent-child relationships.
Time complexity (balanced BST): Search O(log n), Insert O(log n), Traverse O(n)
Traversals:
- In-order (left, root, right) — sorted order for BST
- Pre-order (root, left, right) — copy tree
- Post-order (left, right, root) — delete tree
- Level-order (BFS) — breadth-first
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(root: TreeNode) -> list[int]:
"""In-order traversal: left, root, right."""
result = []
def traverse(node):
if node:
traverse(node.left)
result.append(node.val)
traverse(node.right)
traverse(root)
return result
def max_depth(root: TreeNode) -> int:
"""Find maximum depth of a binary tree."""
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))Heaps (Priority Queues) — efficient min/max extraction:
import heapq
# Min-heap by default in Python
heap = [3, 1, 4, 1, 5, 9]
heapq.heapify(heap)
print(heapq.heappop(heap)) # 1 (smallest)
print(heapq.heappop(heap)) # 1
# Max-heap: store negative values
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -4)
print(-heapq.heappop(max_heap)) # 4 (largest)Graphs
Nodes connected by edges. Can be directed/undirected, weighted/unweighted.
Time complexity: BFS/DFS O(V + E)
Key patterns:
- DFS (stack/recursion) — path finding, connected components
- BFS (queue) — shortest path in unweighted graphs
- Topological sort — dependency resolution
from collections import deque
def bfs(graph: dict, start: str) -> list[str]:
"""Breadth-first search traversal."""
visited = set()
queue = deque([start])
result = []
while queue:
node = queue.popleft()
if node not in visited:
visited.add(node)
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
return result
# Example graph
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']Essential Algorithms
Binary Search
Search a sorted array in O(log n) time by repeatedly dividing the search space in half.
def binary_search(nums: list[int], target: int) -> int:
"""Return index of target in sorted nums, or -1."""
left, right = 0, 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
print(binary_search([1, 3, 5, 7, 9], 5)) # 2
print(binary_search([1, 3, 5, 7, 9], 2)) # -1Sorting (Quick Sort)
Divide and conquer — pick a pivot, partition around it, recurse.
def quick_sort(nums: list[int]) -> list[int]:
"""Sort array using quicksort."""
if len(nums) <= 1:
return nums
pivot = nums[len(nums) // 2]
left = [x for x in nums if x < pivot]
middle = [x for x in nums if x == pivot]
right = [x for x in nums if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# [1, 1, 2, 3, 6, 8, 10]Dynamic Programming
Solve complex problems by breaking them into subproblems and caching results.
When to use DP: Optimal substructure + overlapping subproblems.
Common patterns:
- Fibonacci (1D DP)
- Knapsack (2D DP)
- Longest Common Subsequence (2D DP)
# Fibonacci — Dynamic Programming (bottom-up)
def fibonacci(n: int) -> int:
"""Return nth Fibonacci number using DP."""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Climbing Stairs (LeetCode 70)
def climb_stairs(n: int) -> int:
"""Number of ways to climb n stairs (1 or 2 steps)."""
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b
print(fibonacci(10)) # 55
print(climb_stairs(5)) # 8Pattern Recognition Guide
| Problem Pattern | Data Structure | Approach |
|---|---|---|
| Find pair in array | Hash map | Store complement while iterating |
| Longest substring without repeating | Hash set + two pointers | Sliding window |
| Kth largest element | Heap | Min-heap of size k |
| Shortest path in grid | Queue | BFS |
| Detect cycle in linked list | Two pointers | Fast and slow |
| Tree is balanced | Recursion | Check height difference |
| Graph connected components | Stack/Queue | DFS/BFS from each node |
| Subset sum / combination | Backtracking | Recursion with pruning |
| Longest increasing subsequence | DP array | Compare with all previous |
| Merge intervals | Sort + iterate | Sort by start time |
Big O Complexity Cheatsheet
Operation | Array | Linked List | Hash Table | BST (balanced)
------------------|-------|-------------|------------|---------------
Access | O(1) | O(n) | N/A | O(log n)
Search | O(n) | O(n) | O(1) avg | O(log n)
Insert (beginning)| O(n) | O(1) | O(1) | O(log n)
Insert (end) | O(1)* | O(n) | O(1) | O(log n)
Delete | O(n) | O(n) | O(1) | O(log n)*Amortized — may need resizing.
Common Interview Mistakes
1. Not Identifying the Pattern
Most interview problems follow known patterns. Practice recognizing: “This is a sliding window problem” or “This needs two pointers.”
2. Brute-Forcing Without Considering Optimization
Start with brute force, but immediately discuss optimization. The interviewer wants to see your thought process, not just a correct solution.
3. Ignoring Constraints
Input size determines acceptable complexity: n ≤ 100 → O(n²) is fine. n ≤ 10⁵ → needs O(n log n) or better.
4. Forgetting to Handle Edge Cases
Empty arrays, null values, single elements — always check these before submitting.
5. Writing Messy Recursion Without Base Cases
Always define the base case first, then the recursive step. Test with the smallest possible input.
6. Confusing BFS and DFS
BFS (queue) finds shortest path. DFS (stack/recursion) explores deep paths. Choose based on the problem.
7. Not Practicing on Paper/Whiteboard
Coding on a whiteboard is harder than coding on an IDE. Practice writing code without autocomplete or syntax highlighting.
Practice Questions
1. What is the time complexity of looking up an element in a hash table?
Average O(1), worst-case O(n) if many hash collisions occur. Modern hash tables handle collisions efficiently with chaining or open addressing.
2. When would you use BFS over DFS?
BFS finds the shortest path in unweighted graphs. Use it when the target is likely close to the start. DFS uses less memory for deep graphs.
3. What’s the difference between a stack and a queue?
Stack is LIFO (Last In, First Out) — undo operations, expression parsing. Queue is FIFO (First In, First Out) — BFS, print spooling.
4. What makes a problem solvable with dynamic programming?
Optimal substructure (optimal solution contains optimal sub-solutions) and overlapping subproblems (same subproblems recur).
5. Challenge: Implement a function to check if a binary tree is a valid BST.
Use in-order traversal — a valid BST produces a strictly increasing sequence. Or pass min/max bounds down recursively.
Mini Project: DSA Problem Tracker
# dsa_tracker.py
# Track your DSA practice progress
import json
from datetime import datetime
class DSATracker:
def __init__(self):
self.problems = []
def add_problem(self, name, category, difficulty, solved=True):
"""Record a solved problem."""
self.problems.append({
"name": name,
"category": category,
"difficulty": difficulty,
"solved": solved,
"date": datetime.now().isoformat()
})
def summary(self):
"""Show practice statistics."""
categories = {}
for p in self.problems:
cat = p["category"]
if cat not in categories:
categories[cat] = {"easy": 0, "medium": 0, "hard": 0}
categories[cat][p["difficulty"]] += 1
print("=== DSA Practice Summary ===")
print(f"Total problems: {len(self.problems)}")
print()
for cat, counts in sorted(categories.items()):
total = sum(counts.values())
print(f"{cat}: {total} total ({counts['easy']}E / {counts['medium']}M / {counts['hard']}H)")
# Example usage
tracker = DSATracker()
tracker.add_problem("Two Sum", "Arrays", "easy")
tracker.add_problem("Binary Tree Level Order", "Trees", "medium")
tracker.add_problem("Edit Distance", "DP", "hard")
tracker.summary()FAQ
Try It Yourself
Solve these three problems using the patterns from this review:
- Arrays: “Best Time to Buy and Sell Stock” (LeetCode 121) — track min price while iterating
- Trees: “Invert Binary Tree” (LeetCode 226) — swap left and right recursively
- DP: “House Robber” (LeetCode 198) — max of rob current or skip current
These represent the three most common interview categories. DodaTech’s engineering interviews for Doda Browser and Durga Antivirus Pro teams assess these exact patterns.
What’s Next
What’s Next
Congratulations on completing this DSA Review tutorial! Here’s where to go from here:
- Practice daily — Consistency is more important than long study sessions
- Build a project — Apply what you learned by building something real
- Explore related topics — Check out other tutorials in the same category
- Join the community — Discuss with other learners and share your progress
Remember: every expert was once a beginner. Keep coding!
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro