Coding Interview Cheat Sheet

def find_132_pattern(nums):
    stack = []
    third = float('-inf')
    for n in reversed(nums):
        if n < third:
            return True
        while stack and stack[-1] < n:
            third = stack.pop()
        stack.append(n)
    return False

Trees & BST

Find Closest Value In BST EASY

class Solution:
    def find_closest(self, root, target):
        closest = root.value; node = root
        while node:
            if abs(target - node.value) < abs(target - closest):
                closest = node.value
            node = node.left if target < node.value else node.right
        return closest

Evaluate Expression Tree EASY

Leaves are numbers (≥0); internal nodes are operators (−1 add, −2 subtract, −3 divide, −4 multiply).

class Solution:
    def evaluate_expression_tree(self, node):
        if node.value >= 0: return node.value
        left = self.evaluate_expression_tree(node.left)
        right = self.evaluate_expression_tree(node.right)
        if node.value == -1: return left + right
        if node.value == -2: return left - right
        if node.value == -3: return int(left / right)
        return left * right

Maximum Depth of Binary Tree EASY

def max_depth_trees(root):
    if not root:
        return 0
    return 1 + max(max_depth_trees(root.left), max_depth_trees(root.right))

Minimum Depth of Binary Tree EASY

def min_depth(root):
    if not root:
        return 0
    if not root.left:
        return 1 + min_depth(root.right)
    if not root.right:
        return 1 + min_depth(root.left)
    return 1 + min(min_depth(root.left), min_depth(root.right))

Count Nodes in a Binary Tree EASY

def count_nodes_trees(root):
    if not root:
        return 0
    return 1 + count_nodes_trees(root.left) + count_nodes_trees(root.right)

Sum of All Nodes EASY

def sum_tree(root):
    if not root:
        return 0
    return root.val + sum_tree(root.left) + sum_tree(root.right)

Invert a Binary Tree EASY

def invert_tree_trees(root):
    if not root:
        return None
    root.left, root.right = invert_tree_trees(root.right), invert_tree_trees(root.left)
    return root

Same Tree EASY

def is_same_tree_trees(p, q):
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return is_same_tree_trees(p.left, q.left) and is_same_tree_trees(p.right, q.right)

Maximum Value in a Binary Tree EASY

def find_max_value(root):
    if not root:
        return float('-inf')
    return max(root.val, find_max_value(root.left), find_max_value(root.right))

Count Leaf Nodes EASY

def count_leaves(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

Search in a Binary Search Tree EASY

def bst_contains(root, target):
    while root:
        if root.val == target:
            return True
        root = root.left if target < root.val else root.right
    return False

Range Sum of BST EASY

def range_sum_bst(root, low, high):
    if not root:
        return 0
    if root.val < low:
        return range_sum_bst(root.right, low, high)
    if root.val > high:
        return range_sum_bst(root.left, low, high)
    return root.val + range_sum_bst(root.left, low, high) + range_sum_bst(root.right, low, high)

Tree Traversal - BFS & DFS MEDIUM

DFS (depth-first) uses recursion / a stack; BFS (breadth-first, level by level) uses a queue.

def dfs(node):                # depth-first (pre-order)
    if node is None:
        return
    print(node.value)
    dfs(node.left)
    dfs(node.right)

from collections import deque
def bfs(root):                # breadth-first (level order)
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)

Validate BST MEDIUM

class Solution:
    def validate_bst(self, node, lo=float("-inf"), hi=float("inf")):
        if node is None: return True
        if not (lo < node.value < hi): return False
        return (self.validate_bst(node.left, lo, node.value) and
                self.validate_bst(node.right, node.value, hi))

Invert Binary Tree MEDIUM

class Solution:
    def invert_tree(self, node):
        if node is None: return
        node.left, node.right = node.right, node.left
        self.invert_tree(node.left)
        self.invert_tree(node.right)

BST Traversal (in / pre / post order) MEDIUM

class Solution:
    def in_order(self, node, out):     # left, root, right -> sorted!
        if node:
            self.in_order(node.left, out); out.append(node.value); self.in_order(node.right, out)
    def pre_order(self, node, out):    # root, left, right
        if node:
            out.append(node.value); self.pre_order(node.left, out); self.pre_order(node.right, out)
    def post_order(self, node, out):   # left, right, root
        if node:
            self.post_order(node.left, out); self.post_order(node.right, out); out.append(node.value)

Youngest Common Ancestor (LCA) MEDIUM

Lowest common ancestor when nodes have a .parent. Equalize depths, then climb together. O(d).

class Solution:
    def get_depth(self, node, top):
        d = 0
        while node != top: node = node.parent; d += 1
        return d
    def youngest_common_ancestor(self, top, a, b):
        da, db = self.get_depth(a, top), self.get_depth(b, top)
        while da > db: a = a.parent; da -= 1
        while db > da: b = b.parent; db -= 1
        while a != b: a = a.parent; b = b.parent
        return a

Iterative In-order Traversal MEDIUM

class Solution:
    def inorder(self, root):
        res = []; stack = []; node = root
        while stack or node:
            while node:
                stack.append(node); node = node.left
            node = stack.pop()
            res.append(node.value)
            node = node.right
        return res

Symmetrical Tree MEDIUM

class Solution:
    def is_symmetric(self, root):
        def mirror(a, b):
            if not a and not b: return True
            if not a or not b or a.value != b.value: return False
            return mirror(a.left, b.right) and mirror(a.right, b.left)
        return mirror(root, root)

Height Balanced Binary Tree MEDIUM

class Solution:
    def is_balanced(self, root):
        def check(node):
            if not node: return 0
            lh = check(node.left); rh = check(node.right)
            if lh == -1 or rh == -1 or abs(lh - rh) > 1: return -1
            return max(lh, rh) + 1
        return check(root) != -1

Flatten Binary Tree (to a list) MEDIUM

class Solution:
    def flatten_tree(self, root):
        node = root
        while node:
            if node.left:
                rightmost = node.left
                while rightmost.right: rightmost = rightmost.right
                rightmost.right = node.right
                node.right = node.left; node.left = None
            node = node.right
        return root

Min Height BST MEDIUM

Build a balanced BST from a sorted array - recurse on the middle. O(n).

class Solution:
    def min_height_bst(self, arr):
        def build(lo, hi):
            if lo > hi: return None
            mid = (lo + hi) // 2
            node = BST(arr[mid])
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node
        return build(0, len(arr) - 1)

Find Kth Largest Value In BST MEDIUM

Reverse in-order (right, node, left) gives values largest-first. O(h+k).

class Solution:
    def kth_largest_bst(self, root, k):
        stack = []; node = root; count = 0
        while stack or node:
            while node:
                stack.append(node); node = node.right
            node = stack.pop(); count += 1
            if count == k: return node.value
            node = node.left

Reconstruct BST (from pre-order) MEDIUM

class Solution:
    def reconstruct_bst(self, preorder):
        idx = [0]
        def build(bound=float("inf")):
            if idx[0] == len(preorder) or preorder[idx[0]] >= bound:
                return None
            val = preorder[idx[0]]; idx[0] += 1
            node = BST(val)
            node.left = build(val)
            node.right = build(bound)
            return node
        return build()

Find Successor (in-order) MEDIUM

class Solution:
    def find_successor(self, node):
        if node.right:                       # leftmost of the right subtree
            node = node.right
            while node.left: node = node.left
            return node
        while node.parent and node.parent.right == node:
            node = node.parent               # climb until we go up-left
        return node.parent

Merge Binary Trees MEDIUM

class Solution:
    def merge_trees(self, t1, t2):
        if not t1: return t2
        if not t2: return t1
        t1.value += t2.value
        t1.left = self.merge_trees(t1.left, t2.left)
        t1.right = self.merge_trees(t1.right, t2.right)
        return t1

Max Path Sum In Binary Tree HARD

Largest sum along any path. At each node, best = node + best-left-branch + best-right-branch. O(n).

class Solution:
    def max_path_sum(self, root):
        best = [float("-inf")]
        def helper(node):
            if not node: return 0
            left = max(helper(node.left), 0)
            right = max(helper(node.right), 0)
            best[0] = max(best[0], node.value + left + right)
            return node.value + max(left, right)
        helper(root)
        return best[0]

All Kinds Of Node Depths HARD

Sum of node depths across every subtree. O(n) with a helper that returns sum + count.

class Solution:
    def all_kinds_of_node_depths(self, root):
        def helper(node):
            if not node: return (0, 0)          # (sum_of_depths, node_count)
            ls, lc = helper(node.left)
            rs, rc = helper(node.right)
            depth_sum = ls + lc + rs + rc        # +1 depth for each descendant
            return (depth_sum, lc + rc + 1)
        def total(node):
            if not node: return 0
            return helper(node)[0] + total(node.left) + total(node.right)
        return total(root)

Number Of Binary Tree Topologies HARD

How many tree shapes with n nodes (the Catalan numbers). DP. O(n²).

class Solution:
    def number_of_binary_tree_topologies(self, n):
        cache = [1]
        for m in range(1, n + 1):
            total = 0
            for left in range(m):
                total += cache[left] * cache[m - 1 - left]
            cache.append(total)
        return cache[n]

Compare Leaf Traversal HARD

Do two trees have the same left-to-right leaf sequence?

class Solution:
    def compare_leaf_traversal(self, t1, t2):
        def leaves(node, out):
            if not node: return
            if not node.left and not node.right:
                out.append(node.value); return
            leaves(node.left, out); leaves(node.right, out)
        a, b = [], []
        leaves(t1, a); leaves(t2, b)
        return a == b

Find Nodes Distance K HARD

All nodes exactly k edges from a target. Map parents, then BFS treating the tree as a graph. O(n).

from collections import deque

class Solution:
    def find_nodes_distance_k(self, tree, target, k):
        parents = {}
        def map_parents(node, parent=None):
            if not node: return
            parents[node.value] = parent
            map_parents(node.left, node); map_parents(node.right, node)
        def find(node):
            if not node or node.value == target: return node
            return find(node.left) or find(node.right)
        map_parents(tree)
        start = find(tree)
        queue = deque([(start, 0)]); seen = {start.value}; res = []
        while queue:
            node, dist = queue.popleft()
            if dist == k: res.append(node.value); continue
            for nb in (node.left, node.right, parents[node.value]):
                if nb and nb.value not in seen:
                    seen.add(nb.value); queue.append((nb, dist + 1))
        return res

Binary Tree Maximum Path Sum HARD

def max_path_sum_trees(root):
    best = float('-inf')
    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)
    gain(root)
    return best

Lowest Common Ancestor HARD

def lowest_common_ancestor_trees(root, p, q):
    def helper(node):
        if not node:
            return None
        if node.val == p or node.val == q:
            return node
        left = helper(node.left)
        right = helper(node.right)
        if left and right:
            return node
        return left or right
    return helper(root).val

Path Sum III (Count Paths) HARD

def path_sum_count(root, target):
    from collections import defaultdict
    prefix = defaultdict(int)
    prefix[0] = 1
    def dfs(node, current):
        if not node:
            return 0
        current += node.val
        count = prefix[current - target]
        prefix[current] += 1
        count += dfs(node.left, current) + dfs(node.right, current)
        prefix[current] -= 1
        return count
    return dfs(root, 0)

Vertical Order Traversal HARD

def vertical_order(root):
    from collections import defaultdict
    columns = defaultdict(list)
    def dfs(node, row, col):
        if not node:
            return
        columns[col].append((row, node.val))
        dfs(node.left, row + 1, col - 1)
        dfs(node.right, row + 1, col + 1)
    dfs(root, 0, 0)
    result = []
    for col in sorted(columns):
        result.append([val for row, val in sorted(columns[col])])
    return result

Maximum Width of Binary Tree HARD

def max_width(root):
    if not root:
        return 0
    from collections import deque
    best = 0
    queue = deque([(root, 0)])
    while queue:
        n = len(queue)
        _, first = queue[0]
        last = first
        for _ in range(n):
            node, idx = queue.popleft()
            last = idx
            if node.left:
                queue.append((node.left, 2 * idx))
            if node.right:
                queue.append((node.right, 2 * idx + 1))
        best = max(best, last - first + 1)
    return best

Distribute Coins in Binary Tree HARD

def distribute_coins(root):
    moves = 0
    def dfs(node):
        nonlocal moves
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        moves += abs(left) + abs(right)
        return node.val + left + right - 1
    dfs(root)
    return moves

Graphs

Build an Adjacency List EASY

