Introduction
Data structures are the foundation of coding interviews. Understanding how to use and implement them is essential for passing technical interviews. This guide covers the data structures you’re most likely to encounter and how to use them effectively.
Arrays and Strings
Arrays
Key Operations
| Operation | Time Complexity |
|---|---|
| Access | O(1) |
| Search | O(n) |
| Insert | O(n) |
| Delete | O(n) |
Common Patterns
Two Pointers
def reverse_array(arr, left, right):
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current = arr[left] + arr[right]
if current == target:
return [left, right]
elif current < target:
left += 1
else:
right -= 1
return []
Sliding Window
def max_sum_subarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum = window_sum - arr[i - k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sum
Prefix Sum
def range_sum(arr, left, right):
prefix = [0]
for num in arr:
prefix.append(prefix[-1] + num)
return prefix[right + 1] - prefix[left]
Strings
Common Operations
def count_characters(s):
count = {}
for char in s:
count[char] = count.get(char, 0) + 1
return count
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
Linked Lists
Types
- Singly: One direction
- Doubly: Both directions
- Circular: Last points to first
Implementation
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def append(self, val):
if not self.head:
self.head = ListNode(val)
return
current = self.head
while current.next:
current = current.next
current.next = ListNode(val)
def reverse(self):
prev = None
current = self.head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
self.head = prev
Common Patterns
Fast and Slow Pointers
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Merge Two Sorted Lists
def merge_sorted(l1, l2):
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
Stacks and Queues
Stack
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop() if self.items else None
def peek(self):
return self.items[-1] if self.items else None
def is_empty(self):
return len(self.items) == 0
Applications: Expression evaluation, DFS, undo mechanisms
Queue
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
return self.items.popleft() if self.items else None
Applications: BFS, level-order traversal, task scheduling
Hash Tables
Implementation
class HashTable:
def __init__(self, size=100):
self.size = size
self.table = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def set(self, key, value):
index = self._hash(key)
bucket = self.table[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
index = self._hash(key)
for k, v in self.table[index]:
if k == key:
return v
return None
Interview Patterns
Anagram Detection
def is_anagram(s1, s2):
return sorted(s1) == sorted(s2)
# O(n) using hash table
def is_anagram_hash(s1, s2):
if len(s1) != len(s2):
return False
count = {}
for c in s1:
count[c] = count.get(c, 0) + 1
for c in s2:
count[c] = count.get(c, 0) - 1
if count[c] < 0:
return False
return True
Trees
Binary Tree
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Traversals
Inorder (Left, Root, Right)
def inorder(root, result=[]):
if root:
inorder(root.left, result)
result.append(root.val)
inorder(root.right, result)
return result
Preorder (Root, Left, Right)
def preorder(root, result=[]):
if root:
result.append(root.val)
preorder(root.left, result)
preorder(root.right, result)
return result
Level Order
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
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
BST Operations
class BST:
def __init__(self):
self.root = None
def insert(self, val):
if not self.root:
self.root = TreeNode(val)
return
current = self.root
while True:
if val < current.val:
if not current.left:
current.left = TreeNode(val)
return
current = current.left
else:
if not current.right:
current.right = TreeNode(val)
return
current = current.right
def search(self, val):
current = self.root
while current:
if val == current.val:
return current
elif val < current.val:
current = current.left
else:
current = current.right
return None
Heaps
Min Heap
import heapq
class MinHeap:
def __init__(self):
self.heap = []
def push(self, val):
heapq.heappush(self.heap, val)
def pop(self):
return heapq.heappop(self.heap)
def peek(self):
return self.heap[0]
Applications
- Finding k largest/smallest elements
- Median of data stream
- Priority queues
- Top K problems
Graphs
Representations
# Adjacency List
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
# Adjacency Matrix
graph_matrix = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
]
BFS and DFS
from collections import deque
def bfs(graph, start):
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
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph[start]:
if neighbor not in visited:
result.extend(dfs(graph, neighbor, visited))
return result
Conclusion
Mastering these data structures and their common patterns is essential for coding interviews. Practice implementing each from scratch, understand time and space complexities, and learn the patterns for solving common problems. With this foundation, you’ll be well-prepared for technical interviews.
Comments