Topics Covered:
- Arrays & Lists (9 questions) - Reversing, rotation, two-sum, merging, etc.
- Strings (6 questions) - Palindromes, anagrams, compression, permutations
- Linked Lists (6 questions) - Reversal, cycle detection, palindrome check
- Stacks & Queues (5 questions) - Valid parentheses, min stack, monotonic stack
- Hash Tables (4 questions) - Implementation, duplicates, majority element
- Trees (10 questions) - Traversals, validation, LCA, diameter, serialization
- Heaps & Priority Queues (4 questions) - Kth largest, top K frequent, median
- Graphs (7 questions) - BFS/DFS, cycles, topological sort, shortest path
- Tries (1 question) - Complete Trie implementation
- Dynamic Programming (6 questions) - LIS, edit distance, coin change, house robber
- Advanced (3 questions) - LRU Cache, Union Find, Segment Tree
========================================================================
## ARRAYS & LISTS
=========================================================================
# 1. REVERSE AN ARRAY IN PLACE
def reverse_array(arr):
"""Time: O(n), Space: O(1)"""
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arr
# 2. FIND MAXIMUM PRODUCT OF TWO INTEGERS
def max_product_pair(arr):
"""Time: O(n), Space: O(1)"""
if len(arr) < 2:
return None
max1 = max2 = float('-inf')
for num in arr:
if num > max1:
max2 = max1
max1 = num
elif num > max2:
max2 = num
return max1 * max2
# 3. ROTATE ARRAY BY K POSITIONS
def rotate_array(arr, k):
"""Time: O(n), Space: O(1)"""
k = k % len(arr)
arr[:] = arr[-k:] + arr[:-k]
return arr
# Alternative: Use reverse
# def reverse(arr, start, end):
# while start < end:
# arr[start], arr[end] = arr[end], arr[start]
# start += 1
# end -= 1
# reverse(arr, 0, len(arr)-1)
# reverse(arr, 0, k-1)
# reverse(arr, k, len(arr)-1)
# 4. MOVE ALL ZEROS TO END
def move_zeros(arr):
"""Time: O(n), Space: O(1)"""
write_index = 0
for i in range(len(arr)):
if arr[i] != 0:
arr[write_index] = arr[i]
write_index += 1
while write_index < len(arr):
arr[write_index] = 0
write_index += 1
return arr
# 5. LONGEST CONSECUTIVE ELEMENTS SEQUENCE
def longest_consecutive(nums):
"""Time: O(n), Space: O(n)"""
if not nums:
return 0
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set: # Start of sequence
current = num
length = 1
while current + 1 in num_set:
current += 1
length += 1
longest = max(longest, length)
return longest
# 6. CONTAINER WITH MOST WATER
def max_area(height):
"""Time: O(n), Space: O(1)"""
max_area = 0
left, right = 0, len(height) - 1
while left < right:
width = right - left
h = min(height[left], height[right])
area = width * h
max_area = max(max_area, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area
# 7. TWO SUM PROBLEM
def two_sum(nums, 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 []
# 8. MERGE SORTED ARRAYS
def merge_sorted_arrays(arr1, arr2):
"""Time: O(n+m), Space: O(n+m)"""
result = []
i = j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
result.extend(arr1[i:])
result.extend(arr2[j:])
return result
# 9. REMOVE DUPLICATES FROM SORTED ARRAY
def remove_duplicates(nums):
"""Time: O(n), Space: O(1)"""
if not nums:
return 0
write_index = 1
for i in range(1, len(nums)):
if nums[i] != nums[i-1]:
nums[write_index] = nums[i]
write_index += 1
return write_index
## ============================================================================
## STRINGS
## ============================================================================
# 1. REVERSE A STRING
def reverse_string(s):
"""Time: O(n), Space: O(1)"""
return s[::-1]
# 2. CHECK IF PALINDROME
def is_palindrome(s):
"""Time: O(n), Space: O(1)"""
clean = ''.join(c.lower() for c in s if c.isalnum())
return clean == clean[::-1]
# 3. LONGEST SUBSTRING WITHOUT REPEATING CHARACTERS
def length_of_longest_substring(s):
"""Time: O(n), Space: O(min(n, m))"""
char_index = {}
max_len = 0
start = 0
for i, char in enumerate(s):
if char in char_index and char_index[char] >= start:
start = char_index[char] + 1
char_index[char] = i
max_len = max(max_len, i - start + 1)
return max_len
# 4. STRING COMPRESSION
def compress_string(s):
"""Time: O(n), Space: O(n)"""
if not s:
return s
compressed = []
count = 1
for i in range(len(s)):
if i + 1 >= len(s) or s[i] != s[i + 1]:
compressed.append(s[i] + str(count))
count = 1
else:
count += 1
result = ''.join(compressed)
return result if len(result) < len(s) else s
# 5. CHECK IF ANAGRAM
def is_anagram(s1, s2):
"""Time: O(n), Space: O(1)"""
return sorted(s1) == sorted(s2)
# 6. ALL PERMUTATIONS OF STRING
def permutations(s):
"""Time: O(n!), Space: O(n!)"""
if len(s) <= 1:
return [s]
perms = []
for i, char in enumerate(s):
remaining = s[:i] + s[i+1:]
for perm in permutations(remaining):
perms.append(char + perm)
return perms
# 7. FIRST NON-REPEATING CHARACTER
def first_non_repeating(s):
"""Time: O(n), Space: O(n)"""
char_count = {}
for char in s:
char_count[char] = char_count.get(char, 0) + 1
for char in s:
if char_count[char] == 1:
return char
return None
## ============================================================================
## LINKED LISTS
## ============================================================================
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 1. REVERSE A LINKED LIST
def reverse_linked_list(head):
"""Time: O(n), Space: O(1)"""
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
# 2. DETECT CYCLE IN LINKED LIST
def has_cycle(head):
"""Time: O(n), Space: O(1)"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# 3. FIND MIDDLE OF LINKED LIST
def find_middle(head):
"""Time: O(n), Space: O(1)"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 4. MERGE TWO SORTED LINKED LISTS
def merge_sorted_lists(l1, l2):
"""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 if l1 else l2
return dummy.next
# 5. REMOVE NTH NODE FROM END
def remove_nth_node(head, n):
"""Time: O(n), Space: O(1)"""
dummy = ListNode(0)
dummy.next = head
first = second = dummy
for _ in range(n + 1):
first = first.next
while first:
first = first.next
second = second.next
second.next = second.next.next
return dummy.next
# 6. CHECK IF PALINDROME LINKED LIST
def is_palindrome_linked_list(head):
"""Time: O(n), Space: O(1)"""
if not head or not head.next:
return True
# Find middle
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
while slow:
next_temp = slow.next
slow.next = prev
prev = slow
slow = next_temp
# Compare
left, right = head, prev
while right: # right will be shorter
if left.val != right.val:
return False
left = left.next
right = right.next
return True
## ============================================================================
## STACKS & QUEUES
## ============================================================================
class Stack:
def __init__(self):
self.items = []
def push(self, val):
self.items.append(val)
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
class Queue:
def __init__(self):
self.items = []
def enqueue(self, val):
self.items.append(val)
def dequeue(self):
return self.items.pop(0) if self.items else None
def peek(self):
return self.items[0] if self.items else None
def is_empty(self):
return len(self.items) == 0
# 1. VALID PARENTHESES
def is_valid_parentheses(s):
"""Time: O(n), Space: O(n)"""
stack = []
pairs = {'(': ')', '{': '}', '[': ']'}
for char in s:
if char in pairs:
stack.append(char)
else:
if not stack or pairs[stack.pop()] != char:
return False
return len(stack) == 0
# 2. MIN STACK
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.min_stack[-1]
# 3. EVALUATE POSTFIX EXPRESSION
def evaluate_postfix(tokens):
"""Time: O(n), Space: O(n)"""
stack = []
operators = {'+', '-', '*', '/'}
for token in tokens:
if token in operators:
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(int(a / b))
else:
stack.append(int(token))
return stack[0]
# 4. NEXT GREATER ELEMENT
def next_greater_element(nums):
"""Time: O(n), Space: O(n)"""
stack = []
result = {}
for num in reversed(nums):
while stack and stack[-1] <= num:
stack.pop()
result[num] = stack[-1] if stack else -1
stack.append(num)
return [result[num] for num in nums]
# 5. SLIDING WINDOW MAXIMUM
def sliding_window_maximum(nums, k):
"""Time: O(n), Space: O(k)"""
from collections import deque
deq = deque()
result = []
for i, num in enumerate(nums):
if deq and deq[0][1] < i - k + 1:
deq.popleft()
while deq and deq[-1][0] <= num:
deq.pop()
deq.append((num, i))
if i >= k - 1:
result.append(deq[0][0])
return result
## ============================================================================
## HASH TABLES & HASH MAPS
## ============================================================================
# 1. IMPLEMENT HASH MAP
class HashMap:
def __init__(self, capacity=1000):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, value):
idx = self._hash(key)
for i, (k, v) in enumerate(self.buckets[idx]):
if k == key:
self.buckets[idx][i] = (key, value)
return
self.buckets[idx].append((key, value))
def get(self, key):
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key:
return v
return -1
def remove(self, key):
idx = self._hash(key)
self.buckets[idx] = [(k, v) for k, v in self.buckets[idx] if k != key]
# 2. LONGEST SUBSTRING WITH K DISTINCT CHARACTERS
def longest_substring_k_distinct(s, k):
"""Time: O(n), Space: O(k)"""
char_count = {}
max_len = 0
left = 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
# 3. MAJORITY ELEMENT
def majority_element(nums):
"""Time: O(n), Space: O(1)"""
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate
# 4. FIND DUPLICATE ELEMENTS
def find_duplicates(nums):
"""Time: O(n), Space: O(n)"""
seen = set()
duplicates = set()
for num in nums:
if num in seen:
duplicates.add(num)
else:
seen.add(num)
return list(duplicates)
## ============================================================================
## TREES (BINARY & BST)
## ============================================================================
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# 1. LEVEL-ORDER TRAVERSAL (BFS)
def level_order_traversal(root):
"""Time: O(n), Space: O(w) where w is max width"""
from collections import deque
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
# 2. IN-ORDER TRAVERSAL (Left, Root, Right)
def inorder_traversal(root):
"""Time: O(n), Space: O(h)"""
result = []
def dfs(node):
if node:
dfs(node.left)
result.append(node.val)
dfs(node.right)
dfs(root)
return result
# 3. PRE-ORDER TRAVERSAL (Root, Left, Right)
def preorder_traversal(root):
"""Time: O(n), Space: O(h)"""
result = []
def dfs(node):
if node:
result.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return result
# 4. POST-ORDER TRAVERSAL (Left, Right, Root)
def postorder_traversal(root):
"""Time: O(n), Space: O(h)"""
result = []
def dfs(node):
if node:
dfs(node.left)
dfs(node.right)
result.append(node.val)
dfs(root)
return result
# 5. VALIDATE BINARY SEARCH TREE
def is_valid_bst(root):
"""Time: O(n), Space: O(h)"""
def validate(node, low=float('-inf'), high=float('inf')):
if not node:
return True
if node.val <= low or node.val >= high:
return False
return (validate(node.left, low, node.val) and
validate(node.right, node.val, high))
return validate(root)
# 6. LOWEST COMMON ANCESTOR
def lowest_common_ancestor(root, p, q):
"""Time: O(n), Space: O(h)"""
if not root:
return None
if root.val == p.val or root.val == q.val:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left if left else right
# 7. INVERT BINARY TREE
def invert_tree(root):
"""Time: O(n), Space: O(h)"""
if not root:
return None
root.left, root.right = root.right, root.left
invert_tree(root.left)
invert_tree(root.right)
return root
# 8. DIAMETER OF BINARY TREE
def diameter_of_tree(root):
"""Time: O(n), Space: O(h)"""
diameter = [0]
def height(node):
if not node:
return 0
left_height = height(node.left)
right_height = height(node.right)
diameter[0] = max(diameter[0], left_height + right_height)
return 1 + max(left_height, right_height)
height(root)
return diameter[0]
# 9. BALANCED BINARY TREE
def is_balanced(root):
"""Time: O(n), Space: O(h)"""
def check(node):
if not node:
return True, 0
left_balanced, left_height = check(node.left)
if not left_balanced:
return False, 0
right_balanced, right_height = check(node.right)
if not right_balanced:
return False, 0
balanced = abs(left_height - right_height) <= 1
height = 1 + max(left_height, right_height)
return balanced, height
return check(root)[0]
# 10. SERIALIZE AND DESERIALIZE
def serialize(root):
"""Time: O(n), Space: O(n)"""
if not root:
return "None"
result = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
result.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
result.append("None")
return ",".join(result)
def deserialize(data):
"""Time: O(n), Space: O(n)"""
if data == "None":
return None
values = data.split(",")
root = TreeNode(int(values[0]))
queue = [root]
i = 1
while queue:
node = queue.pop(0)
if values[i] != "None":
node.left = TreeNode(int(values[i]))
queue.append(node.left)
i += 1
if values[i] != "None":
node.right = TreeNode(int(values[i]))
queue.append(node.right)
i += 1
return root
## ============================================================================
## HEAPS & PRIORITY QUEUES
## ============================================================================
import heapq
# 1. KTH LARGEST ELEMENT
def find_kth_largest(nums, k):
"""Time: O(n log k), Space: O(k)"""
heap = []
for num in nums:
if len(heap) < k:
heapq.heappush(heap, num)
elif num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]
# 2. TOP K FREQUENT ELEMENTS
def top_k_frequent(nums, k):
"""Time: O(n log k), Space: O(n)"""
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
heap = []
for num, freq in count.items():
if len(heap) < k:
heapq.heappush(heap, (freq, num))
elif freq > heap[0][0]:
heapq.heapreplace(heap, (freq, num))
return [num for freq, num in heap]
# 3. FIND MEDIAN OF DATA STREAM
class MedianFinder:
def __init__(self):
self.small = [] # max heap (negate values)
self.large = [] # min heap
def addNum(self, num):
if not self.small or num <= -self.small[0]:
heapq.heappush(self.small, -num)
else:
heapq.heappush(self.large, num)
if len(self.small) > len(self.large) + 1:
heapq.heappush(self.large, -heapq.heappop(self.small))
elif len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def findMedian(self):
if len(self.small) > len(self.large):
return float(-self.small[0])
return (-self.small[0] + self.large[0]) / 2
# 4. MERGE K SORTED LISTS
def merge_k_lists(lists):
"""Time: O(n log k), Space: O(k)"""
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst.val, i, lst))
dummy = ListNode(0)
current = dummy
while heap:
val, i, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
## ============================================================================
## GRAPHS
## ============================================================================
# 1. BFS TRAVERSAL
def bfs(graph, start):
"""Time: O(V+E), Space: O(V)"""
from collections import deque
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# 2. DFS TRAVERSAL
def dfs(graph, start):
"""Time: O(V+E), Space: O(V)"""
visited = set()
result = []
def dfs_helper(node):
visited.add(node)
result.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs_helper(neighbor)
dfs_helper(start)
return result
# 3. DETECT CYCLE IN UNDIRECTED GRAPH
def has_cycle_undirected(graph, n):
"""Time: O(V+E), Space: O(V)"""
visited = [False] * n
def dfs(node, parent):
visited[node] = True
for neighbor in graph.get(node, []):
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True
return False
for i in range(n):
if not visited[i]:
if dfs(i, -1):
return True
return False
# 4. TOPOLOGICAL SORT (DFS)
def topological_sort(graph, n):
"""Time: O(V+E), Space: O(V)"""
visited = [False] * n
stack = []
def dfs(node):
visited[node] = True
for neighbor in graph.get(node, []):
if not visited[neighbor]:
dfs(neighbor)
stack.append(node)
for i in range(n):
if not visited[i]:
dfs(i)
return stack[::-1]
# 5. SHORTEST PATH - DIJKSTRA
def dijkstra(graph, start, n):
"""Time: O((V+E) log V), Space: O(V)"""
import heapq
distances = [float('inf')] * n
distances[start] = 0
heap = [(0, start)]
while heap:
curr_dist, node = heapq.heappop(heap)
if curr_dist > distances[node]:
continue
for neighbor, weight in graph.get(node, []):
distance = curr_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
# 6. NUMBER OF CONNECTED COMPONENTS
def count_connected_components(n, edges):
"""Time: O(V+E), Space: O(V)"""
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
count = 0
for i in range(n):
if i not in visited:
dfs(i)
count += 1
return count
# 7. NUMBER OF ISLANDS
def num_islands(grid):
"""Time: O(m*n), Space: O(m*n)"""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if (r, c) in visited or grid[r][c] == '0':
return
visited.add((r, c))
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1' and (i, j) not in visited:
dfs(i, j)
count += 1
return count
## ============================================================================
## TRIES
## ============================================================================
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""Time: O(m) where m is length of word"""
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
"""Time: O(m)"""
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def starts_with(self, prefix):
"""Time: O(m)"""
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
## ============================================================================
## DYNAMIC PROGRAMMING
## ============================================================================
# 1. LONGEST INCREASING SUBSEQUENCE
def longest_increasing_subsequence(nums):
"""Time: O(n^2), Space: O(n)"""
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 2. EDIT DISTANCE (LEVENSHTEIN)
def edit_distance(word1, word2):
"""Time: O(m*n), Space: O(m*n)"""
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]
# 3. COIN CHANGE
def coin_change(coins, amount):
"""Time: O(n*amount), Space: O(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
# 4. HOUSE ROBBER
def rob(nums):
"""Time: O(n), Space: O(1)"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2 = 0
prev1 = nums[0]
for i in range(1, len(nums)):
current = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = current
return prev1
# 5. CLIMBING STAIRS
def climb_stairs(n):
"""Time: O(n), Space: O(1)"""
if n <= 1:
return 1
prev2, prev1 = 1, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
# 6. 0/1 KNAPSACK
def knapsack(weights, values, capacity):
"""Time: O(n*capacity), Space: O(capacity)"""
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):
if weights[i-1] <= w:
dp[i][w] = max(
values[i-1] + dp[i-1][w - weights[i-1]],
dp[i-1][w]
)
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
## ============================================================================
## ADVANCED DATA STRUCTURES
## ============================================================================
# 1. LRU CACHE
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# 2. UNION FIND (DISJOINT SET)
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
# 3. SEGMENT TREE (for range queries)
class SegmentTree:
def __init__(self, nums):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self.build(nums, 0, 0, self.n - 1)
def build(self, nums, node, start, end):
if start == end:
self.tree[node] = nums[start]
else:
mid = (start + end) // 2
self.build(nums, 2*node+1, start, mid)
self.build(nums, 2*node+2, mid+1, end)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def query(self, node, start, end, left, right):
if right < start or end < left:
return 0
if left <= start and end <= right:
return self.tree[node]
mid = (start + end) // 2
return (self.query(2*node+1, start, mid, left, right) +
self.query(2*node+2, mid+1, end, left, right))
def range_sum(self, left, right):
return self.query(0, 0, self.n-1, left, right)
## ============================================================================
## TEST EXAMPLES
## ============================================================================
if __name__ == "__main__":
# Arrays
print("=== Arrays ===")
print(reverse_array([1, 2, 3, 4, 5])) # [5, 4, 3, 2, 1]
print(max_product_pair([1, 5, 2, 8, 3])) # 40
# Strings
print("\n=== Strings ===")
print(is_palindrome("A man, a plan, a canal: Panama")) # True
print(length_of_longest_substring("abcabcbb")) # 3
# Linked Lists
print("\n=== Linked Lists ===")
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print([node.val for node in head] if hasattr(head, 'val') else "Created")
# Stacks & Queues
print("\n=== Stacks & Queues ===")
print(is_valid_parentheses("()[]{}")) # True
print(next_greater_element([1, 3, 2, 4])) # [3, 4, 4, -1]
# Hash Maps
print("\n=== Hash Maps ===")
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
print(majority_element([3, 2, 3])) # 3
# Trees
print("\n=== Trees ===")
# Create sample tree
root = TreeNode(1, TreeNode(2), TreeNode(3))
print(inorder_traversal(root)) # [2, 1, 3]
# Graphs
print("\n=== Graphs ===")
graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}
print(bfs(graph, 0)) # [0, 1, 2, 3]
# DP
print("\n=== Dynamic Programming ===")
print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18])) # 4
print(coin_change([1, 2, 5], 5)) # 1
print("\n✓ All examples executed!")