def build_adjacency_list(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

Node Degree EASY

def node_degree(adj, node):
    return len(adj[node])

Count Edges in an Undirected Graph EASY

def count_edges(adj):
    total = sum(len(neighbors) for neighbors in adj)
    return total // 2

Check if an Edge Exists EASY

def has_edge(adj, u, v):
    return v in adj[u]

Breadth-First Search Order EASY

def bfs_order(adj, start):
    from collections import deque
    visited = [False] * len(adj)
    order = []
    queue = deque([start])
    visited[start] = True
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in adj[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    return order

Depth-First Search Order EASY

def dfs_order(adj, start):
    visited = [False] * len(adj)
    order = []
    def dfs(node):
        visited[node] = True
        order.append(node)
        for neighbor in adj[node]:
            if not visited[neighbor]:
                dfs(neighbor)
    dfs(start)
    return order

Count Reachable Nodes EASY

def count_reachable(adj, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in adj[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return len(visited)

List a Node's Neighbors EASY

def get_neighbors(adj, node):
    return sorted(adj[node])

Path Exists Between Two Nodes EASY

def path_exists(adj, source, dest):
    visited = set()
    stack = [source]
    while stack:
        node = stack.pop()
        if node == dest:
            return True
        if node in visited:
            continue
        visited.add(node)
        stack.extend(adj[node])
    return dest in visited

Count Connected Components EASY

def count_components(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    visited = [False] * n
    count = 0
    for i in range(n):
        if not visited[i]:
            count += 1
            stack = [i]
            while stack:
                node = stack.pop()
                if visited[node]:
                    continue
                visited[node] = True
                stack.extend(adj[node])
    return count

Cycle In Graph MEDIUM

Detect a cycle in a directed graph (adjacency list). DFS tracking the current path. O(V+E).

class Solution:
    def cycle_in_graph(self, edges):
        n = len(edges)
        visited = [False] * n; in_path = [False] * n
        def dfs(node):
            visited[node] = in_path[node] = True
            for nb in edges[node]:
                if not visited[nb]:
                    if dfs(nb): return True
                elif in_path[nb]:
                    return True
            in_path[node] = False
            return False
        return any(dfs(i) for i in range(n) if not visited[i])

Remove Islands MEDIUM

Flip any group of 1s not connected to the border to 0. Mark border-connected 1s, then clear the rest. O(w·h).

class Solution:
    def remove_islands(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        def fill(r, c):
            stack = [(r, c)]
            while stack:
                r, c = stack.pop()
                if 0 <= r < rows and 0 <= c < cols and matrix[r][c] == 1:
                    matrix[r][c] = 2                      # mark as safe
                    stack += [(r+1,c),(r-1,c),(r,c+1),(r,c-1)]
        for r in range(rows):
            for c in range(cols):
                if (r in (0, rows-1) or c in (0, cols-1)) and matrix[r][c] == 1:
                    fill(r, c)
        for r in range(rows):
            for c in range(cols):
                matrix[r][c] = 1 if matrix[r][c] == 2 else 0
        return matrix

River Sizes MEDIUM

Sizes of every connected group of 1s in a grid. Flood-fill each. O(w·h).

class Solution:
    def river_sizes(self, matrix):
        sizes = []
        visited = [[False] * len(matrix[0]) for _ in matrix]
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == 1 and not visited[r][c]:
                    size = 0; stack = [(r, c)]
                    while stack:
                        i, j = stack.pop()
                        if (i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0])
                                or visited[i][j] or matrix[i][j] == 0):
                            continue
                        visited[i][j] = True; size += 1
                        stack += [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]
                    sizes.append(size)
        return sizes

Union-Find (Disjoint Set) MEDIUM

Track which items are connected. Near-O(1) with path compression.

class UnionFind:
    def __init__(self): self.parent = {}
    def add(self, x): self.parent.setdefault(x, x)
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression
            x = self.parent[x]
        return x
    def union(self, a, b):
        self.parent[self.find(a)] = self.find(b)

Two-Colorable (bipartite check) MEDIUM

Can the graph be 2-colored so no edge joins same colors? BFS, alternate colors. O(V+E).

from collections import deque

class Solution:
    def two_colorable(self, edges):
        colors = [None] * len(edges)
        colors[0] = True
        queue = deque([0])
        while queue:
            node = queue.popleft()
            for nb in edges[node]:
                if colors[nb] is None:
                    colors[nb] = not colors[node]; queue.append(nb)
                elif colors[nb] == colors[node]:
                    return False
        return True

Min Knight Moves (BFS) MEDIUM

from collections import deque

class Solution:
    def min_knight_moves(self, start, target):
        moves = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]
        q = deque([(start[0], start[1], 0)]); seen = {tuple(start)}
        while q:
            r, c, d = q.popleft()
            if [r, c] == target: return d
            for dr, dc in moves:
                nxt = (r + dr, c + dc)
                if nxt not in seen:
                    seen.add(nxt); q.append((nxt[0], nxt[1], d + 1))

Number of Islands MEDIUM

def num_islands_graphs(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return
        grid[r][c] = 0
        sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                count += 1
                sink(r, c)
    return count

Max Area of Island MEDIUM

def max_area_of_island(grid):
    rows, cols = len(grid), len(grid[0])
    def area(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
            return 0
        grid[r][c] = 0
        return 1 + area(r+1, c) + area(r-1, c) + area(r, c+1) + area(r, c-1)
    best = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                best = max(best, area(r, c))
    return best

Flood Fill MEDIUM

def flood_fill(image, sr, sc, new_color):
    old = image[sr][sc]
    if old == new_color:
        return image
    rows, cols = len(image), len(image[0])
    def fill(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
            return
        image[r][c] = new_color
        fill(r+1, c); fill(r-1, c); fill(r, c+1); fill(r, c-1)
    fill(sr, sc)
    return image

Is Graph Bipartite MEDIUM

def is_bipartite(graph):
    color = {}
    for start in range(len(graph)):
        if start in color:
            continue
        color[start] = 0
        stack = [start]
        while stack:
            node = stack.pop()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = color[node] ^ 1
                    stack.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False
    return True

Course Schedule (Can Finish) MEDIUM

def can_finish_graphs(num_courses, prerequisites):
    from collections import deque
    adj = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for a, b in prerequisites:
        adj[b].append(a)
        indegree[a] += 1
    queue = deque(i for i in range(num_courses) if indegree[i] == 0)
    taken = 0
    while queue:
        node = queue.popleft()
        taken += 1
        for nxt in adj[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return taken == num_courses

Topological Sort HARD

Order tasks so each comes after its prerequisites. Kahn's algorithm (in-degrees + queue). O(V+E).

from collections import deque

class Solution:
    def topological_sort(self, jobs, deps):
        graph = {j: [] for j in jobs}
        indegree = {j: 0 for j in jobs}
        for a, b in deps:                 # a must come before b
            graph[a].append(b); indegree[b] += 1
        queue = deque(j for j in jobs if indegree[j] == 0)
        order = []
        while queue:
            j = queue.popleft(); order.append(j)
            for nb in graph[j]:
                indegree[nb] -= 1
                if indegree[nb] == 0: queue.append(nb)
        return order if len(order) == len(jobs) else []   # [] means a cycle

Dijkstra's Algorithm (shortest paths) HARD

Shortest distance from a start node to all others (non-negative weights). Min-heap. O(E log V).

import heapq

class Solution:
    def dijkstra(self, start, edges):
        # edges[i] = list of [destination, weight]
        dist = [float("inf")] * len(edges); dist[start] = 0
        pq = [(0, start)]
        while pq:
            d, node = heapq.heappop(pq)
            if d > dist[node]: continue
            for nb, w in edges[node]:
                if d + w < dist[nb]:
                    dist[nb] = d + w; heapq.heappush(pq, (d + w, nb))
        return [-1 if d == float("inf") else d for d in dist]

Boggle Board HARD

Find which words appear on the board (8-directional). Trie of words + DFS.

class Solution:
    def boggle_board(self, board, words):
        trie = {}
        for w in words:                 # build a trie
            node = trie
            for ch in w: node = node.setdefault(ch, {})
            node["*"] = w
        rows, cols = len(board), len(board[0])
        found = set()
        def dfs(r, c, node, visited):
            if (r < 0 or c < 0 or r >= rows or c >= cols or (r, c) in visited
                    or board[r][c] not in node):
                return
            node = node[board[r][c]]; visited = visited | {(r, c)}
            if "*" in node: found.add(node["*"])
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    dfs(r + dr, c + dc, node, visited)
        for r in range(rows):
            for c in range(cols):
                dfs(r, c, trie, set())
        return list(found)

A* Algorithm (heuristic pathfinding) HARD

Like Dijkstra but guided by a heuristic toward the goal. Min-heap on (cost + estimate).

import heapq

class Solution:
    def a_star(self, start, end, graph):
        # graph[node] = list of (neighbor, cost); positions are (row, col)
        h = lambda a, b: abs(a[0]-b[0]) + abs(a[1]-b[1])   # Manhattan estimate
        pq = [(h(start, end), 0, start)]
        g = {start: 0}
        while pq:
            _, cost, node = heapq.heappop(pq)
            if node == end: return cost
            for nb, w in graph.get(node, []):
                ng = cost + w
                if nb not in g or ng < g[nb]:
                    g[nb] = ng
                    heapq.heappush(pq, (ng + h(nb, end), ng, nb))
        return -1

Detect Arbitrage HARD

Is there a currency cycle that multiplies to > 1? Take −log of rates → a profitable cycle is a negative cycle (Bellman-Ford). O(n³).

import math

class Solution:
    def detect_arbitrage(self, rates):
        n = len(rates)
        graph = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
        dist = [0] * n
        for _ in range(n - 1):                 # relax edges n-1 times
            for u in range(n):
                for v in range(n):
                    if dist[u] + graph[u][v] < dist[v]:
                        dist[v] = dist[u] + graph[u][v]
        for u in range(n):                     # one more pass detects a neg cycle
            for v in range(n):
                if dist[u] + graph[u][v] < dist[v]:
                    return True
        return False

Kruskal's Algorithm (MST) HARD

Cheapest set of edges connecting every node. Sort edges, add if they join two different groups (union-find). O(E log E).

class Solution:
    def kruskal(self, n, edges):
        # edges = [(weight, u, v), ...]
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]; x = parent[x]
            return x
        total = 0
        for w, u, v in sorted(edges):
            ru, rv = find(u), find(v)
            if ru != rv:
                parent[ru] = rv; total += w
        return total

Prim's Algorithm (MST) HARD

import heapq

class Solution:
    def prim(self, n, adj):
        # adj[u] = list of (weight, v)
        visited = [False] * n; pq = [(0, 0)]; total = 0
        while pq:
            w, u = heapq.heappop(pq)
            if visited[u]: continue
            visited[u] = True; total += w
            for weight, v in adj[u]:
                if not visited[v]: heapq.heappush(pq, (weight, v))
        return total

Course Schedule II (Order) HARD

def find_order_graphs(num_courses, prerequisites):
    from collections import deque
    adj = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for a, b in prerequisites:
        adj[b].append(a)
        indegree[a] += 1
    queue = deque(i for i in range(num_courses) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in adj[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)
    return order if len(order) == num_courses else []

Network Delay Time HARD

def network_delay_time(times, n, k):
    import heapq
    graph = [[] for _ in range(n + 1)]
    for u, v, w in times:
        graph[u].append((v, w))
    dist = {}
    heap = [(0, k)]
    while heap:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue
        dist[node] = d
        for neighbor, weight in graph[node]:
            if neighbor not in dist:
                heapq.heappush(heap, (d + weight, neighbor))
    return max(dist.values()) if len(dist) == n else -1

Word Ladder Length HARD

def ladder_length_graphs(begin_word, end_word, word_list):
    from collections import deque
    words = set(word_list)
    if end_word not in words:
        return 0
    queue = deque([(begin_word, 1)])
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                candidate = word[:i] + c + word[i+1:]
                if candidate in words:
                    words.remove(candidate)
                    queue.append((candidate, steps + 1))
    return 0

Cheapest Flights Within K Stops HARD

def find_cheapest_price(n, flights, src, dst, k):
    prices = [float('inf')] * n
    prices[src] = 0
    for _ in range(k + 1):
        temp = prices[:]
        for u, v, w in flights:
            if prices[u] + w < temp[v]:
                temp[v] = prices[u] + w
        prices = temp
    return prices[dst] if prices[dst] != float('inf') else -1

Heaps

Kth Largest Element in an Array EASY

def kth_largest_element(nums, k):
    import heapq
    return heapq.nlargest(k, nums)[-1]

Kth Smallest Element in an Array EASY

def kth_smallest_element(nums, k):
    import heapq
    return heapq.nsmallest(k, nums)[-1]

K Smallest Elements EASY

def k_smallest(nums, k):
    import heapq
    return sorted(heapq.nsmallest(k, nums))

K Largest Elements EASY

def k_largest(nums, k):
    import heapq
    return sorted(heapq.nlargest(k, nums), reverse=True)

Last Stone Weight EASY

def last_stone_weight(stones):
    import heapq
    heap = [-s for s in stones]
    heapq.heapify(heap)
    while len(heap) > 1:
        a = -heapq.heappop(heap)
        b = -heapq.heappop(heap)
        if a != b:
            heapq.heappush(heap, -(a - b))
    return -heap[0] if heap else 0

Heap Sort EASY

def heap_sort_heaps(nums):
    import heapq
    heap = list(nums)
    heapq.heapify(heap)
    return [heapq.heappop(heap) for _ in range(len(heap))]

Is Array a Valid Min-Heap EASY

def is_min_heap(arr):
    n = len(arr)
    for i in range(n):
        l, r = 2 * i + 1, 2 * i + 2
        if l < n and arr[i] > arr[l]:
            return False
        if r < n and arr[i] > arr[r]:
            return False
    return True

Sum of K Smallest Elements EASY

def sum_k_smallest(nums, k):
    import heapq
    return sum(heapq.nsmallest(k, nums))

Sum of K Largest Elements EASY

def sum_k_largest(nums, k):
    import heapq
    return sum(heapq.nlargest(k, nums))

Minimum Cost to Connect Ropes EASY

def connect_ropes(ropes):
    import heapq
    heapq.heapify(ropes)
    total = 0
    while len(ropes) > 1:
        a = heapq.heappop(ropes)
        b = heapq.heappop(ropes)
        total += a + b
        heapq.heappush(ropes, a + b)
    return total

Top K Frequent Elements MEDIUM

def top_k_frequent(nums, k):
    import heapq
    from collections import Counter
    freq = Counter(nums)
    return heapq.nlargest(k, freq.keys(), key=freq.get)

K Closest Points to Origin MEDIUM

def k_closest_points(points, k):
    import heapq
    return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)

Kth Largest in a Stream MEDIUM

def kth_largest_stream(k, initial, adds):
    import heapq
    heap = initial[:]
    heapq.heapify(heap)
    while len(heap) > k:
        heapq.heappop(heap)
    out = []
    for x in adds:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
        out.append(heap[0])
    return out

Sort Characters by Frequency MEDIUM

def frequency_sort(s):
    import heapq
    from collections import Counter
    freq = Counter(s)
    heap = [(-c, ch) for ch, c in freq.items()]
    heapq.heapify(heap)
    out = []
    while heap:
        c, ch = heapq.heappop(heap)
        out.append(ch * (-c))
    return ''.join(out)

Find K Pairs With Smallest Sums MEDIUM

def k_smallest_pairs_heaps(nums1, nums2, k):
    import heapq
    if not nums1 or not nums2:
        return []
    heap = [(nums1[i] + nums2[0], i, 0) for i in range(min(k, len(nums1)))]
    heapq.heapify(heap)
    out = []
    while heap and len(out) < k:
        _, i, j = heapq.heappop(heap)
        out.append([nums1[i], nums2[j]])
        if j + 1 < len(nums2):
            heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
    return out

Minimum Number of Meeting Rooms MEDIUM

def min_meeting_rooms(intervals):
    import heapq
    if not intervals:
        return 0
    intervals.sort()
    heap = []
    for s, e in intervals:
        if heap and heap[0] <= s:
            heapq.heappop(heap)
        heapq.heappush(heap, e)
    return len(heap)

Furthest Building You Can Reach MEDIUM

def furthest_building(heights, bricks, ladders):
    import heapq
    heap = []
    for i in range(len(heights) - 1):
        diff = heights[i + 1] - heights[i]
        if diff > 0:
            heapq.heappush(heap, diff)
            if len(heap) > ladders:
                bricks -= heapq.heappop(heap)
                if bricks < 0:
                    return i
    return len(heights) - 1

Reduce Array Size to Half MEDIUM

def min_set_size(arr):
    import heapq
    from collections import Counter
    counts = [-c for c in Counter(arr).values()]
    heapq.heapify(counts)
    removed = 0
    ops = 0
    while removed < len(arr) // 2:
        removed += -heapq.heappop(counts)
        ops += 1
    return ops

Maximum Score After K Operations MEDIUM

def max_score_k_ops(nums, k):
    import heapq, math
    heap = [-n for n in nums]
    heapq.heapify(heap)
    score = 0
    for _ in range(k):
        x = -heapq.heappop(heap)
        score += x
        heapq.heappush(heap, -math.ceil(x / 3))
    return score

Take Gifts With Maximum Value MEDIUM

def take_gifts(gifts, k):
    import heapq, math
    heap = [-g for g in gifts]
    heapq.heapify(heap)
    for _ in range(k):
        x = -heapq.heappop(heap)
        heapq.heappush(heap, -math.isqrt(x))
    return -sum(heap)

Continuous Median HARD

Median of a growing stream. Keep a max-heap of the low half & a min-heap of the high half. O(log n) per add.

import heapq
class ContinuousMedian:
    def __init__(self):
        self.lo = []   # max-heap (store negatives)
        self.hi = []   # min-heap
    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))  # balance
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
    def median(self):
        if len(self.lo) > len(self.hi): return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Heap Sort HARD

import heapq

class Solution:
    def heap_sort(self, arr):
        heapq.heapify(arr)                       # O(n)
        return [heapq.heappop(arr) for _ in range(len(arr))]   # n × O(log n)

Median Of Two Sorted Arrays HARD

O(log(min(m,n))) by binary-searching the partition point.

class Solution:
    def median_two_sorted(self, a, b):
        if len(a) > len(b): a, b = b, a
        m, n = len(a), len(b)
        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2
            j = (m + n + 1) // 2 - i
            a_l = a[i-1] if i > 0 else float("-inf")
            a_r = a[i]   if i < m else float("inf")
            b_l = b[j-1] if j > 0 else float("-inf")
            b_r = b[j]   if j < n else float("inf")
            if a_l <= b_r and b_l <= a_r:
                if (m + n) % 2: return max(a_l, b_l)
                return (max(a_l, b_l) + min(a_r, b_r)) / 2
            elif a_l > b_r: hi = i - 1
            else: lo = i + 1

Find Median From a Data Stream HARD

def running_median(nums):
    import heapq
    low, high, out = [], [], []
    for n in nums:
        heapq.heappush(low, -n)
        heapq.heappush(high, -heapq.heappop(low))
        if len(high) > len(low):
            heapq.heappush(low, -heapq.heappop(high))
        if len(low) > len(high):
            out.append(float(-low[0]))
        else:
            out.append((-low[0] + high[0]) / 2)
    return out

Merge K Sorted Lists HARD

def merge_k_sorted(lists):
    import heapq
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)
        out.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out

Kth Smallest Element in a Sorted Matrix HARD

def kth_smallest_matrix(matrix, k):
    import heapq
    n = len(matrix)
    heap = [(matrix[r][0], r, 0) for r in range(n)]
    heapq.heapify(heap)
    val = None
    for _ in range(k):
        val, r, c = heapq.heappop(heap)
        if c + 1 < len(matrix[r]):
            heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
    return val

Smallest Range Covering K Lists HARD

def smallest_range(nums):
    import heapq
    heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
    heapq.heapify(heap)
    cur_max = max(lst[0] for lst in nums)
    best = [heap[0][0], cur_max]
    while True:
        val, i, j = heapq.heappop(heap)
        if cur_max - val < best[1] - best[0]:
            best = [val, cur_max]
        if j + 1 == len(nums[i]):
            break
        nxt = nums[i][j + 1]
        cur_max = max(cur_max, nxt)
        heapq.heappush(heap, (nxt, i, j + 1))
    return best

Sliding Window Median HARD

def median_sliding_window(nums, k):
    import bisect
    window = sorted(nums[:k])
    out = []
    for i in range(k, len(nums) + 1):
        if k % 2:
            out.append(float(window[k // 2]))
        else:
            out.append((window[k // 2 - 1] + window[k // 2]) / 2)
        if i < len(nums):
            window.pop(bisect.bisect_left(window, nums[i - k]))
            bisect.insort(window, nums[i])
    return out

Minimum Cost to Hire K Workers HARD

def min_cost_hire(quality, wage, k):
    import heapq
    workers = sorted(zip(wage, quality), key=lambda w: w[0] / w[1])
    heap = []
    total_q = 0
    best = float('inf')
    for w, q in workers:
        heapq.heappush(heap, -q)
        total_q += q
        if len(heap) > k:
            total_q += heapq.heappop(heap)
        if len(heap) == k:
            best = min(best, total_q * (w / q))
    return round(best, 5)

Single-Threaded CPU HARD

def get_task_order(tasks):
    import heapq
    indexed = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
    heap = []
    order = []
    time = 0
    i = 0
    while i < len(indexed) or heap:
        if not heap and time < tasks[indexed[i]][0]:
            time = tasks[indexed[i]][0]
        while i < len(indexed) and tasks[indexed[i]][0] <= time:
            idx = indexed[i]
            heapq.heappush(heap, (tasks[idx][1], idx))
            i += 1
        proc, idx = heapq.heappop(heap)
        time += proc
        order.append(idx)
    return order

Maximum Performance of a Team HARD

def max_performance(n, speed, efficiency, k):
    import heapq
    workers = sorted(zip(efficiency, speed), reverse=True)
    heap = []
    speed_sum = 0
    best = 0
    for eff, spd in workers:
        heapq.heappush(heap, spd)
        speed_sum += spd
        if len(heap) > k:
            speed_sum -= heapq.heappop(heap)
        best = max(best, speed_sum * eff)
    return best % (10**9 + 7)

Minimize Deviation in Array HARD

def minimum_deviation(nums):
    import heapq
    heap = [-(n * 2 if n % 2 else n) for n in nums]
    heapq.heapify(heap)
    low = -max(heap)
    best = float('inf')
    while True:
        x = -heapq.heappop(heap)
        best = min(best, x - low)
        if x % 2:
            break
        x //= 2
        low = min(low, x)
        heapq.heappush(heap, -x)
    return best

Rearrange String K Distance Apart HARD

def rearrange_k_distance(s, k):
    import heapq
    from collections import Counter, deque
    if k <= 1:
        return s
    heap = [(-c, ch) for ch, c in Counter(s).items()]
    heapq.heapify(heap)
    wait = deque()
    out = []
    while heap:
        c, ch = heapq.heappop(heap)
        out.append(ch)
        wait.append((c + 1, ch))
        if len(wait) >= k:
            cnt, chr_ = wait.popleft()
            if cnt < 0:
                heapq.heappush(heap, (cnt, chr_))
    return ''.join(out) if len(out) == len(s) else ''

Recursion & Backtracking

Factorial (Recursive) EASY

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Fibonacci Number EASY

def fibonacci(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

Sum From 1 to N (Recursive) EASY

def sum_to_n(n):
    if n <= 0:
        return 0
    return n + sum_to_n(n - 1)

Power Function (Recursive) EASY

def power(base, exp):
    if exp == 0:
        return 1
    return base * power(base, exp - 1)

Reverse a String Recursively EASY

def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]

Greatest Common Divisor EASY

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

Count Digits (Recursive) EASY

def count_digits(n):
    if n < 10:
        return 1
    return 1 + count_digits(n // 10)

Sum of Digits (Recursive) EASY

def sum_of_digits(n):
    if n < 10:
        return n
    return n % 10 + sum_of_digits(n // 10)

Recursive Palindrome Check EASY

def is_palindrome_recursion(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome_recursion(s[1:-1])

Sum of an Array (Recursive) EASY

def array_sum_recursion(nums, i=0):
    if i == len(nums):
        return 0
    return nums[i] + array_sum_recursion(nums, i + 1)

Permutations MEDIUM

class Solution:
    def permutations(self, arr):
        if len(arr) <= 1: return [arr[:]]
        res = []
        for i in range(len(arr)):
            rest = arr[:i] + arr[i+1:]
            for p in self.permutations(rest):
                res.append([arr[i]] + p)
        return res

Powerset (all subsets) MEDIUM

class Solution:
    def powerset(self, arr):
        subsets = [[]]
        for n in arr:
            subsets += [s + [n] for s in subsets]
        return subsets
    # [1,2] -> [[], [1], [2], [1,2]]

Phone Number Mnemonics MEDIUM

class Solution:
    def phone_mnemonics(self, digits):
        keys = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno",
                "7":"pqrs","8":"tuv","9":"wxyz","0":"0","1":"1"}
        res = []
        def backtrack(i, cur):
            if i == len(digits):
                res.append("".join(cur)); return
            for ch in keys[digits[i]]:
                cur.append(ch); backtrack(i+1, cur); cur.pop()
        backtrack(0, [])
        return res

Staircase Traversal MEDIUM

Ways to climb height stairs taking 1..maxSteps at a time. DP. O(n·k).

class Solution:
    def staircase(self, height, max_steps):
        ways = [1] + [0] * height
        for h in range(1, height + 1):
            for step in range(1, min(h, max_steps) + 1):
                ways[h] += ways[h - step]
        return ways[height]

Generate Div Tags (balanced) MEDIUM

All valid arrangements of n <div></div> pairs (same idea as "generate parentheses").

class Solution:
    def generate_div_tags(self, n):
        res = []
        def build(open_used, close_used, cur):
            if open_used < n:
                build(open_used + 1, close_used, cur + "<div>")
            if close_used < open_used:
                build(open_used, close_used + 1, cur + "</div>")
            if close_used == n:
                res.append(cur)
        build(0, 0, "")
        return res

Subsets MEDIUM

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

Permutations MEDIUM

def permutations_recursion(nums):
    res = []
    def backtrack(path, remaining):
        if not remaining:
            res.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])
            backtrack(path, remaining[:i] + remaining[i+1:])
            path.pop()
    backtrack([], nums)
    return res

Combinations MEDIUM

def combine_recursion(n, k):
    res = []
    def backtrack(start, path):
        if len(path) == k:
            res.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    backtrack(1, [])
    return res

Combination Sum MEDIUM

def combination_sum_recursion(candidates, target):
    res = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] <= remaining:
                path.append(candidates[i])
                backtrack(i, path, remaining - candidates[i])
                path.pop()
    backtrack(0, [], target)
    return res

Generate Parentheses MEDIUM

def generate_parentheses(n):
    res = []
    def backtrack(s, open_count, close_count):
        if len(s) == 2 * n:
            res.append(s)
            return
        if open_count < n:
            backtrack(s + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(s + ')', open_count, close_count + 1)
    backtrack('', 0, 0)
    return res

Letter Combinations of a Phone Number MEDIUM

def letter_combinations_recursion(digits):
    if not digits:
        return []
    mapping = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
    res = []
    def backtrack(i, path):
        if i == len(digits):
            res.append(path)
            return
        for c in mapping[digits[i]]:
            backtrack(i + 1, path + c)
    backtrack(0, '')
    return res

Subsets II (With Duplicates) MEDIUM

def subsets_with_dup(nums):
    nums.sort()
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res

Permutations II (With Duplicates) MEDIUM

def permute_unique(nums):
    nums.sort()
    res = []
    used = [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i] == nums[i-1] and not used[i-1]):
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    backtrack([])
    return res

Combination Sum II MEDIUM

def combination_sum2(candidates, target):
    candidates.sort()
    res = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i-1]:
                continue
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])
            path.pop()
    backtrack(0, [], target)
    return res

Restore IP Addresses MEDIUM

def restore_ip_addresses(s):
    res = []
    def backtrack(start, parts):
        if len(parts) == 4:
            if start == len(s):
                res.append('.'.join(parts))
            return
        for length in range(1, 4):
            if start + length > len(s):
                break
            part = s[start:start+length]
            if (part[0] == '0' and len(part) > 1) or int(part) > 255:
                continue
            backtrack(start + length, parts + [part])
    backtrack(0, [])
    return res

Solve Sudoku HARD

Fill the grid by trying digits and backtracking when stuck. 0 = empty.

class Solution:
    def solve_sudoku(self, board):
        def valid(r, c, val):
            for i in range(9):
                if board[r][i] == val or board[i][c] == val: return False
            br, bc = 3 * (r // 3), 3 * (c // 3)
            for i in range(br, br + 3):
                for j in range(bc, bc + 3):
                    if board[i][j] == val: return False
            return True
        def solve():
            for r in range(9):
                for c in range(9):
                    if board[r][c] == 0:
                        for val in range(1, 10):
                            if valid(r, c, val):
                                board[r][c] = val
                                if solve(): return True
                                board[r][c] = 0      # backtrack
                        return False
            return True
        solve()
        return board

Count solutions HARD

Place N queens so none attack each other. Backtrack column by column, tracking used columns & diagonals.

class Solution:
    def non_attacking_queens(self, n):
        cols = set(); diag1 = set(); diag2 = set()
        def place(row):
            if row == n: return 1
            count = 0
            for col in range(n):
                if col in cols or (row+col) in diag1 or (row-col) in diag2:
                    continue
                cols.add(col); diag1.add(row+col); diag2.add(row-col)
                count += place(row + 1)
                cols.discard(col); diag1.discard(row+col); diag2.discard(row-col)
            return count
        return place(0)

N-Queens (Count Solutions) HARD

def total_n_queens_recursion(n):
    cols = set()
    diag1 = set()
    diag2 = set()
    def backtrack(row):
        if row == n:
            return 1
        count = 0
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            count += backtrack(row + 1)
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
        return count
    return backtrack(0)

Word Search HARD

def word_search(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False
        tmp = board[r][c]
        board[r][c] = '#'
        found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                 dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
        board[r][c] = tmp
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

Palindrome Partitioning HARD

def palindrome_partition(s):
    res = []
    def is_pal(sub):
        return sub == sub[::-1]
    def backtrack(start, path):
        if start == len(s):
            res.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            sub = s[start:end]
            if is_pal(sub):
                path.append(sub)
                backtrack(end, path)
                path.pop()
    backtrack(0, [])
    return res

Combination Sum III HARD

def combination_sum3(k, n):
    res = []
    def backtrack(start, path, remaining):
        if len(path) == k:
            if remaining == 0:
                res.append(path[:])
            return
        for i in range(start, 10):
            if i > remaining:
                break
            path.append(i)
            backtrack(i + 1, path, remaining - i)
            path.pop()
    backtrack(1, [], n)
    return res

Permutation Sequence HARD

def get_permutation(n, k):
    import math
    numbers = list(range(1, n + 1))
    k -= 1
    result = []
    for i in range(n, 0, -1):
        fact = math.factorial(i - 1)
        idx = k // fact
        result.append(str(numbers.pop(idx)))
        k %= fact
    return ''.join(result)

Gray Code HARD

def gray_code(n):
    res = [0]
    for i in range(n):
        res += [x | (1 << i) for x in reversed(res)]
    return res

Beautiful Arrangement HARD

def count_arrangement(n):
    used = [False] * (n + 1)
    def backtrack(pos):
        if pos > n:
            return 1
        count = 0
        for num in range(1, n + 1):
            if not used[num] and (num % pos == 0 or pos % num == 0):
                used[num] = True
                count += backtrack(pos + 1)
                used[num] = False
        return count
    return backtrack(1)

Partition to K Equal Sum Subsets HARD

def can_partition_k_subsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    nums.sort(reverse=True)
    if nums[0] > target:
        return False
    used = [False] * len(nums)
    def backtrack(count, current, start):
        if count == k:
            return True
        if current == target:
            return backtrack(count + 1, 0, 0)
        for i in range(start, len(nums)):
            if used[i] or current + nums[i] > target:
                continue
            used[i] = True
            if backtrack(count, current + nums[i], i + 1):
                return True
            used[i] = False
        return False
    return backtrack(0, 0, 0)

Matchsticks to Square HARD

def makesquare(matchsticks):
    total = sum(matchsticks)
    if total % 4 != 0:
        return False
    side = total // 4
    matchsticks.sort(reverse=True)
    if matchsticks[0] > side:
        return False
    sides = [0] * 4
    def backtrack(i):
        if i == len(matchsticks):
            return True
        for j in range(4):
            if sides[j] + matchsticks[i] <= side:
                sides[j] += matchsticks[i]
                if backtrack(i + 1):
                    return True
                sides[j] -= matchsticks[i]
            if sides[j] == 0:
                break
        return False
    return backtrack(0)

Letter Case Permutation HARD

def letter_case_permutation(s):
    res = []
    def backtrack(i, path):
        if i == len(s):
            res.append(path)
            return
        if s[i].isalpha():
            backtrack(i + 1, path + s[i].lower())
            backtrack(i + 1, path + s[i].upper())
        else:
            backtrack(i + 1, path + s[i])
    backtrack(0, '')
    return res

Dynamic Programming

Climbing Stairs EASY

def climbing_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

Fibonacci Number (Bottom-Up) EASY

def fib_dp(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

N-th Tribonacci Number EASY

def tribonacci(n):
    if n == 0:
        return 0
    if n <= 2:
        return 1
    a, b, c = 0, 1, 1
    for _ in range(3, n + 1):
        a, b, c = b, c, a + b + c
    return c

Min Cost Climbing Stairs EASY

def min_cost_climbing_stairs(cost):
    a, b = 0, 0
    for i in range(2, len(cost) + 1):
        a, b = b, min(b + cost[i-1], a + cost[i-2])
    return b

House Robber EASY

def house_robber(nums):
    prev, curr = 0, 0
    for n in nums:
        prev, curr = curr, max(curr, prev + n)
    return curr

Is Subsequence EASY

def is_subsequence_dp(s, t):
    i = 0
    for c in t:
        if i < len(s) and s[i] == c:
            i += 1
    return i == len(s)

Pascal's Triangle Row EASY

def pascal_row(row_index):
    row = [1]
    for _ in range(row_index):
        row = [1] + [row[i] + row[i+1] for i in range(len(row)-1)] + [1]
    return row

Unique Paths EASY

def unique_paths(m, n):
    dp = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]
    return dp[-1]

Minimum Path Sum EASY

def min_path_sum_dp(grid):
    rows, cols = len(grid), len(grid[0])
    dp = [float('inf')] * cols
    dp[0] = 0
    for r in range(rows):
        dp[0] += grid[r][0]
        for c in range(1, cols):
            dp[c] = min(dp[c], dp[c-1]) + grid[r][c]
    return dp[-1]

Maximum Subarray (DP) EASY

def max_subarray_dp(nums):
    best = current = nums[0]
    for n in nums[1:]:
        current = max(n, current + n)
        best = max(best, current)
    return best

Dynamic Programming - Fibonacci MEDIUM

Pattern: naive recursion is O(2ⁿ). Memoize (cache) results to make it O(n).

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Min Number Of Coins For Change MEDIUM

class Solution:
    def min_coins(self, n, denoms):
        dp = [float("inf")] * (n + 1)
        dp[0] = 0
        for coin in denoms:
            for amount in range(coin, n + 1):
                dp[amount] = min(dp[amount], dp[amount - coin] + 1)
        return dp[n] if dp[n] != float("inf") else -1

Number Of Ways To Make Change MEDIUM

class Solution:
    def ways_to_make_change(self, n, denoms):
        dp = [0] * (n + 1)
        dp[0] = 1
        for coin in denoms:
            for amount in range(coin, n + 1):
                dp[amount] += dp[amount - coin]
        return dp[n]

Max Subset Sum No Adjacent MEDIUM

class Solution:
    def max_subset_no_adjacent(self, arr):
        if not arr: return 0
        prev, cur = 0, arr[0]
        for n in arr[1:]:
            prev, cur = cur, max(cur, prev + n)
        return cur

Levenshtein Distance (edit distance) MEDIUM

class Solution:
    def levenshtein(self, a, b):
        dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
        for i in range(len(a)+1): dp[i][0] = i
        for j in range(len(b)+1): dp[0][j] = j
        for i in range(1, len(a)+1):
            for j in range(1, len(b)+1):
                if a[i-1] == b[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[-1][-1]

Max Sum Increasing Subsequence MEDIUM

class Solution:
    def max_sum_increasing(self, arr):
        sums = arr[:]
        for i in range(len(arr)):
            for j in range(i):
                if arr[j] < arr[i] and sums[j] + arr[i] > sums[i]:
                    sums[i] = sums[j] + arr[i]
        return max(sums)

Number Of Ways To Traverse Graph (grid) MEDIUM

Paths from top-left to bottom-right moving only right/down. O(w·h).

class Solution:
    def num_ways(self, width, height):
        dp = [[1] * width for _ in range(height)]
        for r in range(1, height):
            for c in range(1, width):
                dp[r][c] = dp[r-1][c] + dp[r][c-1]
        return dp[height-1][width-1]

Coin Change (Number of Combinations) MEDIUM

def change_dp(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]
    return dp[amount]

Word Break MEDIUM

def word_break_dp(s, word_dict):
    words = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[len(s)]

Decode Ways MEDIUM

def num_decodings(s):
    if not s or s[0] == '0':
        return 0
    prev, curr = 1, 1
    for i in range(1, len(s)):
        temp = 0
        if s[i] != '0':
            temp += curr
        if 10 <= int(s[i-1:i+1]) <= 26:
            temp += prev
        prev, curr = curr, temp
    return curr

Longest Palindromic Substring MEDIUM

def longest_palindrome_dp(s):
    if not s:
        return ''
    start, end = 0, 0
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
    for i in range(len(s)):
        l1, r1 = expand(i, i)
        l2, r2 = expand(i, i + 1)
        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2
    return s[start:end + 1]

Numbers In Pi HARD

Fewest spaces to break a digit string into "known" numbers. Memoized recursion. O(n³).

class Solution:
    def numbers_in_pi(self, pi, numbers):
        known = set(numbers); cache = {}
        def helper(idx):
            if idx == len(pi): return -1          # -1 cancels the last +1
            if idx in cache: return cache[idx]
            best = float("inf")
            for i in range(idx, len(pi)):
                if pi[idx:i+1] in known:
                    best = min(best, 1 + helper(i + 1))
            cache[idx] = best
            return best
        result = helper(0)
        return -1 if result == float("inf") else result

Max Profit With K Transactions (stocks) HARD

class Solution:
    def max_profit_k(self, prices, k):
        if not prices: return 0
        dp = [0] * len(prices)
        for _ in range(k):
            max_diff = -prices[0]; new = [0] * len(prices)
            for d in range(1, len(prices)):
                new[d] = max(new[d-1], prices[d] + max_diff)
                max_diff = max(max_diff, dp[d] - prices[d])
            dp = new
        return dp[-1]

Dice Throws (ways to reach a target) HARD

class Solution:
    def dice_throws(self, num_dice, num_sides, target):
        dp = [[0] * (target + 1) for _ in range(num_dice + 1)]
        dp[0][0] = 1
        for d in range(1, num_dice + 1):
            for t in range(1, target + 1):
                for s in range(1, min(t, num_sides) + 1):
                    dp[d][t] += dp[d-1][t-s]
        return dp[num_dice][target]

Disk Stacking HARD

Tallest stack of disks where each must be strictly smaller in all 3 dimensions. DP after sorting by height. O(n²).

class Solution:
    def disk_stacking(self, disks):
        disks.sort(key=lambda d: d[2])         # by height
        heights = [d[2] for d in disks]
        seq = [None] * len(disks); max_i = 0
        for i in range(len(disks)):
            for j in range(i):
                if all(disks[j][k] < disks[i][k] for k in range(3)):
                    if heights[j] + disks[i][2] > heights[i]:
                        heights[i] = heights[j] + disks[i][2]; seq[i] = j
            if heights[i] >= heights[max_i]: max_i = i
        stack = []; i = max_i
        while i is not None:
            stack.append(disks[i]); i = seq[i]
        return stack[::-1]

Interweaving Strings HARD

Is three an interleaving of one and two (keeping each one's order)? Memoized recursion. O(n·m).

class Solution:
    def interweaving(self, one, two, three):
        if len(one) + len(two) != len(three): return False
        cache = {}
        def helper(i, j):
            if i == len(one) and j == len(two): return True
            if (i, j) in cache: return cache[(i, j)]
            res = False
            k = i + j
            if i < len(one) and one[i] == three[k]: res = helper(i + 1, j)
            if not res and j < len(two) and two[j] == three[k]: res = helper(i, j + 1)
            cache[(i, j)] = res
            return res
        return helper(0, 0)

Longest String Chain HARD

Longest chain where each word becomes the next by adding one letter. Sort by length, DP. O(n·L²).

class Solution:
    def longest_string_chain(self, words):
        words.sort(key=len)
        best = {}; longest = 1
        for w in words:
            best[w] = 1
            for i in range(len(w)):
                pred = w[:i] + w[i+1:]          # remove one char
                if pred in best:
                    best[w] = max(best[w], best[pred] + 1)
            longest = max(longest, best[w])
        return longest

Palindrome Partitioning Min Cuts HARD

Fewest cuts so every piece is a palindrome. Precompute palindromes, then DP. O(n²).

class Solution:
    def palindrome_min_cuts(self, s):
        n = len(s)
        is_pal = [[False] * n for _ in range(n)]
        for i in range(n): is_pal[i][i] = True
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and (length == 2 or is_pal[i+1][j-1]):
                    is_pal[i][j] = True
        cuts = [0] * n
        for i in range(n):
            if is_pal[0][i]:
                cuts[i] = 0
            else:
                cuts[i] = min(cuts[j] + 1 for j in range(i) if is_pal[j+1][i])
        return cuts[-1]

Longest Common Subsequence HARD

class Solution:
    def lcs(self, a, b):
        dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
        for i in range(1, len(a) + 1):
            for j in range(1, len(b) + 1):
                if a[i-1] == b[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[-1][-1]

Longest Increasing Subsequence HARD

class Solution:
    def lis(self, arr):
        if not arr: return 0
        dp = [1] * len(arr)
        for i in range(len(arr)):
            for j in range(i):
                if arr[j] < arr[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

0/1 Knapsack HARD

Maximize value within a weight capacity. Classic 2-D DP. O(n·capacity).

class Solution:
    def knapsack(self, items, capacity):
        # items = [[value, weight], ...]
        dp = [[0] * (capacity + 1) for _ in range(len(items) + 1)]
        for i in range(1, len(items) + 1):
            value, weight = items[i-1]
            for c in range(capacity + 1):
                if weight > c:
                    dp[i][c] = dp[i-1][c]
                else:
                    dp[i][c] = max(dp[i-1][c], dp[i-1][c - weight] + value)
        return dp[-1][-1]

Greedy

Array Partition (Max Sum of Min Pairs) EASY

def array_pair_sum(nums):
    nums.sort()
    return sum(nums[::2])

Maximum Units on a Truck EASY

def maximum_units(boxes, truck_size):
    boxes.sort(key=lambda b: -b[1])
    total = 0
    for count, units in boxes:
        take = min(count, truck_size)
        total += take * units
        truck_size -= take
        if truck_size == 0:
            break
    return total

Largest Perimeter Triangle EASY

def largest_perimeter(nums):
    nums.sort(reverse=True)
    for i in range(len(nums) - 2):
        if nums[i] < nums[i + 1] + nums[i + 2]:
            return nums[i] + nums[i + 1] + nums[i + 2]
    return 0

Can Place Flowers EASY

def can_place_flowers(bed, n):
    bed = [0] + bed + [0]
    for i in range(1, len(bed) - 1):
        if bed[i - 1] == 0 and bed[i] == 0 and bed[i + 1] == 0:
            bed[i] = 1
            n -= 1
    return n <= 0

Lemonade Change EASY

def lemonade_change(bills):
    five = ten = 0
    for b in bills:
        if b == 5:
            five += 1
        elif b == 10:
            if five == 0:
                return False
            five -= 1; ten += 1
        else:
            if ten and five:
                ten -= 1; five -= 1
            elif five >= 3:
                five -= 3
            else:
                return False
    return True

Distribute Candies EASY

def distribute_candies(candy_type):
    return min(len(set(candy_type)), len(candy_type) // 2)

Best Time to Buy and Sell Stock II EASY

def max_profit_greedy(prices):
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] > prices[i - 1]:
            profit += prices[i] - prices[i - 1]
    return profit

Assign Cookies EASY

def find_content_children(greed, sizes):
    greed.sort(); sizes.sort()
    i = j = 0
    while i < len(greed) and j < len(sizes):
        if sizes[j] >= greed[i]:
            i += 1
        j += 1
    return i

Maximize Sum After K Negations EASY

def largest_sum_after_k_negations(nums, k):
    nums.sort()
    i = 0
    while k > 0 and i < len(nums) and nums[i] < 0:
        nums[i] = -nums[i]
        i += 1; k -= 1
    if k % 2 == 1:
        nums.sort()
        nums[0] = -nums[0]
    return sum(nums)

Split a String in Balanced Strings EASY

def balanced_string_split(s):
    balance = count = 0
    for c in s:
        balance += 1 if c == 'R' else -1
        if balance == 0:
            count += 1
    return count

Class Photos / Tandem Bicycle / Non-Constructible Change

class Solution:
    # Non-Constructible Change: smallest amount you CAN'T make
    def non_constructible_change(self, coins):
        coins.sort()
        change = 0
        for c in coins:
            if c > change + 1: break
            change += c
        return change + 1

    # Tandem Bicycle: pair fastest with slowest (fastest total speed)
    def tandem_bicycle(self, red, blue, fastest=True):
        red.sort(); blue.sort()
        if fastest: blue.reverse()
        return sum(max(r, b) for r, b in zip(red, blue))

Jump Game MEDIUM

def can_jump_greedy(nums):
    reach = 0
    for i, n in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + n)
    return True

Jump Game II MEDIUM

def jump_greedy(nums):
    jumps = cur_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = farthest
    return jumps

Gas Station MEDIUM

def can_complete_circuit_greedy(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    total = start = 0
    for i in range(len(gas)):
        total += gas[i] - cost[i]
        if total < 0:
            total = 0
            start = i + 1
    return start

Task Scheduler MEDIUM

def least_interval(tasks, n):
    from collections import Counter
    freq = Counter(tasks)
    max_f = max(freq.values())
    max_count = sum(1 for v in freq.values() if v == max_f)
    return max(len(tasks), (max_f - 1) * (n + 1) + max_count)

Partition Labels MEDIUM

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}
    out, start, end = [], 0, 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            out.append(i - start + 1)
            start = i + 1
    return out

Non-overlapping Intervals MEDIUM

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    end = float('-inf')
    removed = 0
    for s, e in intervals:
        if s >= end:
            end = e
        else:
            removed += 1
    return removed

Minimum Arrows to Burst Balloons MEDIUM

def find_min_arrows(points):
    if not points:
        return 0
    points.sort(key=lambda x: x[1])
    arrows = 1
    end = points[0][1]
    for s, e in points[1:]:
        if s > end:
            arrows += 1
            end = e
    return arrows

Merge Intervals MEDIUM

def merge_intervals_greedy(intervals):
    intervals.sort()
    out = []
    for s, e in intervals:
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

Hand of Straights MEDIUM

def is_n_straight_hand(hand, group_size):
    from collections import Counter
    if len(hand) % group_size != 0:
        return False
    count = Counter(hand)
    for card in sorted(count):
        if count[card] > 0:
            need = count[card]
            for k in range(card, card + group_size):
                if count[k] < need:
                    return False
                count[k] -= need
    return True

Minimum Increments to Make Array Unique MEDIUM

def min_increment_for_unique(nums):
    nums.sort()
    moves = 0
    for i in range(1, len(nums)):
        if nums[i] <= nums[i - 1]:
            need = nums[i - 1] + 1
            moves += need - nums[i]
            nums[i] = need
    return moves

Candy HARD

def candy_greedy(ratings):
    n = len(ratings)
    give = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            give[i] = give[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            give[i] = max(give[i], give[i + 1] + 1)
    return sum(give)

Remove K Digits HARD

def remove_k_digits(num, k):
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop(); k -= 1
        stack.append(d)
    stack = stack[:len(stack) - k] if k else stack
    return ''.join(stack).lstrip('0') or '0'

Reorganize String HARD

def reorganize_string(s):
    import heapq
    from collections import Counter
    heap = [(-c, ch) for ch, c in Counter(s).items()]
    heapq.heapify(heap)
    prev = None
    out = []
    while heap:
        cnt, ch = heapq.heappop(heap)
        out.append(ch)
        if prev and prev[0] < 0:
            heapq.heappush(heap, prev)
        prev = (cnt + 1, ch)
    result = ''.join(out)
    return result if len(result) == len(s) else ''

IPO (Maximize Capital) HARD

def find_maximized_capital_greedy(k, w, profits, capital):
    import heapq
    projects = sorted(zip(capital, profits))
    heap = []
    i = 0
    for _ in range(k):
        while i < len(projects) and projects[i][0] <= w:
            heapq.heappush(heap, -projects[i][1])
            i += 1
        if not heap:
            break
        w += -heapq.heappop(heap)
    return w

Minimum Taps to Water a Garden HARD

def min_taps(n, ranges):
    reach = [0] * (n + 1)
    for i, r in enumerate(ranges):
        left = max(0, i - r)
        reach[left] = max(reach[left], i + r)
    taps = end = farthest = 0
    for i in range(n):
        farthest = max(farthest, reach[i])
        if i == end:
            if farthest <= i:
                return -1
            taps += 1
            end = farthest
    return taps

Video Stitching HARD

def video_stitching(clips, time):
    reach = [0] * (time + 1)
    for s, e in clips:
        if s <= time:
            reach[s] = max(reach[s], e)
    count = end = farthest = 0
    for i in range(time):
        farthest = max(farthest, reach[i])
        if i == end:
            if farthest <= i:
                return -1
            count += 1
            end = farthest
    return count

Two City Scheduling HARD

def two_city_sched_cost(costs):
    costs.sort(key=lambda c: c[0] - c[1])
    n = len(costs) // 2
    return sum(c[0] for c in costs[:n]) + sum(c[1] for c in costs[n:])

Connect Sticks at Minimum Cost HARD

def connect_sticks(sticks):
    import heapq
    heapq.heapify(sticks)
    total = 0
    while len(sticks) > 1:
        a = heapq.heappop(sticks)
        b = heapq.heappop(sticks)
        total += a + b
        heapq.heappush(sticks, a + b)
    return total

Car Fleet HARD

def car_fleet(target, position, speed):
    pairs = sorted(zip(position, speed), reverse=True)
    fleets = 0
    cur = 0.0
    for pos, spd in pairs:
        time = (target - pos) / spd
        if time > cur:
            fleets += 1
            cur = time
    return fleets

Bag of Tokens HARD

def bag_of_tokens_score(tokens, power):
    tokens.sort()
    lo, hi = 0, len(tokens) - 1
    score = best = 0
    while lo <= hi:
        if power >= tokens[lo]:
            power -= tokens[lo]
            score += 1
            best = max(best, score)
            lo += 1
        elif score > 0:
            power += tokens[hi]
            score -= 1
            hi -= 1
        else:
            break
    return best

Data Structures & Design

Min Stack EASY

class MinStack:
    def __init__(self):
        self.stack = []
        self.mins = []
    def push(self, x):
        self.stack.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))
    def pop(self):
        self.mins.pop()
        return self.stack.pop()
    def top(self):
        return self.stack[-1]
    def getMin(self):
        return self.mins[-1]

def min_stack_ops(ops):
    obj = MinStack()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] in ('top', 'getMin') else None)
    return out

Queue Using Two Stacks EASY

class MyQueue:
    def __init__(self):
        self.a = []
        self.b = []
    def push(self, x):
        self.a.append(x)
    def _shift(self):
        if not self.b:
            while self.a:
                self.b.append(self.a.pop())
    def pop(self):
        self._shift()
        return self.b.pop()
    def peek(self):
        self._shift()
        return self.b[-1]
    def empty(self):
        return not self.a and not self.b

def queue_using_stacks(ops):
    obj = MyQueue()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] in ('pop', 'peek', 'empty') else None)
    return out

Stack Using Two Queues EASY

from collections import deque
class MyStack:
    def __init__(self):
        self.q = deque()
    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
    def pop(self):
        return self.q.popleft()
    def top(self):
        return self.q[0]
    def empty(self):
        return not self.q

def stack_using_queues(ops):
    obj = MyStack()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] in ('pop', 'top', 'empty') else None)
    return out

Moving Average From Data Stream EASY

from collections import deque
def moving_average(size, values):
    window = deque()
    total = 0
    out = []
    for v in values:
        window.append(v)
        total += v
        if len(window) > size:
            total -= window.popleft()
        out.append(total / len(window))
    return out

Design HashSet EASY

class MyHashSet:
    def __init__(self):
        self.buckets = [[] for _ in range(769)]
    def _b(self, key):
        return self.buckets[key % 769]
    def add(self, key):
        b = self._b(key)
        if key not in b:
            b.append(key)
    def remove(self, key):
        b = self._b(key)
        if key in b:
            b.remove(key)
    def contains(self, key):
        return key in self._b(key)

def design_hashset(ops):
    obj = MyHashSet()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'contains' else None)
    return out

Design HashMap EASY

class MyHashMap:
    def __init__(self):
        self.buckets = [[] for _ in range(769)]
    def _b(self, key):
        return self.buckets[key % 769]
    def put(self, key, value):
        b = self._b(key)
        for i, (k, v) in enumerate(b):
            if k == key:
                b[i] = (key, value)
                return
        b.append((key, value))
    def get(self, key):
        for k, v in self._b(key):
            if k == key:
                return v
        return -1
    def remove(self, key):
        b = self._b(key)
        for i, (k, v) in enumerate(b):
            if k == key:
                b.pop(i)
                return

def design_hashmap(ops):
    obj = MyHashMap()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'get' else None)
    return out

Logger Rate Limiter EASY

def logger_rate_limiter(logs):
    last = {}
    out = []
    for ts, msg in logs:
        if msg not in last or ts - last[msg] >= 10:
            last[msg] = ts
            out.append(True)
        else:
            out.append(False)
    return out

Range Sum Query (Immutable) EASY

def range_sum_immutable(nums, queries):
    prefix = [0]
    for n in nums:
        prefix.append(prefix[-1] + n)
    return [prefix[j + 1] - prefix[i] for i, j in queries]

Design Parking System EASY

def parking_system(slots, cars):
    remaining = {1: slots[0], 2: slots[1], 3: slots[2]}
    out = []
    for car in cars:
        if remaining[car] > 0:
            remaining[car] -= 1
            out.append(True)
        else:
            out.append(False)
    return out

Number of Recent Calls EASY

from collections import deque
def recent_counter(pings):
    window = deque()
    out = []
    for t in pings:
        window.append(t)
        while window[0] < t - 3000:
            window.popleft()
        out.append(len(window))
    return out

BST Construction MEDIUM

class BST:
    def __init__(self, value):
        self.value = value; self.left = None; self.right = None
    def insert(self, value):
        node = self
        while True:
            if value < node.value:
                if node.left is None: node.left = BST(value); break
                node = node.left
            else:
                if node.right is None: node.right = BST(value); break
                node = node.right
        return self
    def contains(self, value):
        node = self
        while node:
            if value < node.value: node = node.left
            elif value > node.value: node = node.right
            else: return True
        return False

Min Heap (with Python's heapq) MEDIUM

import heapq
nums = [5, 2, 8, 1]
heapq.heapify(nums)         # O(n) -> smallest is always nums[0]
heapq.heappush(nums, 3)     # O(log n)
smallest = heapq.heappop(nums)   # remove + return the min, O(log n)
# Max-heap trick: push/pop the NEGATIVE of each value

Suffix Trie Construction MEDIUM

class SuffixTrie:
    def __init__(self, string):
        self.root = {}; self.end = "*"
        for i in range(len(string)):
            self._insert(string[i:])
    def _insert(self, s):
        node = self.root
        for ch in s: node = node.setdefault(ch, {})
        node[self.end] = True
    def contains(self, s):
        node = self.root
        for ch in s:
            if ch not in node: return False
            node = node[ch]
        return self.end in node

LRU Cache MEDIUM

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.cap = capacity
    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.cap:
            self.cache.popitem(last=False)

def lru_cache_ops(capacity, ops):
    obj = LRUCache(capacity)
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'get' else None)
    return out

Design Circular Queue MEDIUM

class MyCircularQueue:
    def __init__(self, k):
        self.q = [0] * k
        self.head = 0
        self.count = 0
        self.cap = k
    def enQueue(self, v):
        if self.count == self.cap:
            return False
        self.q[(self.head + self.count) % self.cap] = v
        self.count += 1
        return True
    def deQueue(self):
        if self.count == 0:
            return False
        self.head = (self.head + 1) % self.cap
        self.count -= 1
        return True
    def Front(self):
        return -1 if self.count == 0 else self.q[self.head]
    def Rear(self):
        return -1 if self.count == 0 else self.q[(self.head + self.count - 1) % self.cap]
    def isEmpty(self):
        return self.count == 0
    def isFull(self):
        return self.count == self.cap

def circular_queue_ops(k, ops):
    obj = MyCircularQueue(k)
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r)
    return out

