Essential Data Structures
Stack
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
raise IndexError('Stack is empty')
def peek(self):
if not self.is_empty():
return self.items[-1]
raise IndexError('Stack is empty')
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop()) # 3
print(stack.peek()) # 2
Queue
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.is_empty():
return self.items.popleft()
raise IndexError('Queue is empty')
def peek(self):
if not self.is_empty():
return self.items[0]
raise IndexError('Queue is empty')
def is_empty(self):
return len(self.items) == 0
# Usage
queue = Queue()
queue.enqueue('a')
queue.enqueue('b')
print(queue.dequeue()) # 'a'
Linked List
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def add_first(self, val):
self.head = ListNode(val, self.head)
def add_last(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 remove(self, val):
if not self.head:
return
if self.head.val == val:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.val == val:
current.next = current.next.next
return
current = current.next
def to_list(self):
result = []
current = self.head
while current:
result.append(current.val)
current = current.next
return result
Hash Map
# Python dict is a hash map
class HashMap:
def __init__(self):
self.size = 10
self.buckets = [[] for _ in range(self.size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
index = self._hash(key)
bucket = self.buckets[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.buckets[index]:
if k == key:
return v
raise KeyError(key)
Algorithm Patterns
Two Pointers
def two_sum(nums, target):
"""Find two numbers that add to target."""
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
def is_palindrome(s):
"""Check if string is palindrome."""
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
Sliding Window
def max_subarray_sum(nums, k):
"""Maximum sum of k consecutive elements."""
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
def longest_substring(s, k):
"""Longest substring with at most k distinct characters."""
char_count = {}
left = 0
max_len = 0
for right in range(len(s)):
char_count[s[right]] = char_count.get(s[right], 0) + 1
while len(char_count) > k:
char_count[s[left]] -= 1
if char_count[s[left]] == 0:
del char_count[s[left]]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
Binary Search
def binary_search(nums, target):
"""Standard binary search."""
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
def search_rotated(nums, target):
"""Search in rotated sorted array."""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
DFS/BFS
# DFS (using stack)
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return visited
# BFS (using queue)
def bfs(graph, start):
from collections import deque
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
Dynamic Programming
def fibonacci(n, memo={}):
"""Fibonacci with memoization."""
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n-1) + fibonacci(n-2)
return memo[n]
def knapsack(weights, values, capacity):
"""0/1 Knapsack problem."""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i-1][w]
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1])
return dp[n][capacity]