Data Structures and Algorithms for Coding Interviews
Master essential data structures and algorithms for technical interviews at FAANG companies with patterns, examples, and practice problems.
Data Structures and Algorithms for Coding Interviews
Interview Preparation Strategy
Study Plan (8-12 Weeks)
Week 1-2: Arrays & Strings
- Two pointers
- Sliding window
- String manipulation
Week 3-4: Linked Lists & Stacks/Queues
- Fast & slow pointers
- Reversal
- Stack applications
Week 5-6: Trees & Graphs
- DFS & BFS
- Binary search trees
- Graph traversal
Week 7-8: Dynamic Programming
- 1D DP
- 2D DP
- Common patterns
Week 9-10: Advanced Topics
- Heaps
- Tries
- Union Find
Week 11-12: Practice & Mock Interviews
- Mixed problems
- Time management
- Communication
Essential Data Structures
1. Arrays
Time Complexity:
Access: O(1)
Search: O(n)
Insert: O(n)
Delete: O(n)
Common Patterns:
Two Pointers:
def two_sum_sorted(nums, target):
"""
Find two numbers that sum to target in sorted array
Time: O(n), Space: O(1)
"""
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return []
# Example: [1, 2, 3, 4, 6], target = 6
# Output: [1, 3] (2 + 4 = 6)
Sliding Window:
def max_sum_subarray(nums, k):
"""
Find maximum sum of subarray of size k
Time: O(n), Space: O(1)
"""
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum = window_sum - nums[i-k] + nums[i]
max_sum = max(max_sum, window_sum)
return max_sum
# Example: [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4
# Output: 39 (10 + 23 + 3 + 1)
Kadane's Algorithm (Maximum Subarray):
def max_subarray(nums):
"""
Find maximum sum of contiguous subarray
Time: O(n), Space: O(1)
"""
max_sum = current_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
# Example: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Output: 6 ([4, -1, 2, 1])
2. Linked Lists
Node Structure:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Common Patterns:
Fast & Slow Pointers (Cycle Detection):
def has_cycle(head):
"""
Detect cycle in linked list
Time: O(n), Space: O(1)
"""
if not head:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Reverse Linked List:
def reverse_list(head):
"""
Reverse a linked list
Time: O(n), Space: O(1)
"""
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
# Example: 1 -> 2 -> 3 -> 4 -> 5
# Output: 5 -> 4 -> 3 -> 2 -> 1
Merge Two Sorted Lists:
def merge_two_lists(l1, l2):
"""
Merge two sorted linked lists
Time: O(n+m), Space: O(1)
"""
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next
3. Trees
Node Structure:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Tree Traversals:
Inorder (Left, Root, Right):
def inorder_traversal(root):
"""
Inorder traversal (iterative)
Time: O(n), Space: O(h)
"""
result = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
Level Order Traversal (BFS):
from collections import deque
def level_order(root):
"""
Level order traversal
Time: O(n), Space: O(w) where w is max width
"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
Binary Search Tree Operations:
def search_bst(root, val):
"""
Search in BST
Time: O(h), Space: O(1)
"""
while root and root.val != val:
root = root.left if val < root.val else root.right
return root
def insert_bst(root, val):
"""
Insert into BST
Time: O(h), Space: O(1)
"""
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst(root.left, val)
else:
root.right = insert_bst(root.right, val)
return root
4. Graphs
Representations:
# Adjacency List
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 4],
3: [1],
4: [1, 2]
}
# Adjacency Matrix
graph = [
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 1],
[1, 0, 0, 0, 1],
[0, 1, 0, 0, 0],
[0, 1, 1, 0, 0]
]
DFS (Depth-First Search):
def dfs(graph, start, visited=None):
"""
DFS traversal
Time: O(V+E), Space: O(V)
"""
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
BFS (Breadth-First Search):
from collections import deque
def bfs(graph, start):
"""
BFS traversal
Time: O(V+E), Space: O(V)
"""
visited = set([start])
queue = deque([start])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
Dijkstra's Algorithm (Shortest Path):
import heapq
def dijkstra(graph, start):
"""
Find shortest paths from start to all nodes
Time: O((V+E)logV), Space: O(V)
"""
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_dist, current_node = heapq.heappop(pq)
if current_dist > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
5. Hash Tables
Common Operations:
# Python dict is a hash table
hash_map = {}
# Insert: O(1)
hash_map['key'] = 'value'
# Search: O(1)
value = hash_map.get('key')
# Delete: O(1)
del hash_map['key']
# Check existence: O(1)
if 'key' in hash_map:
pass
Common Patterns:
Two Sum:
def two_sum(nums, target):
"""
Find indices of two numbers that sum to target
Time: O(n), Space: O(n)
"""
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
Group Anagrams:
from collections import defaultdict
def group_anagrams(strs):
"""
Group anagrams together
Time: O(n*k*logk), Space: O(n*k)
"""
anagrams = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
anagrams[key].append(s)
return list(anagrams.values())
# Example: ["eat","tea","tan","ate","nat","bat"]
# Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
6. Heaps (Priority Queue)
Min Heap Operations:
import heapq
# Create heap
heap = []
# Insert: O(log n)
heapq.heappush(heap, 5)
# Get min: O(1)
min_val = heap[0]
# Remove min: O(log n)
min_val = heapq.heappop(heap)
# Heapify list: O(n)
nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)
K Largest Elements:
def k_largest(nums, k):
"""
Find k largest elements
Time: O(n*logk), Space: O(k)
"""
return heapq.nlargest(k, nums)
# Or using min heap
def k_largest_heap(nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
return heap
Essential Algorithms
1. Binary Search
Basic Template:
def binary_search(nums, target):
"""
Binary search in sorted array
Time: O(log n), Space: O(1)
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Find First/Last Occurrence:
def find_first(nums, target):
"""Find first occurrence of target"""
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
result = mid
right = mid - 1 # Continue searching left
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
2. Sorting Algorithms
Quick Sort:
def quick_sort(arr):
"""
Quick sort
Time: O(n log n) average, O(n²) worst
Space: O(log n)
"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
Merge Sort:
def merge_sort(arr):
"""
Merge sort
Time: O(n log n), Space: O(n)
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
3. Dynamic Programming
Common Patterns:
Fibonacci (1D DP):
def fibonacci(n):
"""
Calculate nth Fibonacci number
Time: O(n), Space: O(1)
"""
if n <= 1:
return n
prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
Longest Common Subsequence (2D DP):
def lcs(text1, text2):
"""
Find length of longest common subsequence
Time: O(m*n), Space: O(m*n)
"""
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
Coin Change (Unbounded Knapsack):
def coin_change(coins, amount):
"""
Find minimum coins needed for amount
Time: O(amount * len(coins)), Space: O(amount)
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Interview Tips
1. Problem-Solving Framework
UMPIRE Method:
- Understand: Clarify the problem
- Match: Identify pattern
- Plan: Design solution
- Implement: Write code
- Review: Test and optimize
- Evaluate: Analyze complexity
2. Communication
✅ Do:
- Think out loud
- Ask clarifying questions
- Explain your approach
- Discuss trade-offs
- Test your code
❌ Don't:
- Jump into coding
- Stay silent
- Ignore edge cases
- Give up easily
- Argue with interviewer
3. Time Management
45-minute interview:
- 5 min: Understand problem
- 5 min: Plan approach
- 25 min: Implement solution
- 5 min: Test and optimize
- 5 min: Questions
4. Common Mistakes
❌ Not asking questions
❌ Ignoring edge cases
❌ Poor variable names
❌ Not testing code
❌ Premature optimization
❌ Not explaining thought process
Practice Resources
Online Platforms
- LeetCode: 2000+ problems
- HackerRank: Structured learning
- CodeSignal: Interview practice
- Pramp: Mock interviews
Problem Sets
- Blind 75: Essential problems
- Grind 75: Week-by-week plan
- NeetCode 150: Categorized problems
Books
- "Cracking the Coding Interview"
- "Elements of Programming Interviews"
- "Algorithm Design Manual"
Conclusion
Success in coding interviews requires consistent practice and pattern recognition. Focus on understanding core concepts rather than memorizing solutions.
Key Takeaways:
- Master fundamental data structures
- Learn common patterns
- Practice regularly
- Communicate clearly
- Manage time effectively
Next Steps:
- Start with easy problems
- Progress to medium difficulty
- Focus on weak areas
- Do mock interviews
- Review and learn from mistakes
Good luck with your interviews! 🚀