Time-Based Key-Value Store MEDIUM

import bisect
class TimeMap:
    def __init__(self):
        self.store = {}
    def set(self, key, value, timestamp):
        self.store.setdefault(key, []).append((timestamp, value))
    def get(self, key, timestamp):
        arr = self.store.get(key, [])
        i = bisect.bisect_right(arr, (timestamp, chr(127)))
        return arr[i - 1][1] if i else ''

def time_map_ops(ops):
    obj = TimeMap()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'get' else None)
    return out

Design Underground System MEDIUM

class UndergroundSystem:
    def __init__(self):
        self.checkins = {}
        self.totals = {}
    def checkIn(self, uid, station, t):
        self.checkins[uid] = (station, t)
    def checkOut(self, uid, station, t):
        start, t0 = self.checkins.pop(uid)
        key = (start, station)
        total, count = self.totals.get(key, (0, 0))
        self.totals[key] = (total + (t - t0), count + 1)
    def getAverageTime(self, start, end):
        total, count = self.totals[(start, end)]
        return total / count

def underground_system(ops):
    obj = UndergroundSystem()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'getAverageTime' else None)
    return out

Design Browser History MEDIUM

class BrowserHistory:
    def __init__(self, homepage):
        self.history = [homepage]
        self.cur = 0
    def visit(self, url):
        del self.history[self.cur + 1:]
        self.history.append(url)
        self.cur += 1
    def back(self, steps):
        self.cur = max(0, self.cur - steps)
        return self.history[self.cur]
    def forward(self, steps):
        self.cur = min(len(self.history) - 1, self.cur + steps)
        return self.history[self.cur]

def browser_history(homepage, ops):
    obj = BrowserHistory(homepage)
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] in ('back', 'forward') else None)
    return out

Online Stock Span MEDIUM

def stock_spanner(prices):
    stack = []
    out = []
    for price in prices:
        span = 1
        while stack and stack[-1][0] <= price:
            span += stack.pop()[1]
        stack.append((price, span))
        out.append(span)
    return out

Design Front Middle Back Queue MEDIUM

from collections import deque
class FrontMiddleBack:
    def __init__(self):
        self.left = deque()
        self.right = deque()
    def _balance(self):
        if len(self.left) > len(self.right):
            self.right.appendleft(self.left.pop())
        elif len(self.right) > len(self.left) + 1:
            self.left.append(self.right.popleft())
    def pushFront(self, val):
        self.left.appendleft(val); self._balance()
    def pushMiddle(self, val):
        if len(self.left) < len(self.right):
            self.left.append(val)
        else:
            self.right.appendleft(val)
        self._balance()
    def pushBack(self, val):
        self.right.append(val); self._balance()
    def popFront(self):
        if not self.left and not self.right:
            return -1
        val = self.left.popleft() if self.left else self.right.popleft()
        self._balance()
        return val
    def popMiddle(self):
        if not self.left and not self.right:
            return -1
        if len(self.left) == len(self.right):
            val = self.left.pop()
        else:
            val = self.right.popleft()
        self._balance()
        return val
    def popBack(self):
        if not self.right and not self.left:
            return -1
        val = self.right.pop() if self.right else self.left.pop()
        self._balance()
        return val

def front_middle_back_ops(ops):
    obj = FrontMiddleBack()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0].startswith('pop') else None)
    return out

My Calendar I MEDIUM

def my_calendar(bookings):
    booked = []
    out = []
    for start, end in bookings:
        ok = all(end <= s or start >= e for s, e in booked)
        if ok:
            booked.append((start, end))
        out.append(ok)
    return out

Range Sum Query (Mutable) MEDIUM

class NumArray:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (self.n + 1)
        self.nums = [0] * self.n
        for i, v in enumerate(nums):
            self.update(i, v)
    def update(self, i, val):
        delta = val - self.nums[i]
        self.nums[i] = val
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)
    def _prefix(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
    def sumRange(self, i, j):
        return self._prefix(j + 1) - self._prefix(i)

def range_sum_mutable(nums, ops):
    obj = NumArray(nums)
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'sumRange' else None)
    return out

Design Circular Deque MEDIUM

class MyCircularDeque:
    def __init__(self, k):
        self.q = [0] * k
        self.head = 0
        self.count = 0
        self.cap = k
    def insertFront(self, v):
        if self.count == self.cap:
            return False
        self.head = (self.head - 1) % self.cap
        self.q[self.head] = v
        self.count += 1
        return True
    def insertLast(self, v):
        if self.count == self.cap:
            return False
        self.q[(self.head + self.count) % self.cap] = v
        self.count += 1
        return True
    def deleteFront(self):
        if self.count == 0:
            return False
        self.head = (self.head + 1) % self.cap
        self.count -= 1
        return True
    def deleteLast(self):
        if self.count == 0:
            return False
        self.count -= 1
        return True
    def getFront(self):
        return -1 if self.count == 0 else self.q[self.head]
    def getRear(self):
        return -1 if self.count == 0 else self.q[(self.head + self.count - 1) % self.cap]
    def isEmpty(self):
        return self.count == 0
    def isFull(self):
        return self.count == self.cap

def circular_deque_ops(k, ops):
    obj = MyCircularDeque(k)
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r)
    return out

LRU Cache HARD

Get/put in O(1), evicting the least-recently-used item. An OrderedDict does the heavy lifting.

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict(); self.capacity = capacity
    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)         # mark most-recently-used
        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)  # evict least-recently-used

Knuth-Morris-Pratt (string search) HARD

Find a pattern in text in O(n+m) using a precomputed "failure" table.

class Solution:
    def kmp_search(self, text, pattern):
        lps = [0] * len(pattern)          # longest prefix = suffix table
        k = 0
        for i in range(1, len(pattern)):
            while k > 0 and pattern[i] != pattern[k]: k = lps[k-1]
            if pattern[i] == pattern[k]: k += 1
            lps[i] = k
        j = 0
        for i in range(len(text)):
            while j > 0 and text[i] != pattern[j]: j = lps[j-1]
            if text[i] == pattern[j]: j += 1
            if j == len(pattern): return i - j + 1   # start index of match
        return -1

LFU Cache HARD

from collections import defaultdict, OrderedDict
class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.vals = {}
        self.freq = {}
        self.groups = defaultdict(OrderedDict)
        self.min_freq = 0
    def _bump(self, key):
        f = self.freq[key]
        del self.groups[f][key]
        if not self.groups[f]:
            del self.groups[f]
            if self.min_freq == f:
                self.min_freq += 1
        self.freq[key] = f + 1
        self.groups[f + 1][key] = None
    def get(self, key):
        if key not in self.vals:
            return -1
        self._bump(key)
        return self.vals[key]
    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._bump(key)
            return
        if len(self.vals) >= self.cap:
            evict, _ = self.groups[self.min_freq].popitem(last=False)
            del self.vals[evict]
            del self.freq[evict]
        self.vals[key] = value
        self.freq[key] = 1
        self.groups[1][key] = None
        self.min_freq = 1

def lfu_cache_ops(capacity, ops):
    obj = LFUCache(capacity)
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'get' else None)
    return out

Find Median From Data Stream HARD

import heapq
class MedianFinder:
    def __init__(self):
        self.low = []
        self.high = []
    def addNum(self, num):
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))
    def findMedian(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

def median_finder_ops(ops):
    obj = MedianFinder()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'findMedian' else None)
    return out

Add and Search Word (Wildcards) HARD

class WordDictionary:
    def __init__(self):
        self.root = {}
    def addWord(self, word):
        node = self.root
        for c in word:
            node = node.setdefault(c, {})
        node['$'] = True
    def search(self, word):
        def dfs(node, i):
            if i == len(word):
                return '$' in node
            c = word[i]
            if c == '.':
                return any(dfs(child, i + 1) for k, child in node.items() if k != '$')
            return c in node and dfs(node[c], i + 1)
        return dfs(self.root, 0)

def word_dictionary_ops(ops):
    obj = WordDictionary()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'search' else None)
    return out

My Calendar II (No Triple Booking) HARD

def my_calendar_ii(bookings):
    booked = []
    overlaps = []
    out = []
    for start, end in bookings:
        if any(start < e and s < end for s, e in overlaps):
            out.append(False)
            continue
        for s, e in booked:
            if start < e and s < end:
                overlaps.append((max(start, s), min(end, e)))
        booked.append((start, end))
        out.append(True)
    return out

My Calendar III (Max K-Booking) HARD

from collections import defaultdict
def my_calendar_iii(bookings):
    delta = defaultdict(int)
    out = []
    for start, end in bookings:
        delta[start] += 1
        delta[end] -= 1
        active = 0
        best = 0
        for t in sorted(delta):
            active += delta[t]
            best = max(best, active)
        out.append(best)
    return out

Snapshot Array HARD

import bisect
class SnapshotArray:
    def __init__(self, length):
        self.snap_id = 0
        self.history = [[(-1, 0)] for _ in range(length)]
    def set(self, index, val):
        self.history[index].append((self.snap_id, val))
    def snap(self):
        self.snap_id += 1
        return self.snap_id - 1
    def get(self, index, snap_id):
        arr = self.history[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

def snapshot_array_ops(length, ops):
    obj = SnapshotArray(length)
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] in ('snap', 'get') else None)
    return out

Stock Price Fluctuation HARD

import heapq
class StockPrice:
    def __init__(self):
        self.prices = {}
        self.latest = 0
        self.max_heap = []
        self.min_heap = []
    def update(self, timestamp, price):
        self.prices[timestamp] = price
        self.latest = max(self.latest, timestamp)
        heapq.heappush(self.max_heap, (-price, timestamp))
        heapq.heappush(self.min_heap, (price, timestamp))
    def current(self):
        return self.prices[self.latest]
    def maximum(self):
        while -self.max_heap[0][0] != self.prices[self.max_heap[0][1]]:
            heapq.heappop(self.max_heap)
        return -self.max_heap[0][0]
    def minimum(self):
        while self.min_heap[0][0] != self.prices[self.min_heap[0][1]]:
            heapq.heappop(self.min_heap)
        return self.min_heap[0][0]

def stock_price_ops(ops):
    obj = StockPrice()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] in ('current', 'maximum', 'minimum') else None)
    return out

Range Module HARD

import bisect
class RangeModule:
    def __init__(self):
        self.ranges = []
    def addRange(self, left, right):
        i = bisect.bisect_left(self.ranges, left)
        j = bisect.bisect_right(self.ranges, right)
        merged = []
        if i % 2 == 0:
            merged.append(left)
        if j % 2 == 0:
            merged.append(right)
        self.ranges[i:j] = merged
    def queryRange(self, left, right):
        i = bisect.bisect_right(self.ranges, left)
        j = bisect.bisect_left(self.ranges, right)
        return i == j and i % 2 == 1
    def removeRange(self, left, right):
        i = bisect.bisect_left(self.ranges, left)
        j = bisect.bisect_right(self.ranges, right)
        merged = []
        if i % 2 == 1:
            merged.append(left)
        if j % 2 == 1:
            merged.append(right)
        self.ranges[i:j] = merged

def range_module_ops(ops):
    obj = RangeModule()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'queryRange' else None)
    return out

Maximum Frequency Stack HARD

from collections import defaultdict
class FreqStack:
    def __init__(self):
        self.freq = defaultdict(int)
        self.groups = defaultdict(list)
        self.max_freq = 0
    def push(self, val):
        self.freq[val] += 1
        f = self.freq[val]
        self.max_freq = max(self.max_freq, f)
        self.groups[f].append(val)
    def pop(self):
        val = self.groups[self.max_freq].pop()
        self.freq[val] -= 1
        if not self.groups[self.max_freq]:
            self.max_freq -= 1
        return val

def freq_stack_ops(ops):
    obj = FreqStack()
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'pop' else None)
    return out

Authentication Manager HARD

class AuthenticationManager:
    def __init__(self, ttl):
        self.ttl = ttl
        self.tokens = {}
    def generate(self, token_id, current_time):
        self.tokens[token_id] = current_time + self.ttl
    def renew(self, token_id, current_time):
        if token_id in self.tokens and self.tokens[token_id] > current_time:
            self.tokens[token_id] = current_time + self.ttl
    def countUnexpiredTokens(self, current_time):
        return sum(1 for exp in self.tokens.values() if exp > current_time)

def authentication_manager_ops(ttl, ops):
    obj = AuthenticationManager(ttl)
    out = []
    for op in ops:
        r = getattr(obj, op[0])(*op[1:])
        out.append(r if op[0] == 'countUnexpiredTokens' else None)
    return out

Java

Binary Search (Java) EASY

Iterative binary search with the overflow-safe midpoint. O(log n) time, O(1) space.

public static int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // avoids (lo+hi) overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else                   hi = mid - 1;
    }
    return -1;                             // not found
}

Reverse an Array In Place (Java) EASY

    static void reverse(int[] a) {
        int lo = 0, hi = a.length - 1;
        while (lo < hi) {
            int tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
            lo++; hi--;
        }
    }

FizzBuzz (Java) EASY

    static List<String> fizzBuzz(int n) {
        List<String> res = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) res.add("FizzBuzz");
            else if (i % 3 == 0) res.add("Fizz");
            else if (i % 5 == 0) res.add("Buzz");
            else res.add(String.valueOf(i));
        }
        return res;
    }

Find Maximum in an Array (Java) EASY

    static int findMax(int[] a) {
        int max = a[0];
        for (int x : a) max = Math.max(max, x);
        return max;
    }

Sum of an Array (Java) EASY

    static long arraySum(int[] a) {
        long sum = 0;
        for (int x : a) sum += x;
        return sum;
    }

Palindrome Check (Java) EASY

    static boolean isPalindrome(String s) {
        int lo = 0, hi = s.length() - 1;
        while (lo < hi) {
            if (s.charAt(lo) != s.charAt(hi)) return false;
            lo++; hi--;
        }
        return true;
    }

Count Vowels (Java) EASY

    static int countVowels(String s) {
        int count = 0;
        String vowels = "aeiouAEIOU";
        for (char c : s.toCharArray())
            if (vowels.indexOf(c) >= 0) count++;
        return count;
    }

Factorial (Java) EASY

    static long factorial(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) result *= i;
        return result;
    }

Greatest Common Divisor (Java) EASY

    static int gcd(int a, int b) {
        while (b != 0) {
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }

Linear Search (Java) EASY

    static int linearSearch(int[] a, int target) {
        for (int i = 0; i < a.length; i++)
            if (a[i] == target) return i;
        return -1;
    }

Bubble Sort (Java) EASY

    static void bubbleSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp;
                    swapped = true;
                }
            }
            if (!swapped) break;
        }
    }

Breadth-First Search (Java) MEDIUM

Queue-based BFS over an adjacency map. Mark nodes seen at enqueue time so cycles can't loop. O(V+E).

import java.util.*;

public static List<Integer> bfs(Map<Integer, List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    Set<Integer> seen  = new HashSet<>();
    Queue<Integer> queue = new LinkedList<>();
    queue.add(start); seen.add(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        order.add(node);
        for (int next : graph.getOrDefault(node, List.of())) {
            if (!seen.contains(next)) {    // seen-before-enqueue stops cycles
                seen.add(next);
                queue.add(next);
            }
        }
    }
    return order;
}

Longest Common Subsequence (Java) MEDIUM

Bottom-up DP - the plagiarism-detector algorithm in Java. O(n·m) time and space.

public static int lcs(String a, String b) {
    int n = a.length(), m = b.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1))
                dp[i][j] = 1 + dp[i - 1][j - 1];
            else
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}

Two Sum (Java) MEDIUM

    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) return new int[]{seen.get(need), i};
            seen.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

Merge Two Sorted Arrays (Java) MEDIUM

    static int[] merge(int[] a, int[] b) {
        int[] res = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length)
            res[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
        while (i < a.length) res[k++] = a[i++];
        while (j < b.length) res[k++] = b[j++];
        return res;
    }

Valid Parentheses (Java) MEDIUM

    static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
        for (char c : s.toCharArray()) {
            if (pairs.containsKey(c)) {
                if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }

First Unique Character (Java) MEDIUM

    static int firstUniqChar(String s) {
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray())
            count.merge(c, 1, Integer::sum);
        for (int i = 0; i < s.length(); i++)
            if (count.get(s.charAt(i)) == 1) return i;
        return -1;
    }

Move Zeroes (Java) MEDIUM

    static void moveZeroes(int[] nums) {
        int insert = 0;
        for (int n : nums)
            if (n != 0) nums[insert++] = n;
        while (insert < nums.length) nums[insert++] = 0;
    }

Rotate Array (Java) MEDIUM

    static void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }
    static void reverse(int[] a, int lo, int hi) {
        while (lo < hi) {
            int tmp = a[lo]; a[lo] = a[hi]; a[hi] = tmp;
            lo++; hi--;
        }
    }

Maximum Subarray - Kadane (Java) MEDIUM

    static int maxSubArray(int[] nums) {
        int best = nums[0], current = nums[0];
        for (int i = 1; i < nums.length; i++) {
            current = Math.max(nums[i], current + nums[i]);
            best = Math.max(best, current);
        }
        return best;
    }

Group Anagrams (Java) MEDIUM

    static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());
    }

Quicksort (Java) MEDIUM

    static void quickSort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = a[hi], i = lo;
        for (int j = lo; j < hi; j++) {
            if (a[j] < pivot) {
                int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
                i++;
            }
        }
        int tmp = a[i]; a[i] = a[hi]; a[hi] = tmp;
        quickSort(a, lo, i - 1);
        quickSort(a, i + 1, hi);
    }

Merge Sort (Java) MEDIUM

    static int[] mergeSort(int[] a) {
        if (a.length <= 1) return a;
        int mid = a.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
        int[] res = new int[a.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length)
            res[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
        while (i < left.length) res[k++] = left[i++];
        while (j < right.length) res[k++] = right[j++];
        return res;
    }

Edit Distance (Java) HARD

Levenshtein distance, bottom-up. O(n·m).

public static int editDistance(String a, String b) {
    int n = a.length(), m = b.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = i;   // delete all of a[:i]
    for (int j = 0; j <= m; j++) dp[0][j] = j;   // insert all of b[:j]

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                              Math.min(dp[i - 1][j], dp[i][j - 1]));
        }
    }
    return dp[n][m];
}

OOP Design - Cloud E-Reader (Java) HARD

The same design as the Python version, in idiomatic Java with a HashMap collection.

import java.util.*;

class Book {
    int id; String title; List<String> content; int lastPage = 0;
    Book(int id, String title, List<String> content) {
        this.id = id; this.title = title; this.content = content;
    }
    String displayPage() { return content.get(lastPage); }
    String turnPage() {
        if (lastPage < content.size() - 1) lastPage++;
        return displayPage();
    }
}

class Library {
    private Map<Integer, Book> collection = new HashMap<>();
    private Integer activeId = null;
    private int nextId = 0;

    int addBook(String title, List<String> content) {
        Book b = new Book(nextId++, title, content);
        collection.put(b.id, b);
        return b.id;
    }
    void removeBook(int id) {
        collection.remove(id);
        if (activeId != null && activeId == id) activeId = null;
    }
    void setActive(int id) { if (collection.containsKey(id)) activeId = id; }
    String displayPage() { return activeId == null ? null : collection.get(activeId).displayPage(); }
    String turnPage()    { return activeId == null ? null : collection.get(activeId).turnPage(); }
}

Dijkstra's Shortest Path (Java) HARD

    static int[] dijkstra(int[][] graph, int src) {
        int n = graph.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        boolean[] done = new boolean[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.add(new int[]{src, 0});
        while (!pq.isEmpty()) {
            int u = pq.poll()[0];
            if (done[u]) continue;
            done[u] = true;
            for (int v = 0; v < n; v++) {
                if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    pq.add(new int[]{v, dist[v]});
                }
            }
        }
        return dist;
    }

LRU Cache (Java) HARD

    static class LRUCache {
        private final int cap;
        private final LinkedHashMap<Integer, Integer> map;
        LRUCache(int capacity) {
            cap = capacity;
            map = new LinkedHashMap<>(16, 0.75f, true) {
                protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
                    return size() > cap;
                }
            };
        }
        int get(int key) { return map.getOrDefault(key, -1); }
        void put(int key, int value) { map.put(key, value); }
    }

Trie (Prefix Tree) (Java) HARD

    static class Trie {
        private final Trie[] children = new Trie[26];
        private boolean isEnd;
        void insert(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                if (node.children[i] == null) node.children[i] = new Trie();
                node = node.children[i];
            }
            node.isEnd = true;
        }
        boolean search(String word) {
            Trie node = find(word);
            return node != null && node.isEnd;
        }
        boolean startsWith(String prefix) { return find(prefix) != null; }
        private Trie find(String word) {
            Trie node = this;
            for (char c : word.toCharArray()) {
                int i = c - 'a';
                if (node.children[i] == null) return null;
                node = node.children[i];
            }
            return node;
        }
    }

Topological Sort - Kahn's (Java) HARD

    static int[] topologicalSort(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] indegree = new int[n];
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            indegree[e[1]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) if (indegree[i] == 0) queue.add(i);
        int[] order = new int[n];
        int idx = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            order[idx++] = u;
            for (int v : adj.get(u))
                if (--indegree[v] == 0) queue.add(v);
        }
        return order;
    }

0/1 Knapsack (Java) HARD

    static int knapsack(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < weights.length; i++)
            for (int w = capacity; w >= weights[i]; w--)
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        return dp[capacity];
    }

Longest Increasing Subsequence (Java) HARD

    static int lengthOfLIS(int[] nums) {
        List<Integer> tails = new ArrayList<>();
        for (int x : nums) {
            int lo = 0, hi = tails.size();
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if (tails.get(mid) < x) lo = mid + 1;
                else hi = mid;
            }
            if (lo == tails.size()) tails.add(x);
            else tails.set(lo, x);
        }
        return tails.size();
    }

Median of Two Sorted Arrays (Java) HARD

    static double findMedianSortedArrays(int[] A, int[] B) {
        if (A.length > B.length) { int[] t = A; A = B; B = t; }
        int m = A.length, n = B.length, lo = 0, hi = m, half = (m + n + 1) / 2;
        while (lo <= hi) {
            int i = (lo + hi) / 2, j = half - i;
            int aL = i == 0 ? Integer.MIN_VALUE : A[i - 1];
            int aR = i == m ? Integer.MAX_VALUE : A[i];
            int bL = j == 0 ? Integer.MIN_VALUE : B[j - 1];
            int bR = j == n ? Integer.MAX_VALUE : B[j];
            if (aL <= bR && bL <= aR) {
                if (((m + n) & 1) == 1) return Math.max(aL, bL);
                return (Math.max(aL, bL) + Math.min(aR, bR)) / 2.0;
            } else if (aL > bR) hi = i - 1;
            else lo = i + 1;
        }
        return 0.0;
    }

N-Queens (Count) (Java) HARD

    static int totalNQueens(int n) {
        return solve(0, 0, 0, 0, n);
    }
    static int solve(int row, int cols, int d1, int d2, int n) {
        if (row == n) return 1;
        int count = 0;
        int available = ((1 << n) - 1) & ~(cols | d1 | d2);
        while (available != 0) {
            int p = available & (-available);
            available -= p;
            count += solve(row + 1, cols | p, (d1 | p) << 1, (d2 | p) >> 1, n);
        }
        return count;
    }

Coin Change (Java) HARD

    static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int c : coins)
            for (int a = c; a <= amount; a++)
                dp[a] = Math.min(dp[a], dp[a - c] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }

Union-Find / Disjoint Set (Java) HARD

    static class UnionFind {
        private final int[] parent, rank;
        private int count;
        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            count = n;
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        void union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return;
            if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
            parent[rb] = ra;
            if (rank[ra] == rank[rb]) rank[ra]++;
            count--;
        }
        int count() { return count; }
    }

Real-world & On-the-job

API + JSON - revenue by product EASY

Integration roles live on this: call a REST endpoint that returns a JSON list of orders and aggregate revenue per product, highest first. Standard library only - no external packages.

import json, urllib.request
from collections import defaultdict

def revenue_by_product(url):
    with urllib.request.urlopen(url, timeout=10) as resp:
        orders = json.load(resp)        # [{"product": "...", "price": 9.99, "qty": 2}, ...]

    totals = defaultdict(float)
    for o in orders:
        totals[o["product"]] += o["price"] * o["qty"]

    # highest-grossing first
    return sorted(totals.items(), key=lambda kv: kv[1], reverse=True)

SQL - group, filter & rank customers EASY

From Orders(id, customer_id, amount), list customers with more than 3 orders plus their total spend, biggest spenders first. Tests GROUP BY / HAVING / ORDER BY.

SELECT customer_id,
       COUNT(*)    AS order_count,
       SUM(amount) AS total_spent
FROM   Orders
GROUP BY customer_id
HAVING COUNT(*) > 3
ORDER BY total_spent DESC;

Unit testing / TDD EASY

Every listing wants tests, code reviews and Agile. Given is_valid_email, write tests that cover the happy path and the edge cases (missing @, empty, double @). Interviewers love when you test before you trust the code.

import unittest

def is_valid_email(s):
    return s.count("@") == 1 and "." in s.split("@")[1]

class TestEmail(unittest.TestCase):
    def test_valid(self):    self.assertTrue(is_valid_email("[email protected]"))
    def test_no_at(self):    self.assertFalse(is_valid_email("abc.com"))
    def test_empty(self):    self.assertFalse(is_valid_email(""))
    def test_two_ats(self):  self.assertFalse(is_valid_email("a@@b.com"))

if __name__ == "__main__":
    unittest.main()

Parse a Query String EASY

def parse_query_string(qs):
    result = {}
    if not qs:
        return result
    for pair in qs.split('&'):
        if '=' in pair:
            key, value = pair.split('=', 1)
            result[key] = value
        else:
            result[pair] = ''
    return result

Convert camelCase to snake_case EASY

def to_snake_case(s):
    result = []
    for c in s:
        if c.isupper():
            result.append('_')
            result.append(c.lower())
        else:
            result.append(c)
    return ''.join(result)

Convert snake_case to camelCase EASY

def to_camel_case(s):
    parts = s.split('_')
    return parts[0] + ''.join(word.capitalize() for word in parts[1:])

Format Cents as Currency EASY

def format_currency(cents):
    dollars = cents / 100
    return '${:,.2f}'.format(dollars)

Truncate Text With Ellipsis EASY

def truncate_text(text, max_len):
    if len(text) <= max_len:
        return text
    return text[:max_len] + '...'

Slugify a Title EASY

def slugify(title):
    out = []
    for c in title.lower():
        if c.isalnum():
            out.append(c)
        elif c in ' -_':
            out.append('-')
    slug = ''.join(out)
    while '--' in slug:
        slug = slug.replace('--', '-')
    return slug.strip('-')

Count Words in Text EASY

def count_words(text):
    return len(text.split())

Validate an Email Address EASY

def validate_email(email):
    if email.count('@') != 1:
        return False
    local, domain = email.split('@')
    if not local or not domain:
        return False
    return '.' in domain and not domain.startswith('.') and not domain.endswith('.')

Mask a Credit Card Number EASY

def mask_credit_card(number):
    digits = number.replace(' ', '').replace('-', '')
    if len(digits) <= 4:
        return digits
    return '*' * (len(digits) - 4) + digits[-4:]

Celsius to Fahrenheit EASY

def celsius_to_fahrenheit(c):
    return round(c * 9 / 5 + 32, 1)

Plagiarism Detector - Longest Common Subsequence MEDIUM

To flag plagiarism between two stories, find the length of their longest shared subsequence of characters (same order, but gaps allowed). The naive "try every substring" approach is exponential; memoized recursion is O(n·m). Then run it over every pair of books to surface the most-likely match.

from functools import lru_cache

def longest_common_subsequence(a, b):
    @lru_cache(maxsize=None)
    def lcs(i, j):
        if i == len(a) or j == len(b):
            return 0
        if a[i] == b[j]:
            return 1 + lcs(i + 1, j + 1)            # match -> advance both
        return max(lcs(i + 1, j), lcs(i, j + 1))    # else skip one side
    return lcs(0, 0)

def most_likely_plagiarism(books):                  # books: list[(title, text)]
    best = (0, None, None)
    for i in range(len(books)):
        for j in range(i + 1, len(books)):
            score = longest_common_subsequence(books[i][1], books[j][1])
            if score > best[0]:
                best = (score, books[i][0], books[j][0])
    return best                                     # (shared_chars, titleA, titleB)

SQL - second-highest salary MEDIUM

SQL was the single most-requested hard skill across the listings. From Employee(id, name, salary), return the second-highest distinct salary (return NULL if there isn't one). Know both the sub-query and the window-function answer.

-- Classic sub-query
SELECT MAX(salary) AS second_highest
FROM   Employee
WHERE  salary < (SELECT MAX(salary) FROM Employee);

-- Modern, scales to "Nth highest" (window function)
SELECT DISTINCT salary AS second_highest
FROM (
    SELECT salary,
           DENSE_RANK() OVER (ORDER BY salary DESC) AS rnk
    FROM   Employee
) ranked
WHERE rnk = 2;

SQL - top earner per department MEDIUM

Join + correlated sub-query, a daily-driver pattern for data roles. List each department and the employee(s) earning the most within that department.

SELECT d.name AS department,
       e.name AS employee,
       e.salary
FROM   Employee  e
JOIN   Department d ON e.dept_id = d.id
WHERE  e.salary = (
    SELECT MAX(e2.salary)
    FROM   Employee e2
    WHERE  e2.dept_id = e.dept_id
)
ORDER BY d.name;

Parse a CSV Line With Quotes MEDIUM

def parse_csv_line(line):
    fields = []
    current = []
    in_quotes = False
    for c in line:
        if c == '"':
            in_quotes = not in_quotes
        elif c == ',' and not in_quotes:
            fields.append(''.join(current))
            current = []
        else:
            current.append(c)
    fields.append(''.join(current))
    return fields

Group Records by a Key MEDIUM

def group_by_key(records, key):
    groups = {}
    for record in records:
        groups.setdefault(record[key], []).append(record)
    return groups

Flatten a Nested Dictionary MEDIUM

def flatten_dict(d, prefix=''):
    result = {}
    for key, value in d.items():
        full = prefix + key if not prefix else prefix + '.' + key
        if isinstance(value, dict):
            result.update(flatten_dict(value, full))
        else:
            result[full] = value
    return result

Deep Merge Two Dictionaries MEDIUM

def deep_merge(a, b):
    result = dict(a)
    for key, value in b.items():
        if key in result and isinstance(result[key], dict) and isinstance(value, dict):
            result[key] = deep_merge(result[key], value)
        else:
            result[key] = value
    return result

Rate Limit Check MEDIUM

def rate_limit_ok(timestamps, now, limit, window):
    recent = [t for t in timestamps if t > now - window]
    return len(recent) < limit

Paginate a List MEDIUM

def paginate(items, page, per_page):
    start = (page - 1) * per_page
    return items[start:start + per_page]

Parse a Duration String MEDIUM

def parse_duration(s):
    units = {'h': 3600, 'm': 60, 's': 1}
    total = 0
    num = ''
    for c in s:
        if c.isdigit():
            num += c
        elif c in units:
            total += int(num) * units[c]
            num = ''
    return total

Deduplicate Preserving Order MEDIUM

def dedupe(items):
    seen = set()
    result = []
    for item in items:
        if item not in seen:
            seen.add(item)
            result.append(item)
    return result

Exponential Backoff Delays MEDIUM

def backoff_delays(attempts, base, max_delay):
    delays = []
    for i in range(attempts):
        delay = min(base * (2 ** i), max_delay)
        delays.append(delay)
    return delays

Top N Items by Frequency MEDIUM

def top_n_by_count(items, n):
    from collections import Counter
    counts = Counter(items)
    return counts.most_common(n)

OOP System Design - Cloud E-Reader HARD

Design the core classes for an online cloud reading app (think Kindle, but for indie short stories). Requirements: a user has a library of books they can add to / remove from; they can set one book active; the app remembers where they left off in each book; and it shows one page at a time of the active book. Keep the Book and Library responsibilities separate so the storage format can change later.

class Book:
    """One story. content = list of page-strings; remembers the reader's spot."""
    def __init__(self, book_id, title, content):
        self.id = book_id
        self.title = title
        self.content = content          # list[str], one entry per page
        self.last_page = 0              # index into content

    def display_page(self):
        return self.content[self.last_page]

    def turn_page(self):
        if self.last_page < len(self.content) - 1:
            self.last_page += 1
        return self.display_page()


class Library:
    """A reader's collection of books + which one is open right now."""
    def __init__(self):
        self.collection = {}            # id -> Book  (dict = O(1) lookup)
        self.active_id = None
        self._next_id = 0               # simple unique-id generator

    def add_book(self, title, content):
        book = Book(self._next_id, title, content)
        self.collection[book.id] = book
        self._next_id += 1
        return book.id

    def remove_book(self, book_id):
        self.collection.pop(book_id, None)
        if self.active_id == book_id:
            self.active_id = None

    def set_active(self, book_id):
        if book_id in self.collection:
            self.active_id = book_id

    def display_page(self):
        if self.active_id is None: return None
        return self.collection[self.active_id].display_page()

    def turn_page(self):
        if self.active_id is None: return None
        return self.collection[self.active_id].turn_page()

# Follow-ups the interviewer will ask:
#  • Bigger font? Store content as ONE string + a Display class that computes
#    chars_per_page from font_size, then page n = content[n*cpp : (n+1)*cpp].
#  • Many users sharing books? Store each Book ONCE (e.g. a SQL table keyed by a
#    global id); keep per-user state (active_id, last_page) in a separate UserState.

Edit Distance (Levenshtein) HARD

The other DP every fuzzy-matching/plagiarism system uses: minimum single-character insert / delete / replace edits to turn string a into b. Bottom-up table, O(n·m).

def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = i        # delete all of a[:i]
    for j in range(m + 1): dp[0][j] = j        # insert all of b[:j]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]         # chars match -> free
            else:
                dp[i][j] = 1 + min(dp[i-1][j],      # delete
                                   dp[i][j-1],      # insert
                                   dp[i-1][j-1])    # replace
    return dp[n][m]

Compare Semantic Versions HARD

def compare_versions(a, b):
    pa = [int(x) for x in a.split('.')]
    pb = [int(x) for x in b.split('.')]
    length = max(len(pa), len(pb))
    pa += [0] * (length - len(pa))
    pb += [0] * (length - len(pb))
    for x, y in zip(pa, pb):
        if x < y:
            return -1
        if x > y:
            return 1
    return 0

Parse CSV Into Records HARD

def csv_to_records_realworld(text):
    lines = [line for line in text.strip().split('\n') if line]
    if not lines:
        return []
    headers = lines[0].split(',')
    records = []
    for line in lines[1:]:
        values = line.split(',')
        records.append(dict(zip(headers, values)))
    return records

Get a Value by Dotted Path HARD

def get_by_path(obj, path):
    current = obj
    for part in path.split('.'):
        if isinstance(current, dict):
            if part not in current:
                return None
            current = current[part]
        elif isinstance(current, list):
            idx = int(part)
            if idx < 0 or idx >= len(current):
                return None
            current = current[idx]
        else:
            return None
    return current

Validate a Password HARD

def validate_password(pw):
    failures = []
    if len(pw) < 8:
        failures.append('too_short')
    if not any(c.isupper() for c in pw):
        failures.append('no_upper')
    if not any(c.islower() for c in pw):
        failures.append('no_lower')
    if not any(c.isdigit() for c in pw):
        failures.append('no_digit')
    if not any(not c.isalnum() for c in pw):
        failures.append('no_special')
    return failures

Diff Two Lists HARD

def diff_lists(old, new):
    old_set = set(old)
    new_set = set(new)
    added = [x for x in new if x not in old_set]
    removed = [x for x in old if x not in new_set]
    return {'added': added, 'removed': removed}

Parse an INI Config HARD

def parse_ini_realworld(text):
    config = {}
    section = None
    for line in text.split('\n'):
        line = line.strip()
        if not line or line.startswith(';'):
            continue
        if line.startswith('[') and line.endswith(']'):
            section = line[1:-1]
            config[section] = {}
        elif '=' in line and section is not None:
            key, value = line.split('=', 1)
            config[section][key.strip()] = value.strip()
    return config

Expand a Range Expression HARD

def expand_ranges(s):
    result = []
    for part in s.split(','):
        part = part.strip()
        if '-' in part:
            start, end = part.split('-')
            result.extend(range(int(start), int(end) + 1))
        else:
            result.append(int(part))
    return result

Format an Aligned Text Table HARD

def format_table(rows):
    if not rows:
        return ''
    cols = len(rows[0])
    widths = [max(len(row[c]) for row in rows) for c in range(cols)]
    lines = []
    for row in rows:
        lines.append('  '.join(cell.ljust(widths[c]) for c, cell in enumerate(row)))
    return '\n'.join(line.rstrip() for line in lines)

Normalize a File Path HARD

def normalize_path(path):
    parts = path.split('/')
    stack = []
    for part in parts:
        if part == '' or part == '.':
            continue
        if part == '..':
            if stack:
                stack.pop()
        else:
            stack.append(part)
    return '/' + '/'.join(stack)

Parse a Web Server Log Line HARD

def parse_log_line(line):
    import re
    pattern = r'(\S+) \S+ \S+ \[[^\]]+\] "(\S+) (\S+) [^"]*" (\d+) (\d+)'
    m = re.match(pattern, line)
    if not m:
        return None
    return {
        'ip': m.group(1),
        'method': m.group(2),
        'path': m.group(3),
        'status': int(m.group(4)),
        'size': int(m.group(5)),
    }

🏢 Real-world & on-the-job problems

Pulled straight from what 2026 job listings actually ask for - across data, finance, cloud and full-stack roles the recurring hard skills are SQL, OOP/system design, dynamic programming, APIs/JSON and unit testing. These are worked end-to-end, the way a real 45-minute interview runs (design first, then an algorithm). The two headline problems below are the exact format of a full-length mock interview: an open-ended OOP design, then a DP algorithm.

Mixed & Hardest

Optimal Freelancing EASY

Max profit picking jobs (1 day each) by their deadlines within a 7-day week. Greedy by pay.

class Solution:
    def optimal_freelancing(self, jobs):
        LIMIT = 7
        jobs.sort(key=lambda j: j["payment"], reverse=True)
        taken = [False] * LIMIT; profit = 0
        for job in jobs:
            for day in range(min(job["deadline"], LIMIT) - 1, -1, -1):
                if not taken[day]:
                    taken[day] = True; profit += job["payment"]; break
        return profit

Knight Connection (two knights meet) MEDIUM

Min total moves for two knights to land on the same square. BFS from one; they move alternately.

from collections import deque

class Solution:
    def knight_connection(self, a, b):
        moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
        q = deque([(a[0], a[1], 0)]); seen = {tuple(a)}
        while q:
            r, c, d = q.popleft()
            if [r, c] == b: return (d + 1) // 2
            for dr, dc in moves:
                nxt = (r + dr, c + dc)
                if nxt not in seen:
                    seen.add(nxt); q.append((nxt[0], nxt[1], d + 1))

Split Binary Tree MEDIUM

Can one cut split the tree into two equal-sum halves? Returns that half-sum or 0.

class Solution:
    def split_binary_tree(self, tree):
        def total(node):
            return 0 if not node else node.value + total(node.left) + total(node.right)
        whole = total(tree)
        if whole % 2: return 0
        found = [False]
        def helper(node):
            if not node: return 0
            s = node.value + helper(node.left) + helper(node.right)
            if s == whole // 2: found[0] = True
            return s
        helper(tree)
        return whole // 2 if found[0] else 0

Merging Linked Lists (find intersection) MEDIUM

Where two lists join. Swap each pointer to the other list's head when it ends - they meet at the join. O(n).

class Solution:
    def merging_linked_lists(self, l1, l2):
        a, b = l1, l2
        while a != b:
            a = a.next if a else l2
            b = b.next if b else l1
        return a            # the shared node (or None)

Min Heap Construction (from scratch) MEDIUM

class MinHeap:
    def __init__(self, array):
        self.heap = array
        for i in range((len(array) - 2) // 2, -1, -1):   # heapify, O(n)
            self.sift_down(i)
    def sift_down(self, i):
        n = len(self.heap)
        while 2*i + 1 < n:
            child = 2*i + 1
            if 2*i + 2 < n and self.heap[2*i+2] < self.heap[child]:
                child = 2*i + 2
            if self.heap[child] < self.heap[i]:
                self.heap[i], self.heap[child] = self.heap[child], self.heap[i]; i = child
            else: break
    def sift_up(self, i):
        while i > 0 and self.heap[i] < self.heap[(i-1)//2]:
            self.heap[i], self.heap[(i-1)//2] = self.heap[(i-1)//2], self.heap[i]; i = (i-1)//2
    def insert(self, v):
        self.heap.append(v); self.sift_up(len(self.heap) - 1)
    def remove(self):
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        v = self.heap.pop(); self.sift_down(0); return v

Juice Bottling MEDIUM

Split N liters into bottle sizes to maximize total price (like rod-cutting), returning the split. O(n²).

class Solution:
    def juice_bottling(self, prices):
        n = len(prices) - 1
        dp = [0] * len(prices); splits = [[] for _ in prices]
        for size in range(1, len(prices)):
            for liters in range(1, size + 1):
                if dp[size - liters] + prices[liters] > dp[size]:
                    dp[size] = dp[size - liters] + prices[liters]
                    splits[size] = splits[size - liters] + [liters]
        return splits[n]

Zero Sum Subarray MEDIUM

Does any subarray sum to 0? If a running sum repeats, the slice between is 0. O(n).

class Solution:
    def zero_sum_subarray(self, nums):
        seen = {0}; running = 0
        for n in nums:
            running += n
            if running in seen: return True
            seen.add(running)
        return False

Binary Tree Diameter MEDIUM

class Solution:
    def binary_tree_diameter(self, tree):
        diameter = [0]
        def height(node):
            if not node: return 0
            lh, rh = height(node.left), height(node.right)
            diameter[0] = max(diameter[0], lh + rh)
            return max(lh, rh) + 1
        height(tree)
        return diameter[0]

Minimum Passes Of Matrix MEDIUM

Each pass, positives convert their negative neighbors. How many passes to flip all? Multi-source BFS. O(w·h).

from collections import deque

class Solution:
    def minimum_passes_of_matrix(self, matrix):
        q = deque((r, c) for r in range(len(matrix))
                  for c in range(len(matrix[0])) if matrix[r][c] > 0)
        passes = 0
        while q:
            for _ in range(len(q)):
                r, c = q.popleft()
                for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                    nr, nc = r+dr, c+dc
                    if 0 <= nr < len(matrix) and 0 <= nc < len(matrix[0]) and matrix[nr][nc] < 0:
                        matrix[nr][nc] *= -1; q.append((nr, nc))
            passes += 1
        return -1 if any(v < 0 for row in matrix for v in row) else max(passes - 1, 0)

Best Digits (remove k to maximize) MEDIUM

class Solution:
    def best_digits(self, number, k):
        stack = []
        for d in number:
            while k > 0 and stack and stack[-1] < d:
                stack.pop(); k -= 1
            stack.append(d)
        return "".join(stack[:len(stack) - k]) if k else "".join(stack)

Colliding Asteroids MEDIUM

Positive = moving right, negative = left. Use a stack; resolve collisions. O(n).

class Solution:
    def colliding_asteroids(self, asteroids):
        stack = []
        for a in asteroids:
            alive = True
            while alive and a < 0 and stack and stack[-1] > 0:
                if stack[-1] < -a: stack.pop()
                elif stack[-1] == -a: stack.pop(); alive = False
                else: alive = False
            if alive: stack.append(a)
        return stack

Minimum Characters For Words MEDIUM

from collections import Counter

class Solution:
    def minimum_characters_for_words(self, words):
        max_counts = {}
        for word in words:
            for ch, cnt in Counter(word).items():
                max_counts[ch] = max(max_counts.get(ch, 0), cnt)
        out = []
        for ch, cnt in max_counts.items(): out += [ch] * cnt
        return out

Longest Balanced Substring HARD

Longest run of valid () parentheses. Stack of indices. O(n).

class Solution:
    def longest_balanced(self, s):
        stack = [-1]; longest = 0
        for i, ch in enumerate(s):
            if ch == "(":
                stack.append(i)
            else:
                stack.pop()
                if not stack: stack.append(i)
                else: longest = max(longest, i - stack[-1])
        return longest

Right Smaller Than HARD

For each element, how many to its right are smaller. Insert into a sorted list from the right. O(n²) (O(n log n) with a BIT).

import bisect

class Solution:
    def right_smaller_than(self, arr):
        res = [0] * len(arr); sorted_seen = []
        for i in range(len(arr) - 1, -1, -1):
            pos = bisect.bisect_left(sorted_seen, arr[i])
            res[i] = pos
            sorted_seen.insert(pos, arr[i])
        return res

Maximize Expression HARD

Maximize a[i]−a[j]+a[k]−a[l] for i<j<k<l. Build four running-best arrays. O(n).

class Solution:
    def maximize_expression(self, arr):
        n = len(arr)
        if n < 4: return 0
        maxA = [arr[0]] * n
        for i in range(1, n): maxA[i] = max(maxA[i-1], arr[i])
        maxAB = [float("-inf")] * n
        for i in range(1, n): maxAB[i] = max(maxAB[i-1], maxA[i-1] - arr[i])
        maxABC = [float("-inf")] * n
        for i in range(2, n): maxABC[i] = max(maxABC[i-1], maxAB[i-1] + arr[i])
        maxABCD = [float("-inf")] * n
        for i in range(3, n): maxABCD[i] = max(maxABCD[i-1], maxABC[i-1] - arr[i])
        return maxABCD[n-1]

Repair BST (two nodes swapped) HARD

An in-order walk of a BST is sorted - the two out-of-order nodes are the swapped pair. O(n).

class Solution:
    def repair_bst(self, tree):
        first = second = prev = None
        def inorder(node):
            nonlocal first, second, prev
            if not node: return
            inorder(node.left)
            if prev and prev.value > node.value:
                if not first: first = prev
                second = node
            prev = node
            inorder(node.right)
        inorder(tree)
        first.value, second.value = second.value, first.value
        return tree

Validate Three Nodes HARD

Is the middle node a descendant of one outer node and an ancestor of the other? O(h).

class Solution:
    def validate_three_nodes(self, one, two, three):
        def is_descendant(node, target):
            while node and node != target:
                node = node.left if target.value < node.value else node.right
            return node == target
        if is_descendant(two, one):  return is_descendant(three, two)
        if is_descendant(two, three): return is_descendant(one, two)
        return False

Line Through Points HARD

Max points on a single straight line. Group by reduced slope (use gcd to normalize). O(n²).

from math import gcd

class Solution:
    def line_through_points(self, points):
        best = 1
        for i in range(len(points)):
            slopes = {}
            for j in range(i + 1, len(points)):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                g = gcd(dx, dy) or 1
                slope = (dx // g, dy // g)
                slopes[slope] = slopes.get(slope, 1) + 1
                best = max(best, slopes[slope])
        return best

Stable Internships (Gale-Shapley) HARD

Match interns ↔ teams so no pair would both rather swap. The classic stable-matching algorithm.

class Solution:
    def stable_internships(self, interns, teams):
        chosen = {}                       # team -> intern
        free = list(range(len(interns)))
        next_choice = [0] * len(interns)
        while free:
            intern = free.pop(0)
            team = interns[intern][next_choice[intern]]
            next_choice[intern] += 1
            if team not in chosen:
                chosen[team] = intern
            else:
                current = chosen[team]; pref = teams[team]
                if pref.index(intern) < pref.index(current):
                    chosen[team] = intern; free.append(current)
                else:
                    free.append(intern)
        return [[team, intern] for team, intern in chosen.items()]

Shortest Unique Prefixes HARD

Shortest prefix of each word that no other word shares. Trie with counts. O(total chars).

class Solution:
    def shortest_unique_prefixes(self, strings):
        trie = {}
        for s in strings:                 # build trie, counting visits
            node = trie
            for ch in s:
                node = node.setdefault(ch, {"count": 0})
                node["count"] += 1
        res = []
        for s in strings:
            node = trie; prefix = ""
            for ch in s:
                node = node[ch]; prefix += ch
                if node["count"] == 1: break   # unique from here
            res.append(prefix)
        return res

Square of Zeroes HARD

Is there a square whose border is all 0s? Precompute consecutive zeros right/down, then check each square. O(n³).

class Solution:
    def square_of_zeroes(self, matrix):
        n = len(matrix)
        info = [[[0, 0] for _ in range(n)] for _ in range(n)]   # [right, down]
        for r in range(n - 1, -1, -1):
            for c in range(n - 1, -1, -1):
                if matrix[r][c] == 0:
                    info[r][c][0] = 1 + (info[r][c+1][0] if c+1 < n else 0)
                    info[r][c][1] = 1 + (info[r+1][c][1] if r+1 < n else 0)
        for r in range(n):
            for c in range(n):
                for size in range(2, n - max(r, c) + 1):
                    br, bc = r + size - 1, c + size - 1
                    if (info[r][c][0] >= size and info[r][c][1] >= size and
                            info[r][bc][1] >= size and info[br][c][0] >= size):
                        return True
        return False

Optimal Assembly Line HARD

Min possible max-station-time when splitting ordered steps across k stations. Binary-search the answer. O(n log(sum)).

class Solution:
    def optimal_assembly_line(self, durations, num_stations):
        def feasible(max_time):
            used, current = 1, 0
            for d in durations:
                if d > max_time: return False
                if current + d > max_time: used += 1; current = d
                else: current += d
            return used <= num_stations
        lo, hi, best = max(durations), sum(durations), sum(durations)
        while lo <= hi:
            mid = (lo + hi) // 2
            if feasible(mid): best = mid; hi = mid - 1
            else: lo = mid + 1
        return best

Pattern Matcher HARD

Given a pattern of x's & y's, find strings for x and y that rebuild s. Try every length of x. O(n²).

class Solution:
    def pattern_matcher(self, pattern, s):
        if len(pattern) > len(s): return []
        swapped = pattern[0] != "x"
        p = ["x" if c == "y" else "y" for c in pattern] if swapped else list(pattern)
        cx, cy = p.count("x"), p.count("y")
        first_y = p.index("y") if cy else None
        if cy:
            for lx in range(1, len(s) // cx + 1):
                rem = len(s) - lx * cx
                if rem % cy: continue
                ly = rem // cy
                yi = first_y * lx
                x, y = s[:lx], s[yi:yi + ly]
                if "".join(x if c == "x" else y for c in p) == s:
                    return [y, x] if swapped else [x, y]
        else:
            if len(s) % cx: return []
            x = s[: len(s) // cx]
            if x * cx == s:
                return ["", x] if swapped else [x, ""]
        return []

Right Sibling Tree HARD

Rewire every node's right to point to its sibling on the same level. Recurse left before mutating right.

class Solution:
    def right_sibling_tree(self, root):
        def mutate(node, parent, is_left):
            if node is None: return
            left, right = node.left, node.right
            mutate(left, node, True)
            if parent is None: node.right = None
            elif is_left: node.right = parent.right
            else: node.right = parent.right.left if parent.right else None
            mutate(right, node, False)
        mutate(root, None, False)
        return root

Airport Connections HARD

Fewest new routes so every airport is reachable from the start. Score unreachable airports by how many other unreachable ones they unlock; add greedily.

class Solution:
    def airport_connections(self, airports, routes, start):
        graph = {a: [] for a in airports}
        for src, dst in routes: graph[src].append(dst)
        reachable = set()
        def dfs(node):
            if node in reachable: return
            reachable.add(node)
            for nb in graph[node]: dfs(nb)
        dfs(start)
        def reach_count(node, seen):
            if node in seen: return 0
            seen.add(node)
            total = 0 if node in reachable else 1
            for nb in graph[node]: total += reach_count(nb, seen)
            return total
        scored = sorted(((a, reach_count(a, set())) for a in airports if a not in reachable),
                        key=lambda x: -x[1])
        connections = 0
        for airport, _ in scored:
            if airport in reachable: continue
            connections += 1
            dfs(airport)
        return connections

Largest Park HARD

Biggest rectangle of empty land (0s) in a grid. Row-by-row histogram + largest-rectangle. O(rows·cols).

class Solution:
    def largest_park(self, land):
        cols = len(land[0]); heights = [0] * cols; best = 0
        for row in land:
            for c in range(cols):
                heights[c] = 0 if row[c] == 1 else heights[c] + 1
            stack = []                              # largest rectangle in histogram
            for i in range(cols + 1):
                h = heights[i] if i < cols else 0
                while stack and heights[stack[-1]] >= h:
                    height = heights[stack.pop()]
                    width = i if not stack else i - stack[-1] - 1
                    best = max(best, height * width)
                stack.append(i)
        return best

Sum BSTs (count valid BST subtrees) HARD

class Solution:
    def count_bsts(self, tree):
        count = [0]
        def helper(node):                # returns (is_bst, min, max)
            if not node: return (True, float("inf"), float("-inf"))
            lb, lmin, lmax = helper(node.left)
            rb, rmin, rmax = helper(node.right)
            is_bst = lb and rb and lmax < node.value < rmin
            if is_bst: count[0] += 1
            return (is_bst, min(lmin, node.value), max(rmax, node.value))
        helper(tree)
        return count[0]

Doubly Linked List (construction) HARD

class DLL:
    def __init__(self): self.head = self.tail = None
    def set_head(self, node):
        if not self.head: self.head = self.tail = node; return
        self.insert_before(self.head, node)
    def insert_before(self, node, new):
        self.remove(new)
        new.prev, new.next = node.prev, node
        if node.prev is None: self.head = new
        else: node.prev.next = new
        node.prev = new
    def remove(self, node):
        if node is self.head: self.head = node.next
        if node is self.tail: self.tail = node.prev
        if node.prev: node.prev.next = node.next
        if node.next: node.next.prev = node.prev
        node.prev = node.next = None

Blackjack Probability HARD

Chance the dealer busts (goes over the target). Dealer draws (cards 1-10) until within 4 of target. Memoized.

class Solution:
    def blackjack_probability(self, target, starting):
        cache = {}
        def helper(current):
            if current > target: return 1.0          # busted
            if current + 4 >= target: return 0.0      # dealer stands, safe
            if current in cache: return cache[current]
            cache[current] = sum(helper(current + d) for d in range(1, 11)) / 10
            return cache[current]
        return round(helper(starting), 3)

Two-Edge-Connected Graph HARD

Is the graph connected with no "bridge" edges (every edge lies on a cycle)? DFS arrival/low times (Tarjan). O(V+E).

class Solution:
    def two_edge_connected(self, edges):
        n = len(edges)
        if n == 0: return True
        arrival = [-1] * n
        def dfs(node, prev, time):
            arrival[node] = time; lowest = time
            for nb in edges[node]:
                if arrival[nb] == -1:
                    low = dfs(nb, node, time + 1)
                    if low == -1: return -1            # bridge below
                    if low <= arrival[node] and node != 0 is False: pass
                    lowest = min(lowest, low)
                elif nb != prev:
                    lowest = min(lowest, arrival[nb])
            if lowest == arrival[node] and node != 0:  # edge to parent is a bridge
                return -1
            return lowest
        if dfs(0, -1, 0) == -1: return False
        return all(a != -1 for a in arrival)           # also fully connected

Count Squares HARD

How many squares can be formed from a set of points? Check each pair as a diagonal. O(n²).

class Solution:
    def count_squares(self, points):
        pts = {(x, y) for x, y in points}; count = 0
        for x1, y1 in points:
            for x2, y2 in points:
                if (x1, y1) == (x2, y2): continue
                mx, my = (x1 + x2) / 2, (y1 + y2) / 2
                dx, dy = x1 - mx, y1 - my
                if (mx - dy, my + dx) in pts and (mx + dy, my - dx) in pts:
                    count += 1
        return count // 4                       # each square counted 4×

Largest Island HARD

Flip one water cell to land - what's the biggest land block possible? Label regions, then test each water cell. O(w·h).

class Solution:
    def largest_island(self, grid):
        n, m = len(grid), len(grid[0])
        rid = [[-1]*m for _ in range(n)]; sizes = {}; cur = 0
        def fill(r, c, cur):
            stack = [(r, c)]; size = 0
            while stack:
                i, j = stack.pop()
                if 0<=i<n and 0<=j<m and grid[i][j]==0 and rid[i][j]==-1:
                    rid[i][j] = cur; size += 1
                    stack += [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]
            return size
        for r in range(n):
            for c in range(m):
                if grid[r][c]==0 and rid[r][c]==-1:
                    sizes[cur] = fill(r, c, cur); cur += 1
        best = max(sizes.values(), default=0)
        for r in range(n):
            for c in range(m):
                if grid[r][c]==1:
                    ids = {rid[r+dr][c+dc] for dr, dc in ((1,0),(-1,0),(0,1),(0,-1))
                           if 0<=r+dr<n and 0<=c+dc<m and grid[r+dr][c+dc]==0}
                    best = max(best, 1 + sum(sizes[i] for i in ids))
        return best

Sort K-Sorted Array HARD

Every element is at most k spots from its sorted position. A size-(k+1) min-heap. O(n log k).

import heapq

class Solution:
    def sort_k_sorted(self, array, k):
        heap = array[:k+1]; heapq.heapify(heap); idx = 0
        for i in range(k+1, len(array)):
            array[idx] = heapq.heappop(heap); idx += 1
            heapq.heappush(heap, array[i])
        while heap:
            array[idx] = heapq.heappop(heap); idx += 1
        return array

Merge K Sorted Arrays HARD

import heapq

class Solution:
    def merge_sorted_arrays(self, arrays):
        heap = [(arr[0], i, 0) for i, arr in enumerate(arrays) if arr]
        heapq.heapify(heap); res = []
        while heap:
            val, a, e = heapq.heappop(heap); res.append(val)
            if e + 1 < len(arrays[a]):
                heapq.heappush(heap, (arrays[a][e+1], a, e+1))
        return res

Shift Linked List HARD

Rotate a list by k. Make it circular, then break it at the right spot. O(n).

class Solution:
    def shift_linked_list(self, head, k):
        length = 1; tail = head
        while tail.next: tail = tail.next; length += 1
        k %= length
        if k == 0: return head
        tail.next = head                          # circular
        new_tail = head
        for _ in range(length - k - 1): new_tail = new_tail.next
        new_head = new_tail.next; new_tail.next = None
        return new_head

Lowest Common Manager HARD

LCA on an org chart (n-ary tree, no parent links). Count how many of the two appear in each subtree. O(n).

class Solution:
    def lowest_common_manager(self, top, one, two):
        def helper(manager):
            count = 0
            for report in manager.direct_reports:
                found, lca = helper(report)
                if lca: return 0, lca
                count += found
            if manager in (one, two): count += 1
            return count, (manager if count == 2 else None)
        return helper(top)[1]

Ambiguous Measurements HARD

Can imprecise measuring cups produce a target range? Memoized recursion.

class Solution:
    def ambiguous_measurements(self, cups, low, high):
        cache = {}
        def can(low, high):
            if low <= 0 and high <= 0: return False
            if (low, high) in cache: return cache[(low, high)]
            result = False
            for cl, ch in cups:
                if low <= cl and ch <= high:
                    result = True; break
                if can(max(0, low - cl), max(0, high - ch)):
                    result = True; break
            cache[(low, high)] = result
            return result
        return can(low, high)

Shorten Path HARD

Simplify a Unix-style path (handle ., .., extra slashes). Stack. O(n).

class Solution:
    def shorten_path(self, path):
        is_abs = path[0] == "/"
        tokens = [t for t in path.split("/") if t and t != "."]
        stack = [""] if is_abs else []
        for t in tokens:
            if t == "..":
                if not stack or stack[-1] == "..":
                    if not is_abs: stack.append(t)
                elif stack[-1] != "":
                    stack.pop()
            else:
                stack.append(t)
        if stack == [""]: return "/"
        return "/".join(stack)

Rearrange Linked List (around a value) HARD

Reorder so everything < k comes before == k before > k. Build three sublists, then stitch. O(n).

class Solution:
    def rearrange_linked_list(self, head, k):
        parts = {"less": [None, None], "equal": [None, None], "greater": [None, None]}
        node = head
        while node:
            nxt = node.next; node.next = None
            b = "less" if node.value < k else "greater" if node.value > k else "equal"
            h, t = parts[b]
            if not h: parts[b] = [node, node]
            else: t.next = node; parts[b][1] = node
            node = nxt
        new_head = prev_tail = None
        for h, t in (parts["less"], parts["equal"], parts["greater"]):
            if h is None: continue
            if new_head is None: new_head = h
            if prev_tail: prev_tail.next = h
            prev_tail = t
        return new_head

Laptop Rentals HARD

Min laptops for overlapping rental times. Sort starts & ends, sweep with two pointers. O(n log n).

class Solution:
    def laptop_rentals(self, times):
        if not times: return 0
        starts = sorted(t[0] for t in times)
        ends = sorted(t[1] for t in times)
        used = max_used = s = e = 0
        while s < len(starts):
            if starts[s] < ends[e]:
                used += 1; s += 1; max_used = max(max_used, used)
            else:
                used -= 1; e += 1
        return max_used

Strings Made Up Of Strings HARD

Which big strings can be built by concatenating the smaller ones (word-break)? DP per string. O(n·L²).

class Solution:
    def strings_made_up_of_strings(self, strings, substrings):
        subs = set(substrings)
        max_len = max((len(s) for s in substrings), default=0)
        out = []
        for s in strings:
            n = len(s); dp = [False] * (n + 1); dp[0] = True
            for i in range(1, n + 1):
                for j in range(max(0, i - max_len), i):
                    if dp[j] and s[j:i] in subs:
                        dp[i] = True; break
            if dp[n]: out.append(s)
        return out

Longest Most Frequent Prefix HARD

Longest prefix shared by the most strings. Build a counting trie, then follow the most-visited path. O(total chars).

class Solution:
    def longest_most_frequent_prefix(self, strings):
        trie = {}
        for s in strings:
            node = trie
            for ch in s:
                node = node.setdefault(ch, {"_count": 0})
                node["_count"] += 1
        best_count = len(strings)
        node = trie; prefix = ""
        while True:
            nxt = next(((ch, c) for ch, c in node.items()
                        if ch != "_count" and c["_count"] == best_count), None)
            if not nxt: break
            prefix += nxt[0]; node = nxt[1]
        return prefix

Waterfall Streams HARD

Water poured at a source flows down, splitting 50/50 around walls (1s). Return how much reaches each bottom slot. Row-by-row simulation; carry % as negatives.

class Solution:
    def waterfall_streams(self, array, source):
        rows = [r[:] for r in array]
        rows[0][source] = -1                      # -1 == 100% water
        for r in range(len(rows) - 1):
            for c in range(len(rows[r])):
                cur = rows[r][c]
                if cur >= 0: continue              # no water here
                if rows[r+1][c] == 0:              # falls straight down
                    rows[r+1][c] += cur; continue
                split = cur / 2                    # blocked → split left/right
                left = c
                while left - 1 >= 0:
                    left -= 1
                    if rows[r][left] == 1: break
                    if rows[r+1][left] == 0: rows[r+1][left] += split; break
                right = c
                while right + 1 < len(rows[r]):
                    right += 1
                    if rows[r][right] == 1: break
                    if rows[r+1][right] == 0: rows[r+1][right] += split; break
        return [(-v) * 100 if v < 0 else 0 for v in rows[-1]]

Top 150

🏆 Top 150 Interview Questions

Array / String

Merge Sorted Array EASY

Merge nums2 into nums1 in place - fill from the back to avoid overwriting. O(m+n).

class Solution:
    def merge(self, nums1, m, nums2, n):
        i, j, k = m - 1, n - 1, m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]; i -= 1
            else:
                nums1[k] = nums2[j]; j -= 1
            k -= 1

Remove Element EASY

class Solution:
    def remove_element(self, nums, val):
        k = 0
        for n in nums:
            if n != val: nums[k] = n; k += 1
        return k

Remove Duplicates from Sorted Array EASY

class Solution:
    def remove_duplicates(self, nums):
        if not nums: return 0
        k = 1
        for i in range(1, len(nums)):
            if nums[i] != nums[k-1]:
                nums[k] = nums[i]; k += 1
        return k

Remove Duplicates from Sorted Array II (keep 2) MEDIUM

class Solution:
    def remove_duplicates_ii(self, nums):
        k = 0
        for n in nums:
            if k < 2 or n != nums[k-2]:
                nums[k] = n; k += 1
        return k

Majority Element EASY

class Solution:
    def majority_element(self, nums):
        count = 0; cand = None
        for n in nums:
            if count == 0: cand = n
            count += 1 if n == cand else -1
        return cand

Rotate Array MEDIUM

class Solution:
    def rotate(self, nums, k):
        k %= len(nums)
        nums[:] = nums[-k:] + nums[:-k]

Best Time to Buy and Sell Stock EASY

class Solution:
    def max_profit(self, prices):
        min_price = float("inf"); profit = 0
        for p in prices:
            min_price = min(min_price, p)
            profit = max(profit, p - min_price)
        return profit

Best Time to Buy and Sell Stock II MEDIUM

Unlimited trades → grab every upward step. O(n).

class Solution:
    def max_profit_ii(self, prices):
        return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))

Jump Game MEDIUM

class Solution:
    def can_jump(self, nums):
        reach = 0
        for i, n in enumerate(nums):
            if i > reach: return False
            reach = max(reach, i + n)
        return True

Jump Game II (min jumps) MEDIUM

class Solution:
    def jump(self, nums):
        jumps = end = farthest = 0
        for i in range(len(nums) - 1):
            farthest = max(farthest, i + nums[i])
            if i == end:
                jumps += 1; end = farthest
        return jumps

H-Index MEDIUM

class Solution:
    def h_index(self, citations):
        citations.sort(reverse=True)
        h = 0
        for i, c in enumerate(citations):
            if c >= i + 1: h = i + 1
            else: break
        return h

Insert Delete GetRandom O(1) MEDIUM

Array for O(1) random + dict of value→index; on remove, swap with the last element.

import random
class RandomizedSet:
    def __init__(self):
        self.data = []; self.idx = {}
    def insert(self, val):
        if val in self.idx: return False
        self.idx[val] = len(self.data); self.data.append(val); return True
    def remove(self, val):
        if val not in self.idx: return False
        i = self.idx[val]; last = self.data[-1]
        self.data[i] = last; self.idx[last] = i
        self.data.pop(); del self.idx[val]; return True
    def getRandom(self):
        return random.choice(self.data)

Product of Array Except Self MEDIUM

Prefix products left-to-right, then multiply by suffix products right-to-left. No division. O(n).

class Solution:
    def product_except_self(self, nums):
        n = len(nums); res = [1] * n
        left = 1
        for i in range(n):
            res[i] = left; left *= nums[i]
        right = 1
        for i in range(n - 1, -1, -1):
            res[i] *= right; right *= nums[i]
        return res

Gas Station MEDIUM

class Solution:
    def can_complete_circuit(self, gas, cost):
        if sum(gas) < sum(cost): return -1
        total = start = 0
        for i in range(len(gas)):
            total += gas[i] - cost[i]
            if total < 0: total = 0; start = i + 1
        return start

Candy HARD

Two passes: reward left-to-right for rising ratings, then right-to-left. O(n).

class Solution:
    def candy(self, ratings):
        n = len(ratings); c = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i-1]: c[i] = c[i-1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i+1]: c[i] = max(c[i], c[i+1] + 1)
        return sum(c)

Trapping Rain Water HARD

class Solution:
    def trap(self, height):
        left, right = 0, len(height) - 1
        left_max = right_max = water = 0
        while left < right:
            if height[left] < height[right]:
                left_max = max(left_max, height[left])
                water += left_max - height[left]; left += 1
            else:
                right_max = max(right_max, height[right])
                water += right_max - height[right]; right -= 1
        return water

Roman to Integer EASY

class Solution:
    def roman_to_int(self, s):
        v = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
        total = 0
        for i in range(len(s)):
            if i + 1 < len(s) and v[s[i]] < v[s[i+1]]: total -= v[s[i]]
            else: total += v[s[i]]
        return total

Integer to Roman MEDIUM

class Solution:
    def int_to_roman(self, num):
        vals = [(1000,"M"),(900,"CM"),(500,"D"),(400,"CD"),(100,"C"),(90,"XC"),
                (50,"L"),(40,"XL"),(10,"X"),(9,"IX"),(5,"V"),(4,"IV"),(1,"I")]
        res = []
        for v, sym in vals:
            while num >= v: res.append(sym); num -= v
        return "".join(res)

Length of Last Word EASY

class Solution:
    def length_of_last_word(self, s):
        parts = s.split()
        return len(parts[-1]) if parts else 0

Longest Common Prefix EASY

class Solution:
    def longest_common_prefix(self, strs):
        if not strs: return ""
        prefix = strs[0]
        for s in strs[1:]:
            while not s.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix: return ""
        return prefix

Reverse Words in a String MEDIUM

class Solution:
    def reverse_words(self, s):
        return " ".join(s.split()[::-1])

Zigzag Conversion MEDIUM

class Solution:
    def convert(self, s, num_rows):
        if num_rows == 1: return s
        rows = [""] * num_rows
        r, step = 0, 1
        for c in s:
            rows[r] += c
            if r == 0: step = 1
            elif r == num_rows - 1: step = -1
            r += step
        return "".join(rows)

Find the Index of First Occurrence EASY

class Solution:
    def str_str(self, haystack, needle):
        n, m = len(haystack), len(needle)
        for i in range(n - m + 1):
            if haystack[i:i+m] == needle: return i
        return -1

Text Justification HARD

Greedily pack words per line, then distribute spaces evenly (extra spaces go to the left gaps); last line is left-justified.

class Solution:
    def full_justify(self, words, max_width):
        res = []; line = []; length = 0
        for w in words:
            if length + len(line) + len(w) > max_width:
                slots = max(1, len(line) - 1)
                for i in range(max_width - length):
                    line[i % slots] += " "
                res.append("".join(line)); line = []; length = 0
            line.append(w); length += len(w)
        res.append(" ".join(line).ljust(max_width))
        return res

Two Pointers

Valid Palindrome EASY

class Solution:
    def is_palindrome(self, s):
        cleaned = [c.lower() for c in s if c.isalnum()]
        return cleaned == cleaned[::-1]

Is Subsequence EASY

class Solution:
    def is_subsequence(self, s, t):
        i = 0
        for c in t:
            if i < len(s) and s[i] == c: i += 1
        return i == len(s)

Two Sum II - Input Array Is Sorted MEDIUM

class Solution:
    def two_sum_ii(self, numbers, target):
        lo, hi = 0, len(numbers) - 1
        while lo < hi:
            s = numbers[lo] + numbers[hi]
            if s == target: return [lo + 1, hi + 1]
            if s < target: lo += 1
            else: hi -= 1

Container With Most Water MEDIUM

class Solution:
    def max_area(self, height):
        lo, hi, best = 0, len(height) - 1, 0
        while lo < hi:
            best = max(best, min(height[lo], height[hi]) * (hi - lo))
            if height[lo] < height[hi]: lo += 1
            else: hi -= 1
        return best

3Sum MEDIUM

Sort, fix one number, then two-pointer the rest. Skip duplicates. O(n²).

class Solution:
    def three_sum(self, nums):
        nums.sort(); res = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]: continue
            lo, hi = i + 1, len(nums) - 1
            while lo < hi:
                s = nums[i] + nums[lo] + nums[hi]
                if s < 0: lo += 1
                elif s > 0: hi -= 1
                else:
                    res.append([nums[i], nums[lo], nums[hi]])
                    lo += 1; hi -= 1
                    while lo < hi and nums[lo] == nums[lo-1]: lo += 1
                    while lo < hi and nums[hi] == nums[hi+1]: hi -= 1
        return res

Sliding Window

Minimum Size Subarray Sum MEDIUM

class Solution:
    def min_subarray_len(self, target, nums):
        left = total = 0; best = float("inf")
        for right in range(len(nums)):
            total += nums[right]
            while total >= target:
                best = min(best, right - left + 1)
                total -= nums[left]; left += 1
        return best if best != float("inf") else 0

Longest Substring Without Repeating Characters MEDIUM

class Solution:
    def length_of_longest_substring(self, s):
        seen = {}; left = best = 0
        for right, c in enumerate(s):
            if c in seen and seen[c] >= left:
                left = seen[c] + 1
            seen[c] = right
            best = max(best, right - left + 1)
        return best

Substring with Concatenation of All Words HARD

from collections import Counter

class Solution:
    def find_substring(self, s, words):
        if not words: return []
        wl, n = len(words[0]), len(words); total = wl * n
        need = Counter(words); res = []
        for i in range(len(s) - total + 1):
            seen = Counter()
            for j in range(i, i + total, wl):
                word = s[j:j+wl]
                if word not in need: break
                seen[word] += 1
                if seen[word] > need[word]: break
            else:
                res.append(i)
        return res

Minimum Window Substring HARD

Expand right to cover all needed chars, then shrink left while still valid. O(n).

from collections import Counter

class Solution:
    def min_window(self, s, t):
        need = Counter(t); missing = len(t)
        left = start = 0; end = float("inf")
        for right, c in enumerate(s):
            if need[c] > 0: missing -= 1
            need[c] -= 1
            while missing == 0:
                if right - left < end - start: start, end = left, right
                need[s[left]] += 1
                if need[s[left]] > 0: missing += 1
                left += 1
        return s[start:end+1] if end != float("inf") else ""

Matrix

Valid Sudoku MEDIUM

class Solution:
    def is_valid_sudoku(self, board):
        seen = set()
        for r in range(9):
            for c in range(9):
                v = board[r][c]
                if v == ".": continue
                for key in ((v, "row", r), (v, "col", c), (v, "box", r//3, c//3)):
                    if key in seen: return False
                    seen.add(key)
        return True

Spiral Matrix MEDIUM

Pop the top row, rotate the rest counter-clockwise, repeat. O(m·n).

class Solution:
    def spiral_order(self, matrix):
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = [list(row) for row in zip(*matrix)][::-1]
        return res

Rotate Image (90° in place) MEDIUM

class Solution:
    def rotate_image(self, matrix):
        matrix.reverse()                       # flip vertically
        for i in range(len(matrix)):           # then transpose
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Set Matrix Zeroes MEDIUM

class Solution:
    def set_zeroes(self, matrix):
        rows, cols = set(), set()
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if matrix[r][c] == 0: rows.add(r); cols.add(c)
        for r in range(len(matrix)):
            for c in range(len(matrix[0])):
                if r in rows or c in cols: matrix[r][c] = 0

Game of Life MEDIUM

Encode next state in bit 2 so neighbors still read the old state (bit 1), then shift. O(m·n), O(1) space.

class Solution:
    def game_of_life(self, board):
        rows, cols = len(board), len(board[0])
        for r in range(rows):
            for c in range(cols):
                live = 0
                for dr in (-1, 0, 1):
                    for dc in (-1, 0, 1):
                        if (dr or dc) and 0 <= r+dr < rows and 0 <= c+dc < cols:
                            live += board[r+dr][c+dc] & 1
                if board[r][c] & 1:
                    if live in (2, 3): board[r][c] |= 2
                elif live == 3: board[r][c] |= 2
        for r in range(rows):
            for c in range(cols):
                board[r][c] >>= 1

Hashmap

Ransom Note EASY

from collections import Counter

class Solution:
    def can_construct(self, ransom_note, magazine):
        return not (Counter(ransom_note) - Counter(magazine))

Isomorphic Strings EASY

class Solution:
    def is_isomorphic(self, s, t):
        return len(set(s)) == len(set(t)) == len(set(zip(s, t)))

Word Pattern EASY

class Solution:
    def word_pattern(self, pattern, s):
        words = s.split()
        if len(pattern) != len(words): return False
        return len(set(pattern)) == len(set(words)) == len(set(zip(pattern, words)))

Valid Anagram EASY

from collections import Counter

class Solution:
    def is_anagram(self, s, t):
        return Counter(s) == Counter(t)

Group Anagrams MEDIUM

from collections import defaultdict

class Solution:
    def group_anagrams(self, strs):
        groups = defaultdict(list)
        for s in strs:
            groups[tuple(sorted(s))].append(s)
        return list(groups.values())

Two Sum EASY

class Solution:
    def two_sum(self, nums, target):
        seen = {}
        for i, n in enumerate(nums):
            if target - n in seen: return [seen[target - n], i]
            seen[n] = i

Happy Number EASY

class Solution:
    def is_happy(self, n):
        seen = set()
        while n != 1 and n not in seen:
            seen.add(n)
            n = sum(int(d) ** 2 for d in str(n))
        return n == 1

Contains Duplicate II EASY

class Solution:
    def contains_nearby_duplicate(self, nums, k):
        last = {}
        for i, n in enumerate(nums):
            if n in last and i - last[n] <= k: return True
            last[n] = i
        return False

Longest Consecutive Sequence MEDIUM

Put all in a set; only start counting from numbers with no left neighbor. O(n).

class Solution:
    def longest_consecutive(self, nums):
        s = set(nums); best = 0
        for n in s:
            if n - 1 not in s:
                length = 1
                while n + length in s: length += 1
                best = max(best, length)
        return best

Intervals

Summary Ranges EASY

class Solution:
    def summary_ranges(self, nums):
        res = []; i = 0
        while i < len(nums):
            start = nums[i]
            while i + 1 < len(nums) and nums[i+1] == nums[i] + 1: i += 1
            res.append(str(start) if start == nums[i] else f"{start}->{nums[i]}")
            i += 1
        return res

Merge Intervals MEDIUM

class Solution:
    def merge_intervals(self, intervals):
        intervals.sort()
        res = [intervals[0]]
        for s, e in intervals[1:]:
            if s <= res[-1][1]: res[-1][1] = max(res[-1][1], e)
            else: res.append([s, e])
        return res

Insert Interval MEDIUM

class Solution:
    def insert_interval(self, intervals, new):
        res = []; i = 0; n = len(intervals)
        while i < n and intervals[i][1] < new[0]:
            res.append(intervals[i]); i += 1
        while i < n and intervals[i][0] <= new[1]:
            new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]; i += 1
        res.append(new)
        while i < n: res.append(intervals[i]); i += 1
        return res

Min Number of Arrows to Burst Balloons MEDIUM

Sort by end, shoot at each non-overlapping end. Greedy. O(n log n).

class Solution:
    def find_min_arrow_shots(self, points):
        points.sort(key=lambda p: p[1])
        arrows = 1; end = points[0][1]
        for s, e in points[1:]:
            if s > end: arrows += 1; end = e
        return arrows

Stack

Valid Parentheses EASY

class Solution:
    def is_valid(self, s):
        pairs = {")": "(", "]": "[", "}": "{"}
        stack = []
        for c in s:
            if c in pairs:
                if not stack or stack.pop() != pairs[c]: return False
            else:
                stack.append(c)
        return not stack

Simplify Path MEDIUM

class Solution:
    def simplify_path(self, path):
        stack = []
        for part in path.split("/"):
            if part in ("", "."): continue
            if part == "..":
                if stack: stack.pop()
            else: stack.append(part)
        return "/" + "/".join(stack)

Min Stack MEDIUM

class MinStack:
    def __init__(self): self.stack = []
    def push(self, val):
        m = min(val, self.stack[-1][1]) if self.stack else val
        self.stack.append((val, m))
    def pop(self): self.stack.pop()
    def top(self): return self.stack[-1][0]
    def getMin(self): return self.stack[-1][1]

Evaluate Reverse Polish Notation MEDIUM

class Solution:
    def eval_rpn(self, tokens):
        stack = []
        ops = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
               "*": lambda a, b: a * b, "/": lambda a, b: int(a / b)}
        for t in tokens:
            if t in ops:
                b = stack.pop(); a = stack.pop(); stack.append(ops[t](a, b))
            else:
                stack.append(int(t))
        return stack[0]

Basic Calculator HARD

Handle + - ( ). Push the running result & sign on (, fold back on ). O(n).

class Solution:
    def calculate(self, s):
        stack = []; result = 0; num = 0; sign = 1
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c in "+-":
                result += sign * num; num = 0
                sign = 1 if c == "+" else -1
            elif c == "(":
                stack.append(result); stack.append(sign)
                result = 0; sign = 1
            elif c == ")":
                result += sign * num; num = 0
                result = result * stack.pop() + stack.pop()   # sign, then prev result
        return result + sign * num

Linked List

Linked List Cycle EASY

class Solution:
    def has_cycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next; fast = fast.next.next
            if slow == fast: return True
        return False

Add Two Numbers MEDIUM

class Solution:
    def add_two_numbers(self, l1, l2):
        dummy = ListNode(0); cur = dummy; carry = 0
        while l1 or l2 or carry:
            total = carry
            if l1: total += l1.val; l1 = l1.next
            if l2: total += l2.val; l2 = l2.next
            carry, digit = divmod(total, 10)
            cur.next = ListNode(digit); cur = cur.next
        return dummy.next

Merge Two Sorted Lists EASY

class Solution:
    def merge_two_lists(self, l1, l2):
        dummy = ListNode(0); tail = dummy
        while l1 and l2:
            if l1.val <= l2.val: tail.next = l1; l1 = l1.next
            else: tail.next = l2; l2 = l2.next
            tail = tail.next
        tail.next = l1 or l2
        return dummy.next

Copy List with Random Pointer MEDIUM

Map each old node to its clone, then wire up next/random. O(n).

class Solution:
    def copy_random_list(self, head):
        if not head: return None
        clone = {}
        cur = head
        while cur:
            clone[cur] = Node(cur.val); cur = cur.next
        cur = head
        while cur:
            clone[cur].next = clone.get(cur.next)
            clone[cur].random = clone.get(cur.random)
            cur = cur.next
        return clone[head]

Reverse Linked List II MEDIUM

class Solution:
    def reverse_between(self, head, left, right):
        dummy = ListNode(0, head); prev = dummy
        for _ in range(left - 1): prev = prev.next
        cur = prev.next
        for _ in range(right - left):
            nxt = cur.next
            cur.next = nxt.next
            nxt.next = prev.next
            prev.next = nxt
        return dummy.next

Reverse Nodes in k-Group HARD

class Solution:
    def reverse_k_group(self, head, k):
        node = head
        for _ in range(k):                      # need k nodes
            if not node: return head
            node = node.next
        prev = None; cur = head
        for _ in range(k):
            nxt = cur.next; cur.next = prev; prev = cur; cur = nxt
        head.next = self.reverse_k_group(cur, k)
        return prev

Remove Nth Node From End of List MEDIUM

class Solution:
    def remove_nth_from_end(self, head, n):
        dummy = ListNode(0, head); fast = slow = dummy
        for _ in range(n): fast = fast.next
        while fast.next:
            fast = fast.next; slow = slow.next
        slow.next = slow.next.next
        return dummy.next

Remove Duplicates from Sorted List II MEDIUM

class Solution:
    def delete_duplicates_ii(self, head):
        dummy = ListNode(0, head); prev = dummy; cur = head
        while cur:
            if cur.next and cur.val == cur.next.val:
                while cur.next and cur.val == cur.next.val: cur = cur.next
                prev.next = cur.next
            else:
                prev = prev.next
            cur = cur.next
        return dummy.next

Rotate List MEDIUM

class Solution:
    def rotate_right(self, head, k):
        if not head or not head.next: return head
        n = 1; tail = head
        while tail.next: tail = tail.next; n += 1
        k %= n
        if k == 0: return head
        tail.next = head                        # circular
        new_tail = head
        for _ in range(n - k - 1): new_tail = new_tail.next
        new_head = new_tail.next; new_tail.next = None
        return new_head

Partition List MEDIUM

class Solution:
    def partition(self, head, x):
        less = ListNode(0); greater = ListNode(0)
        lt, gt = less, greater
        while head:
            if head.val < x: lt.next = head; lt = lt.next
            else: gt.next = head; gt = gt.next
            head = head.next
        gt.next = None; lt.next = greater.next
        return less.next

LRU Cache MEDIUM

An OrderedDict gives O(1) get/put with recency tracking (move_to_end).

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict(); self.cap = capacity
    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.cap:
            self.cache.popitem(last=False)

Binary Tree - General

Maximum Depth of Binary Tree EASY

class Solution:
    def max_depth(self, root):
        if not root: return 0
        return 1 + max(self.max_depth(root.left), self.max_depth(root.right))

Same Tree EASY

class Solution:
    def is_same_tree(self, p, q):
        if not p and not q: return True
        if not p or not q or p.val != q.val: return False
        return self.is_same_tree(p.left, q.left) and self.is_same_tree(p.right, q.right)

Invert Binary Tree EASY

class Solution:
    def invert_tree(self, root):
        if root:
            root.left, root.right = self.invert_tree(root.right), self.invert_tree(root.left)
        return root

Symmetric Tree EASY

class Solution:
    def is_symmetric(self, root):
        def mirror(a, b):
            if not a and not b: return True
            if not a or not b or a.val != b.val: return False
            return mirror(a.left, b.right) and mirror(a.right, b.left)
        return mirror(root, root)

Construct Tree from Preorder & Inorder MEDIUM

First preorder value is the root; its index in inorder splits left/right. O(n).

class Solution:
    def build_tree(self, preorder, inorder):
        idx = {v: i for i, v in enumerate(inorder)}
        pre = [0]
        def build(lo, hi):
            if lo > hi: return None
            val = preorder[pre[0]]; pre[0] += 1
            node = TreeNode(val); mid = idx[val]
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node
        return build(0, len(inorder) - 1)

Construct Tree from Inorder & Postorder MEDIUM

class Solution:
    def build_tree_post(self, inorder, postorder):
        idx = {v: i for i, v in enumerate(inorder)}
        post = [len(postorder) - 1]
        def build(lo, hi):
            if lo > hi: return None
            val = postorder[post[0]]; post[0] -= 1
            node = TreeNode(val); mid = idx[val]
            node.right = build(mid + 1, hi)     # right before left (postorder reversed)
            node.left = build(lo, mid - 1)
            return node
        return build(0, len(inorder) - 1)

Populating Next Right Pointers II MEDIUM

Use the already-linked current level to build the next level's next chain. O(n), O(1) extra.

class Solution:
    def connect(self, root):
        head = root
        while head:
            dummy = Node(0); tail = dummy; cur = head
            while cur:
                if cur.left: tail.next = cur.left; tail = tail.next
                if cur.right: tail.next = cur.right; tail = tail.next
                cur = cur.next
            head = dummy.next
        return root

Flatten Binary Tree to Linked List MEDIUM

class Solution:
    def flatten(self, root):
        node = root
        while node:
            if node.left:
                rightmost = node.left
                while rightmost.right: rightmost = rightmost.right
                rightmost.right = node.right
                node.right = node.left; node.left = None
            node = node.right

Path Sum EASY

class Solution:
    def has_path_sum(self, root, target):
        if not root: return False
        if not root.left and not root.right: return root.val == target
        rem = target - root.val
        return self.has_path_sum(root.left, rem) or self.has_path_sum(root.right, rem)

Sum Root to Leaf Numbers MEDIUM

class Solution:
    def sum_numbers(self, root):
        def dfs(node, cur):
            if not node: return 0
            cur = cur * 10 + node.val
            if not node.left and not node.right: return cur
            return dfs(node.left, cur) + dfs(node.right, cur)
        return dfs(root, 0)

Binary Tree Maximum Path Sum HARD

class Solution:
    def max_path_sum(self, root):
        best = [float("-inf")]
        def gain(node):
            if not node: return 0
            left = max(gain(node.left), 0)
            right = max(gain(node.right), 0)
            best[0] = max(best[0], node.val + left + right)
            return node.val + max(left, right)
        gain(root)
        return best[0]

Binary Search Tree Iterator MEDIUM

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)
    def _push_left(self, node):
        while node:
            self.stack.append(node); node = node.left
    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val
    def hasNext(self):
        return bool(self.stack)

Count Complete Tree Nodes EASY

If left and right heights match, it's a perfect subtree → 2^h − 1. Otherwise recurse. O(log²n).

class Solution:
    def count_nodes(self, root):
        if not root: return 0
        lh = rh = 0; l = r = root
        while l: lh += 1; l = l.left
        while r: rh += 1; r = r.right
        if lh == rh: return (1 << lh) - 1
        return 1 + self.count_nodes(root.left) + self.count_nodes(root.right)

Lowest Common Ancestor of a Binary Tree MEDIUM

class Solution:
    def lowest_common_ancestor(self, root, p, q):
        if not root or root == p or root == q: return root
        left = self.lowest_common_ancestor(root.left, p, q)
        right = self.lowest_common_ancestor(root.right, p, q)
        if left and right: return root
        return left or right

Binary Tree - BFS

Binary Tree Right Side View MEDIUM

from collections import deque

class Solution:
    def right_side_view(self, root):
        if not root: return []
        res = []; queue = deque([root])
        while queue:
            n = len(queue)
            for i in range(n):
                node = queue.popleft()
                if i == n - 1: res.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
        return res

Average of Levels in Binary Tree EASY

from collections import deque

class Solution:
    def average_of_levels(self, root):
        res = []; queue = deque([root])
        while queue:
            n = len(queue); total = 0
            for _ in range(n):
                node = queue.popleft(); total += node.val
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(total / n)
        return res

Binary Tree Level Order Traversal MEDIUM

from collections import deque

class Solution:
    def level_order(self, root):
        if not root: return []
        res = []; 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)
            res.append(level)
        return res

Binary Tree Zigzag Level Order Traversal MEDIUM

from collections import deque

class Solution:
    def zigzag_level_order(self, root):
        if not root: return []
        res = []; queue = deque([root]); ltr = True
        while queue:
            level = deque()
            for _ in range(len(queue)):
                node = queue.popleft()
                if ltr: level.append(node.val)
                else: level.appendleft(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(list(level)); ltr = not ltr
        return res

Binary Search Tree

Minimum Absolute Difference in BST EASY

In-order visits values sorted → the min gap is between adjacent values. O(n).

class Solution:
    def get_minimum_difference(self, root):
        prev = [None]; best = [float("inf")]
        def inorder(node):
            if not node: return
            inorder(node.left)
            if prev[0] is not None:
                best[0] = min(best[0], node.val - prev[0])
            prev[0] = node.val
            inorder(node.right)
        inorder(root)
        return best[0]

Kth Smallest Element in a BST MEDIUM

class Solution:
    def kth_smallest(self, root, k):
        stack = []; node = root
        while stack or node:
            while node:
                stack.append(node); node = node.left
            node = stack.pop(); k -= 1
            if k == 0: return node.val
            node = node.right

Validate Binary Search Tree MEDIUM

class Solution:
    def is_valid_bst(self, root):
        def valid(node, low, high):
            if not node: return True
            if not (low < node.val < high): return False
            return valid(node.left, low, node.val) and valid(node.right, node.val, high)
        return valid(root, float("-inf"), float("inf"))

Graph - General

Number of Islands MEDIUM

class Solution:
    def num_islands(self, grid):
        if not grid: return 0
        count = 0
        def sink(r, c):
            if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] == "1":
                grid[r][c] = "0"
                sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == "1":
                    count += 1; sink(r, c)
        return count

Surrounded Regions MEDIUM

Any 'O' connected to the border survives - mark those first, flip the rest. O(m·n).

class Solution:
    def surrounded(self, board):
        if not board: return
        rows, cols = len(board), len(board[0])
        def mark(r, c):
            if 0 <= r < rows and 0 <= c < cols and board[r][c] == "O":
                board[r][c] = "#"
                mark(r+1, c); mark(r-1, c); mark(r, c+1); mark(r, c-1)
        for r in range(rows): mark(r, 0); mark(r, cols-1)
        for c in range(cols): mark(0, c); mark(rows-1, c)
        for r in range(rows):
            for c in range(cols):
                board[r][c] = "O" if board[r][c] == "#" else "X"

Clone Graph MEDIUM

class Solution:
    def clone_graph(self, node):
        if not node: return None
        clones = {}
        def dfs(n):
            if n in clones: return clones[n]
            copy = Node(n.val); clones[n] = copy
            for nb in n.neighbors:
                copy.neighbors.append(dfs(nb))
            return copy
        return dfs(node)

Evaluate Division MEDIUM

Build a weighted graph (a/b = v, b/a = 1/v); each query is a DFS multiplying edge weights.

from collections import defaultdict

class Solution:
    def calc_equation(self, equations, values, queries):
        graph = defaultdict(dict)
        for (a, b), v in zip(equations, values):
            graph[a][b] = v; graph[b][a] = 1 / v
        def dfs(src, dst, seen):
            if src not in graph or dst not in graph: return -1.0
            if src == dst: return 1.0
            seen.add(src)
            for nb, w in graph[src].items():
                if nb not in seen:
                    res = dfs(nb, dst, seen)
                    if res != -1.0: return w * res
            return -1.0
        return [dfs(a, b, set()) for a, b in queries]

Course Schedule (can finish?) MEDIUM

Detect a cycle in the prereq graph via 3-color DFS. O(V+E).

from collections import defaultdict

class Solution:
    def can_finish(self, num_courses, prerequisites):
        graph = defaultdict(list)
        for a, b in prerequisites: graph[b].append(a)
        state = [0] * num_courses        # 0=unseen, 1=visiting, 2=done
        def dfs(node):
            if state[node] == 1: return False
            if state[node] == 2: return True
            state[node] = 1
            for nb in graph[node]:
                if not dfs(nb): return False
            state[node] = 2
            return True
        return all(dfs(i) for i in range(num_courses))

Course Schedule II (order) MEDIUM

Kahn's topological sort (BFS on in-degrees). O(V+E).

from collections import defaultdict, deque

class Solution:
    def find_order(self, num_courses, prerequisites):
        graph = defaultdict(list); indeg = [0] * num_courses
        for a, b in prerequisites:
            graph[b].append(a); indeg[a] += 1
        queue = deque(i for i in range(num_courses) if indeg[i] == 0)
        order = []
        while queue:
            node = queue.popleft(); order.append(node)
            for nb in graph[node]:
                indeg[nb] -= 1
                if indeg[nb] == 0: queue.append(nb)
        return order if len(order) == num_courses else []

Graph - BFS

Snakes and Ladders MEDIUM

from collections import deque

class Solution:
    def snakes_and_ladders(self, board):
        n = len(board)
        def cell(s):
            r, c = divmod(s - 1, n)
            if r % 2: c = n - 1 - c
            return board[n - 1 - r][c]
        queue = deque([(1, 0)]); seen = {1}
        while queue:
            s, moves = queue.popleft()
            if s == n * n: return moves
            for nxt in range(s + 1, min(s + 6, n * n) + 1):
                dest = cell(nxt)
                if dest != -1: nxt = dest
                if nxt not in seen:
                    seen.add(nxt); queue.append((nxt, moves + 1))
        return -1

Minimum Genetic Mutation MEDIUM

from collections import deque

class Solution:
    def min_mutation(self, start, end, bank):
        bank = set(bank)
        queue = deque([(start, 0)]); seen = {start}
        while queue:
            gene, steps = queue.popleft()
            if gene == end: return steps
            for i in range(len(gene)):
                for ch in "ACGT":
                    mut = gene[:i] + ch + gene[i+1:]
                    if mut in bank and mut not in seen:
                        seen.add(mut); queue.append((mut, steps + 1))
        return -1

Word Ladder HARD

from collections import deque

class Solution:
    def ladder_length(self, begin, end, word_list):
        words = set(word_list)
        if end not in words: return 0
        queue = deque([(begin, 1)]); seen = {begin}
        while queue:
            word, length = queue.popleft()
            if word == end: return length
            for i in range(len(word)):
                for ch in "abcdefghijklmnopqrstuvwxyz":
                    nxt = word[:i] + ch + word[i+1:]
                    if nxt in words and nxt not in seen:
                        seen.add(nxt); queue.append((nxt, length + 1))
        return 0

Trie

Implement Trie (Prefix Tree) MEDIUM

class Trie:
    def __init__(self): self.root = {}
    def insert(self, word):
        node = self.root
        for c in word: node = node.setdefault(c, {})
        node["$"] = True
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node: return False
            node = node[c]
        return "$" in node
    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node: return False
            node = node[c]
        return True

Design Add and Search Words (wildcards) MEDIUM

class WordDictionary:
    def __init__(self): self.root = {}
    def addWord(self, word):
        node = self.root
        for c in word: node = node.setdefault(c, {})
        node["$"] = True
    def search(self, word):
        def dfs(node, i):
            if i == len(word): return "$" in node
            c = word[i]
            if c == ".":
                return any(dfs(child, i+1) for k, child in node.items() if k != "$")
            return c in node and dfs(node[c], i+1)
        return dfs(self.root, 0)

Word Search II HARD

Put all words in a trie, then DFS the board once, pruning by trie paths.

class Solution:
    def find_words(self, board, words):
        trie = {}
        for w in words:
            node = trie
            for c in w: node = node.setdefault(c, {})
            node["$"] = w
        res = []; rows, cols = len(board), len(board[0])
        def dfs(r, c, node):
            ch = board[r][c]
            if ch not in node: return
            nxt = node[ch]
            if "$" in nxt: res.append(nxt.pop("$"))
            board[r][c] = "#"
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r+dr, c+dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#":
                    dfs(nr, nc, nxt)
            board[r][c] = ch
        for r in range(rows):
            for c in range(cols):
                dfs(r, c, trie)
        return res

Backtracking

Letter Combinations of a Phone Number MEDIUM

class Solution:
    def letter_combinations(self, digits):
        if not digits: return []
        m = {"2":"abc","3":"def","4":"ghi","5":"jkl",
             "6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
        res = [""]
        for d in digits:
            res = [prefix + c for prefix in res for c in m[d]]
        return res

Combinations MEDIUM

class Solution:
    def combine(self, n, k):
        res = []
        def backtrack(start, path):
            if len(path) == k:
                res.append(path[:]); return
            for i in range(start, n + 1):
                path.append(i)
                backtrack(i + 1, path)
                path.pop()
        backtrack(1, [])
        return res

Permutations MEDIUM

class Solution:
    def permute(self, nums):
        res = []
        def backtrack(path, remaining):
            if not remaining:
                res.append(path[:]); return
            for i in range(len(remaining)):
                backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
        backtrack([], nums)
        return res

Combination Sum MEDIUM

class Solution:
    def combination_sum(self, candidates, target):
        res = []
        def backtrack(start, path, remaining):
            if remaining == 0:
                res.append(path[:]); return
            for i in range(start, len(candidates)):
                if candidates[i] <= remaining:
                    path.append(candidates[i])
                    backtrack(i, path, remaining - candidates[i])   # i: reuse allowed
                    path.pop()
        backtrack(0, [], target)
        return res

N-Queens II (count) HARD

class Solution:
    def total_n_queens(self, n):
        cols = set(); diag1 = set(); diag2 = set()
        def place(row):
            if row == n: return 1
            count = 0
            for col in range(n):
                if col in cols or (row+col) in diag1 or (row-col) in diag2: continue
                cols.add(col); diag1.add(row+col); diag2.add(row-col)
                count += place(row + 1)
                cols.discard(col); diag1.discard(row+col); diag2.discard(row-col)
            return count
        return place(0)

Generate Parentheses MEDIUM

class Solution:
    def generate_parenthesis(self, n):
        res = []
        def backtrack(s, open_n, close_n):
            if len(s) == 2 * n:
                res.append(s); return
            if open_n < n: backtrack(s + "(", open_n + 1, close_n)
            if close_n < open_n: backtrack(s + ")", open_n, close_n + 1)
        backtrack("", 0, 0)
        return res

Word Search MEDIUM

class Solution:
    def exist(self, board, word):
        rows, cols = len(board), len(board[0])
        def dfs(r, c, i):
            if i == len(word): return True
            if not (0 <= r < rows and 0 <= c < cols) or board[r][c] != word[i]:
                return False
            board[r][c] = "#"
            found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                     dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
            board[r][c] = word[i]
            return found
        return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Divide & Conquer

Convert Sorted Array to BST EASY

class Solution:
    def sorted_array_to_bst(self, nums):
        def build(lo, hi):
            if lo > hi: return None
            mid = (lo + hi) // 2
            node = TreeNode(nums[mid])
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node
        return build(0, len(nums) - 1)

Sort List (merge sort) MEDIUM

class Solution:
    def sort_list(self, head):
        if not head or not head.next: return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next; fast = fast.next.next
        mid = slow.next; slow.next = None
        left, right = self.sort_list(head), self.sort_list(mid)
        dummy = tail = ListNode(0)
        while left and right:
            if left.val <= right.val: tail.next = left; left = left.next
            else: tail.next = right; right = right.next
            tail = tail.next
        tail.next = left or right
        return dummy.next

Construct Quad Tree MEDIUM

class Solution:
    def construct(self, grid):
        def build(r, c, size):
            if size == 1:
                return Node(grid[r][c] == 1, True, None, None, None, None)
            half = size // 2
            tl = build(r, c, half);        tr = build(r, c + half, half)
            bl = build(r + half, c, half); br = build(r + half, c + half, half)
            if (tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf
                    and tl.val == tr.val == bl.val == br.val):
                return Node(tl.val, True, None, None, None, None)
            return Node(True, False, tl, tr, bl, br)
        return build(0, 0, len(grid))

Merge k Sorted Lists HARD

import heapq

class Solution:
    def merge_k_lists(self, lists):
        heap = []
        for i, node in enumerate(lists):
            if node: heapq.heappush(heap, (node.val, i, node))
        dummy = tail = ListNode(0)
        while heap:
            val, i, node = heapq.heappop(heap)
            tail.next = node; tail = node
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

Kadane's Algorithm

Maximum Subarray MEDIUM

class Solution:
    def max_sub_array(self, nums):
        best = cur = nums[0]
        for n in nums[1:]:
            cur = max(n, cur + n)
            best = max(best, cur)
        return best

Maximum Sum Circular Subarray MEDIUM

Answer is either a normal Kadane max, or total − (minimum subarray), whichever's bigger. Guard the all-negative case.

class Solution:
    def max_subarray_circular(self, nums):
        total = 0
        cur_max = best_max = nums[0]
        cur_min = best_min = nums[0]
        for n in nums:
            cur_max = max(n, cur_max + n); best_max = max(best_max, cur_max)
            cur_min = min(n, cur_min + n); best_min = min(best_min, cur_min)
            total += n
        if best_max < 0: return best_max
        return max(best_max, total - best_min)

Binary Search

Search Insert Position EASY

class Solution:
    def search_insert(self, nums, target):
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target: lo = mid + 1
            else: hi = mid
        return lo

Search a 2D Matrix MEDIUM

Treat the matrix as one sorted array of length rows·cols. O(log(mn)).

class Solution:
    def search_matrix(self, matrix, target):
        rows, cols = len(matrix), len(matrix[0])
        lo, hi = 0, rows * cols - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            val = matrix[mid // cols][mid % cols]
            if val == target: return True
            if val < target: lo = mid + 1
            else: hi = mid - 1
        return False

Find Peak Element MEDIUM

class Solution:
    def find_peak_element(self, nums):
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < nums[mid + 1]: lo = mid + 1
            else: hi = mid
        return lo

Search in Rotated Sorted Array MEDIUM

One half is always sorted - check which, then decide which side to keep. O(log n).

class Solution:
    def search_rotated(self, nums, target):
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target: return mid
            if nums[lo] <= nums[mid]:                # left half sorted
                if nums[lo] <= target < nums[mid]: hi = mid - 1
                else: lo = mid + 1
            else:                                   # right half sorted
                if nums[mid] < target <= nums[hi]: lo = mid + 1
                else: hi = mid - 1
        return -1

Find First and Last Position MEDIUM

import bisect

class Solution:
    def search_range(self, nums, target):
        left = bisect.bisect_left(nums, target)
        if left == len(nums) or nums[left] != target: return [-1, -1]
        right = bisect.bisect_right(nums, target) - 1
        return [left, right]

Find Minimum in Rotated Sorted Array MEDIUM

class Solution:
    def find_min(self, nums):
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]: lo = mid + 1
            else: hi = mid
        return nums[lo]

Median of Two Sorted Arrays HARD

Binary-search a partition of the smaller array so left halves ≤ right halves. O(log(min(m,n))).

class Solution:
    def find_median_sorted_arrays(self, a, b):
        if len(a) > len(b): a, b = b, a
        m, n = len(a), len(b); half = (m + n + 1) // 2
        lo, hi = 0, m
        while lo <= hi:
            i = (lo + hi) // 2; j = half - i
            a_left  = a[i-1] if i > 0 else float("-inf")
            a_right = a[i]   if i < m else float("inf")
            b_left  = b[j-1] if j > 0 else float("-inf")
            b_right = b[j]   if j < n else float("inf")
            if a_left <= b_right and b_left <= a_right:
                if (m + n) % 2: return max(a_left, b_left)
                return (max(a_left, b_left) + min(a_right, b_right)) / 2
            elif a_left > b_right: hi = i - 1
            else: lo = i + 1

Heap

Kth Largest Element in an Array MEDIUM

import heapq

class Solution:
    def find_kth_largest(self, nums, k):
        return heapq.nlargest(k, nums)[-1]

IPO HARD

Greedy: among all affordable projects, always take the most profitable. Max-heap of profits. O(n log n).

import heapq

class Solution:
    def find_maximized_capital(self, k, w, profits, capital):
        projects = sorted(zip(capital, profits))
        heap = []; i = 0
        for _ in range(k):
            while i < len(projects) and projects[i][0] <= w:
                heapq.heappush(heap, -projects[i][1]); i += 1
            if not heap: break
            w -= heapq.heappop(heap)
        return w

Find K Pairs with Smallest Sums MEDIUM

import heapq

class Solution:
    def k_smallest_pairs(self, nums1, nums2, k):
        if not nums1 or not nums2: return []
        heap = []; res = []
        for i in range(min(k, len(nums1))):
            heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))
        while heap and len(res) < k:
            _, i, j = heapq.heappop(heap)
            res.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(heap, (nums1[i] + nums2[j+1], i, j+1))
        return res

Find Median from Data Stream HARD

Two heaps: a max-heap for the lower half, a min-heap for the upper. Median is the top(s). O(log n) per add.

import heapq
class MedianFinder:
    def __init__(self):
        self.small = []   # max-heap (store negatives)
        self.large = []   # min-heap
    def addNum(self, num):
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        if 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 -self.small[0]
        return (-self.small[0] + self.large[0]) / 2

Bit Manipulation

Add Binary EASY

class Solution:
    def add_binary(self, a, b):
        return bin(int(a, 2) + int(b, 2))[2:]

Reverse Bits EASY

class Solution:
    def reverse_bits(self, n):
        result = 0
        for _ in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result

Number of 1 Bits EASY

class Solution:
    def hamming_weight(self, n):
        count = 0
        while n:
            n &= n - 1            # clears the lowest set bit
            count += 1
        return count

Single Number EASY

class Solution:
    def single_number(self, nums):
        result = 0
        for n in nums: result ^= n     # pairs cancel via XOR
        return result

Single Number II (others appear 3×) MEDIUM

class Solution:
    def single_number_ii(self, nums):
        ones = twos = 0
        for n in nums:
            ones = (ones ^ n) & ~twos
            twos = (twos ^ n) & ~ones
        return ones

Bitwise AND of Numbers Range MEDIUM

The result is the common binary prefix of left & right. Shift both right until equal. O(log n).

class Solution:
    def range_bitwise_and(self, left, right):
        shift = 0
        while left < right:
            left >>= 1; right >>= 1; shift += 1
        return left << shift

Math

Palindrome Number EASY

class Solution:
    def is_palindrome_number(self, x):
        if x < 0: return False
        return str(x) == str(x)[::-1]

Plus One EASY

class Solution:
    def plus_one(self, digits):
        for i in range(len(digits) - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1; return digits
            digits[i] = 0
        return [1] + digits

Factorial Trailing Zeroes MEDIUM

Count factors of 5 in n! (each pairs with a 2 to make a trailing zero). O(log n).

class Solution:
    def trailing_zeroes(self, n):
        count = 0
        while n:
            n //= 5; count += n
        return count

Sqrt(x) EASY

class Solution:
    def my_sqrt(self, x):
        lo, hi = 0, x
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x: lo = mid + 1
            else: hi = mid - 1
        return hi

Pow(x, n) - fast exponentiation MEDIUM

class Solution:
    def my_pow(self, x, n):
        if n < 0: x = 1 / x; n = -n
        result = 1
        while n:
            if n & 1: result *= x
            x *= x; n >>= 1
        return result

Max Points on a Line HARD

from math import gcd

class Solution:
    def max_points(self, points):
        if len(points) <= 2: return len(points)
        best = 0
        for i in range(len(points)):
            slopes = {}
            for j in range(i + 1, len(points)):
                dx = points[j][0] - points[i][0]
                dy = points[j][1] - points[i][1]
                g = gcd(dx, dy) or 1
                slope = (dx // g, dy // g)
                slopes[slope] = slopes.get(slope, 1) + 1
                best = max(best, slopes[slope])
        return best

1-D Dynamic Programming

Climbing Stairs EASY

class Solution:
    def climb_stairs(self, n):
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a

House Robber MEDIUM

class Solution:
    def rob(self, nums):
        prev = curr = 0
        for n in nums:
            prev, curr = curr, max(curr, prev + n)
        return curr

Word Break MEDIUM

class Solution:
    def word_break(self, s, word_dict):
        words = set(word_dict); n = len(s)
        dp = [False] * (n + 1); dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True; break
        return dp[n]

Coin Change MEDIUM

class Solution:
    def coin_change(self, coins, amount):
        dp = [0] + [float("inf")] * amount
        for a in range(1, amount + 1):
            for c in coins:
                if c <= a:
                    dp[a] = min(dp[a], dp[a - c] + 1)
        return dp[amount] if dp[amount] != float("inf") else -1

Longest Increasing Subsequence MEDIUM

Patience sorting: keep the smallest tail for each length. O(n log n).

import bisect

class Solution:
    def length_of_lis(self, nums):
        tails = []
        for n in nums:
            i = bisect.bisect_left(tails, n)
            if i == len(tails): tails.append(n)
            else: tails[i] = n
        return len(tails)

Multidimensional DP

Triangle MEDIUM

class Solution:
    def minimum_total(self, triangle):
        dp = triangle[-1][:]
        for row in range(len(triangle) - 2, -1, -1):
            for i in range(len(triangle[row])):
                dp[i] = triangle[row][i] + min(dp[i], dp[i + 1])
        return dp[0]

Minimum Path Sum MEDIUM

class Solution:
    def min_path_sum(self, grid):
        rows, cols = len(grid), len(grid[0])
        for r in range(rows):
            for c in range(cols):
                if r == 0 and c == 0: continue
                up = grid[r-1][c] if r > 0 else float("inf")
                left = grid[r][c-1] if c > 0 else float("inf")
                grid[r][c] += min(up, left)
        return grid[-1][-1]

Unique Paths II (obstacles) MEDIUM

class Solution:
    def unique_paths_with_obstacles(self, grid):
        cols = len(grid[0])
        dp = [0] * cols; dp[0] = 1
        for row in grid:
            for c in range(cols):
                if row[c] == 1: dp[c] = 0
                elif c > 0: dp[c] += dp[c - 1]
        return dp[-1]

Longest Palindromic Substring MEDIUM

Expand around each center (odd and even length). O(n²).

class Solution:
    def longest_palindrome(self, s):
        start = end = 0
        def expand(l, r):
            while l >= 0 and r < len(s) and s[l] == s[r]:
                l -= 1; r += 1
            return l + 1, r - 1
        for i in range(len(s)):
            for l, r in (expand(i, i), expand(i, i + 1)):
                if r - l > end - start: start, end = l, r
        return s[start:end + 1]

Interleaving String MEDIUM

class Solution:
    def is_interleave(self, s1, s2, s3):
        if len(s1) + len(s2) != len(s3): return False
        dp = [False] * (len(s2) + 1); dp[0] = True
        for j in range(1, len(s2) + 1):
            dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
        for i in range(1, len(s1) + 1):
            dp[0] = dp[0] and s1[i-1] == s3[i-1]
            for j in range(1, len(s2) + 1):
                dp[j] = ((dp[j] and s1[i-1] == s3[i+j-1]) or
                         (dp[j-1] and s2[j-1] == s3[i+j-1]))
        return dp[-1]

Edit Distance MEDIUM

class Solution:
    def min_distance(self, word1, word2):
        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]

Best Time to Buy and Sell Stock III (2 txns) HARD

class Solution:
    def max_profit_iii(self, prices):
        buy1 = buy2 = float("-inf"); sell1 = sell2 = 0
        for p in prices:
            buy1 = max(buy1, -p)
            sell1 = max(sell1, buy1 + p)
            buy2 = max(buy2, sell1 - p)
            sell2 = max(sell2, buy2 + p)
        return sell2

Best Time to Buy and Sell Stock IV (k txns) HARD

class Solution:
    def max_profit_iv(self, k, prices):
        if not prices: return 0
        if k >= len(prices) // 2:               # unlimited → grab every rise
            return sum(max(0, prices[i] - prices[i-1]) for i in range(1, len(prices)))
        buy = [float("-inf")] * (k + 1); sell = [0] * (k + 1)
        for p in prices:
            for j in range(1, k + 1):
                buy[j] = max(buy[j], sell[j-1] - p)
                sell[j] = max(sell[j], buy[j] + p)
        return sell[k]

Maximal Square MEDIUM

dp[r][c] = side of the largest all-1 square ending at (r,c) = 1 + min of its top/left/diagonal. O(m·n).

class Solution:
    def maximal_square(self, matrix):
        if not matrix: return 0
        rows, cols = len(matrix), len(matrix[0])
        dp = [[0] * (cols + 1) for _ in range(rows + 1)]
        best = 0
        for r in range(1, rows + 1):
            for c in range(1, cols + 1):
                if matrix[r-1][c-1] == "1":
                    dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])
                    best = max(best, dp[r][c])
        return best * best

🗣️ Behavioral, projects & interview flow

Coding is only half the interview. A typical CS interview runs intro → resume/projects → coding → behavioral → your questions. These parts are free here because they win (or lose) you offers just as often as the algorithm does.

Situation → Task → Action → Result. Set the scene in a sentence, say what you were responsible for, explain what you specifically did, then finish with a concrete (ideally measurable) result. Aim for ~90 seconds.

"What does success look like in the first 90 days?" · "How does the team handle code review and testing?" · "What's the biggest technical challenge the team is facing right now?" · "How do you support growth for early-career engineers?" Asking nothing signals low interest - always ask at least two.

🎓 CS fundamentals - the questions interviewers actually ask

Crisp, correct answers to the conceptual questions that come up constantly (languages, OOP, memory/OS, databases, architecture & process). Free to read - tap any question.