Expert Problem Solving
Master the most challenging algorithmic problems with advanced techniques and sophisticated solutions
Level 5: Expert Interview Preparation - Expert Problem Solving
Hard Dynamic Programming Variants
Expert-level DP problems involve complex state spaces, multiple dimensions, optimization with constraints, and advanced techniques like digit DP and DP on trees/graphs.
🧩 Real-Life Analogy:
Think of planning a complex multi-city business trip with budget constraints, time limits, and varying costs. You need to consider multiple factors simultaneously and find the optimal path. Hard DP problems require similar multi-dimensional thinking.
TypeScript
// Digit DP: Count numbers with specific properties
function countNumbersWithProperty(n: string): number {
const digits = n.split('').map(Number);
const memo = new Map();
function dp(pos: number, tight: boolean, started: boolean, sum: number): number {
if (pos === digits.length) {
return started ? (sum % 3 === 0 ? 1 : 0) : 0;
}
const key = `${pos}-${tight}-${started}-${sum}`;
if (memo.has(key)) return memo.get(key)!;
const limit = tight ? digits[pos] : 9;
let result = 0;
for (let digit = 0; digit <= limit; digit++) {
const newTight = tight && (digit === limit);
const newStarted = started || (digit > 0);
const newSum = sum + digit;
result += dp(pos + 1, newTight, newStarted, newSum);
}
memo.set(key, result);
return result;
}
return dp(0, true, false, 0);
}
// DP on Trees: Maximum sum with no adjacent nodes
class TreeNode {
val: number;
children: TreeNode[];
constructor(val: number) {
this.val = val;
this.children = [];
}
}
function robTree(root: TreeNode | null): number {
if (!root) return 0;
function dfs(node: TreeNode | null): [number, number] {
if (!node) return [0, 0];
let withoutCurrent = 0;
let withCurrent = node.val;
for (const child of node.children) {
const [childWithout, childWith] = dfs(child);
withoutCurrent += Math.max(childWithout, childWith);
withCurrent += childWithout;
}
return [withoutCurrent, withCurrent];
}
const [without, with_] = dfs(root);
return Math.max(without, with_);
}
// Bitmask DP: Traveling Salesman Problem
function tsp(graph: number[][]): number {
const n = graph.length;
const memo = Array(1 << n).fill(null).map(() => Array(n).fill(-1));
function dp(mask: number, pos: number): number {
if (mask === (1 << n) - 1) {
return graph[pos][0]; // Return to start
}
if (memo[mask][pos] !== -1) {
return memo[mask][pos];
}
let result = Infinity;
for (let city = 0; city < n; city++) {
if (!(mask & (1 << city))) {
const newMask = mask | (1 << city);
const cost = graph[pos][city] + dp(newMask, city);
result = Math.min(result, cost);
}
}
memo[mask][pos] = result;
return result;
}
return dp(1, 0); // Start from city 0
}
// Matrix Chain Multiplication with optimal parenthesization
function matrixChainOrder(dimensions: number[]): [number, string] {
const n = dimensions.length - 1;
const dp = Array(n).fill(null).map(() => Array(n).fill(0));
const split = Array(n).fill(null).map(() => Array(n).fill(0));
// l is chain length
for (let l = 2; l <= n; l++) {
for (let i = 0; i <= n - l; i++) {
const j = i + l - 1;
dp[i][j] = Infinity;
for (let k = i; k < j; k++) {
const cost = dp[i][k] + dp[k + 1][j] +
dimensions[i] * dimensions[k + 1] * dimensions[j + 1];
if (cost < dp[i][j]) {
dp[i][j] = cost;
split[i][j] = k;
}
}
}
}
function buildParentheses(i: number, j: number): string {
if (i === j) return `M${i}`;
return `(${buildParentheses(i, split[i][j])} * ${buildParentheses(split[i][j] + 1, j)})`;
}
return [dp[0][n - 1], buildParentheses(0, n - 1)];
}
// Advanced DP: Edit Distance with operations cost
function editDistanceWithCosts(s1: string, s2: string,
insertCost: number, deleteCost: number, replaceCost: number): number {
const m = s1.length, n = s2.length;
const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
// Initialize base cases
for (let i = 0; i <= m; i++) {
dp[i][0] = i * deleteCost;
}
for (let j = 0; j <= n; j++) {
dp[0][j] = j * insertCost;
}
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i - 1] === s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(
dp[i - 1][j] + deleteCost, // Delete
dp[i][j - 1] + insertCost, // Insert
dp[i - 1][j - 1] + replaceCost // Replace
);
}
}
}
return dp[m][n];
}
Python
from functools import lru_cache
from typing import List, Tuple
# Digit DP: Count numbers with specific properties
def count_numbers_with_property(n: str) -> int:
digits = [int(d) for d in n]
@lru_cache(None)
def dp(pos: int, tight: bool, started: bool, digit_sum: int) -> int:
if pos == len(digits):
return 1 if started and digit_sum % 3 == 0 else 0
limit = digits[pos] if tight else 9
result = 0
for digit in range(limit + 1):
new_tight = tight and (digit == limit)
new_started = started or (digit > 0)
new_sum = digit_sum + digit
result += dp(pos + 1, new_tight, new_started, new_sum)
return result
return dp(0, True, False, 0)
# DP on Trees: Maximum sum with no adjacent nodes
class TreeNode:
def __init__(self, val=0):
self.val = val
self.children = []
def rob_tree(root: TreeNode) -> int:
def dfs(node):
if not node:
return (0, 0) # (without_current, with_current)
without_current = 0
with_current = node.val
for child in node.children:
child_without, child_with = dfs(child)
without_current += max(child_without, child_with)
with_current += child_without
return (without_current, with_current)
if not root:
return 0
without, with_node = dfs(root)
return max(without, with_node)
# Bitmask DP: Traveling Salesman Problem
def tsp(graph: List[List[int]]) -> int:
n = len(graph)
memo = {}
def dp(mask: int, pos: int) -> int:
if mask == (1 << n) - 1:
return graph[pos][0] # Return to start
if (mask, pos) in memo:
return memo[(mask, pos)]
result = float('inf')
for city in range(n):
if not (mask & (1 << city)):
new_mask = mask | (1 << city)
cost = graph[pos][city] + dp(new_mask, city)
result = min(result, cost)
memo[(mask, pos)] = result
return result
return dp(1, 0) # Start from city 0
# Matrix Chain Multiplication with optimal parenthesization
def matrix_chain_order(dimensions: List[int]) -> Tuple[int, str]:
n = len(dimensions) - 1
dp = [[0] * n for _ in range(n)]
split = [[0] * n for _ in range(n)]
# l is chain length
for l in range(2, n + 1):
for i in range(n - l + 1):
j = i + l - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = (dp[i][k] + dp[k + 1][j] +
dimensions[i] * dimensions[k + 1] * dimensions[j + 1])
if cost < dp[i][j]:
dp[i][j] = cost
split[i][j] = k
def build_parentheses(i: int, j: int) -> str:
if i == j:
return f"M{i}"
return f"({build_parentheses(i, split[i][j])} * {build_parentheses(split[i][j] + 1, j)})"
return dp[0][n - 1], build_parentheses(0, n - 1)
# Advanced DP: Edit Distance with operations cost
def edit_distance_with_costs(s1: str, s2: str,
insert_cost: int, delete_cost: int, replace_cost: int) -> int:
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# Initialize base cases
for i in range(m + 1):
dp[i][0] = i * delete_cost
for j in range(n + 1):
dp[0][j] = j * insert_cost
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + delete_cost, # Delete
dp[i][j - 1] + insert_cost, # Insert
dp[i - 1][j - 1] + replace_cost # Replace
)
return dp[m][n]
# DP with Convex Hull Trick: Optimize line intersection queries
class ConvexHullTrick:
def __init__(self):
self.lines = [] # (slope, intercept, id)
def bad(self, l1, l2, l3):
# Check if l2 is redundant
return ((l3[1] - l1[1]) * (l1[0] - l2[0]) <=
(l2[1] - l1[1]) * (l1[0] - l3[0]))
def add_line(self, slope, intercept, line_id=0):
new_line = (slope, intercept, line_id)
while (len(self.lines) >= 2 and
self.bad(self.lines[-2], self.lines[-1], new_line)):
self.lines.pop()
self.lines.append(new_line)
def query(self, x):
if not self.lines:
return float('inf')
# Binary search for best line
left, right = 0, len(self.lines) - 1
while left < right:
mid = (left + right) // 2
val1 = self.lines[mid][0] * x + self.lines[mid][1]
val2 = self.lines[mid + 1][0] * x + self.lines[mid + 1][1]
if val1 > val2:
left = mid + 1
else:
right = mid
line = self.lines[left]
return line[0] * x + line[1]
OCaml
open Printf
(* Digit DP: Count numbers with specific properties *)
let count_numbers_with_property n =
let digits = Array.init (String.length n) (fun i -> int_of_char n.[i] - int_of_char '0') in
let memo = Hashtbl.create 1000 in
let rec dp pos tight started digit_sum =
if pos = Array.length digits then
if started && digit_sum mod 3 = 0 then 1 else 0
else
let key = (pos, tight, started, digit_sum) in
match Hashtbl.find_opt memo key with
| Some result -> result
| None ->
let limit = if tight then digits.(pos) else 9 in
let result = ref 0 in
for digit = 0 to limit do
let new_tight = tight && (digit = limit) in
let new_started = started || (digit > 0) in
let new_sum = digit_sum + digit in
result := !result + dp (pos + 1) new_tight new_started new_sum
done;
Hashtbl.add memo key !result;
!result
in
dp 0 true false 0
(* DP on Trees: Maximum sum with no adjacent nodes *)
type tree_node = {
value: int;
children: tree_node list;
}
let rob_tree root =
let rec dfs node =
match node with
| None -> (0, 0) (* (without_current, with_current) *)
| Some n ->
let without_current = ref 0 in
let with_current = ref n.value in
List.iter (fun child ->
let child_without, child_with = dfs (Some child) in
without_current := !without_current + max child_without child_with;
with_current := !with_current + child_without
) n.children;
(!without_current, !with_current)
in
match root with
| None -> 0
| Some _ ->
let without, with_node = dfs root in
max without with_node
(* Bitmask DP: Traveling Salesman Problem *)
let tsp graph =
let n = Array.length graph in
let memo = Hashtbl.create (1 lsl n * n) in
let rec dp mask pos =
if mask = (1 lsl n) - 1 then
graph.(pos).(0) (* Return to start *)
else
match Hashtbl.find_opt memo (mask, pos) with
| Some result -> result
| None ->
let result = ref max_int in
for city = 0 to n - 1 do
if mask land (1 lsl city) = 0 then (
let new_mask = mask lor (1 lsl city) in
let cost = graph.(pos).(city) + dp new_mask city in
result := min !result cost
)
done;
Hashtbl.add memo (mask, pos) !result;
!result
in
dp 1 0 (* Start from city 0 *)
(* Matrix Chain Multiplication *)
let matrix_chain_order dimensions =
let n = Array.length dimensions - 1 in
let dp = Array.make_matrix n n 0 in
let split = Array.make_matrix n n 0 in
(* l is chain length *)
for l = 2 to n do
for i = 0 to n - l do
let j = i + l - 1 in
dp.(i).(j) <- max_int;
for k = i to j - 1 do
let cost = dp.(i).(k) + dp.(k + 1).(j) +
dimensions.(i) * dimensions.(k + 1) * dimensions.(j + 1) in
if cost < dp.(i).(j) then (
dp.(i).(j) <- cost;
split.(i).(j) <- k
)
done
done
done;
let rec build_parentheses i j =
if i = j then sprintf "M%d" i
else sprintf "(%s * %s)"
(build_parentheses i split.(i).(j))
(build_parentheses (split.(i).(j) + 1) j)
in
(dp.(0).(n - 1), build_parentheses 0 (n - 1))
(* Edit Distance with costs *)
let edit_distance_with_costs s1 s2 insert_cost delete_cost replace_cost =
let m = String.length s1 and n = String.length s2 in
let dp = Array.make_matrix (m + 1) (n + 1) 0 in
(* Initialize base cases *)
for i = 0 to m do
dp.(i).(0) <- i * delete_cost
done;
for j = 0 to n do
dp.(0).(j) <- j * insert_cost
done;
for i = 1 to m do
for j = 1 to n do
if s1.[i - 1] = s2.[j - 1] then
dp.(i).(j) <- dp.(i - 1).(j - 1)
else
dp.(i).(j) <- min (min
(dp.(i - 1).(j) + delete_cost) (* Delete *)
(dp.(i).(j - 1) + insert_cost)) (* Insert *)
(dp.(i - 1).(j - 1) + replace_cost) (* Replace *)
done
done;
dp.(m).(n)
🧠 Advanced DP Techniques:
- Digit DP: Count numbers with specific digit properties
- Bitmask DP: Exponential state spaces using bit manipulation
- DP on Trees: Optimal solutions considering tree structure
- Convex Hull Trick: Optimize linear function queries
- Divide & Conquer DP: Reduce complexity with monotonicity
Complex Graph Algorithms
Advanced graph problems involving flow networks, matching algorithms, strongly connected components, and sophisticated traversal techniques.
🌐 Real-Life Analogy:
Think of managing a complex transportation network during peak hours - you need to handle maximum flow through highways, match drivers to routes optimally, detect traffic circles, and find strongly connected regions. Advanced graph algorithms solve these intricate network problems.
TypeScript
// Ford-Fulkerson Algorithm for Maximum Flow
class MaxFlow {
private graph: number[][];
private rGraph: number[][];
private parent: number[];
private n: number;
constructor(capacity: number[][]) {
this.n = capacity.length;
this.graph = capacity.map(row => [...row]);
this.rGraph = capacity.map(row => [...row]);
this.parent = new Array(this.n);
}
private bfs(source: number, sink: number): boolean {
const visited = new Array(this.n).fill(false);
const queue: number[] = [source];
visited[source] = true;
this.parent[source] = -1;
while (queue.length > 0) {
const u = queue.shift()!;
for (let v = 0; v < this.n; v++) {
if (!visited[v] && this.rGraph[u][v] > 0) {
visited[v] = true;
this.parent[v] = u;
queue.push(v);
if (v === sink) return true;
}
}
}
return false;
}
fordFulkerson(source: number, sink: number): number {
let maxFlow = 0;
while (this.bfs(source, sink)) {
let pathFlow = Infinity;
// Find minimum residual capacity along the path
for (let v = sink; v !== source; v = this.parent[v]) {
const u = this.parent[v];
pathFlow = Math.min(pathFlow, this.rGraph[u][v]);
}
// Add path flow to overall flow
maxFlow += pathFlow;
// Update residual capacities
for (let v = sink; v !== source; v = this.parent[v]) {
const u = this.parent[v];
this.rGraph[u][v] -= pathFlow;
this.rGraph[v][u] += pathFlow;
}
}
return maxFlow;
}
}
// Dinic's Algorithm for Maximum Flow (O(V²E))
class Dinic {
private graph: Map>;
private level: number[];
private iter: number[];
private n: number;
constructor(n: number) {
this.n = n;
this.graph = new Map();
this.level = new Array(n);
this.iter = new Array(n);
for (let i = 0; i < n; i++) {
this.graph.set(i, new Map());
}
}
addEdge(from: number, to: number, capacity: number): void {
this.graph.get(from)!.set(to, (this.graph.get(from)!.get(to) || 0) + capacity);
this.graph.get(to)!.set(from, this.graph.get(to)!.get(from) || 0);
}
private bfs(source: number, sink: number): boolean {
this.level.fill(-1);
this.level[source] = 0;
const queue: number[] = [source];
while (queue.length > 0) {
const v = queue.shift()!;
for (const [to, capacity] of this.graph.get(v)!) {
if (this.level[to] < 0 && capacity > 0) {
this.level[to] = this.level[v] + 1;
queue.push(to);
}
}
}
return this.level[sink] >= 0;
}
private dfs(v: number, sink: number, pushed: number): number {
if (v === sink || pushed === 0) return pushed;
const edges = this.graph.get(v)!;
const edgeList = Array.from(edges.entries());
for (let i = this.iter[v]; i < edgeList.length; i++) {
const [to, capacity] = edgeList[i];
if (this.level[v] + 1 !== this.level[to] || capacity <= 0) {
continue;
}
const tr = this.dfs(to, sink, Math.min(pushed, capacity));
if (tr > 0) {
edges.set(to, capacity - tr);
this.graph.get(to)!.set(v, this.graph.get(to)!.get(v)! + tr);
return tr;
}
}
return 0;
}
maxFlow(source: number, sink: number): number {
let flow = 0;
while (this.bfs(source, sink)) {
this.iter.fill(0);
while (true) {
const pushed = this.dfs(source, sink, Infinity);
if (pushed === 0) break;
flow += pushed;
}
}
return flow;
}
}
// Hungarian Algorithm for Bipartite Matching
class HungarianAlgorithm {
private cost: number[][];
private n: number;
private u: number[];
private v: number[];
private p: number[];
private way: number[];
constructor(cost: number[][]) {
this.n = cost.length;
this.cost = cost.map(row => [...row]);
this.u = new Array(this.n + 1).fill(0);
this.v = new Array(this.n + 1).fill(0);
this.p = new Array(this.n + 1).fill(0);
this.way = new Array(this.n + 1).fill(0);
}
solve(): [number, number[]] {
for (let i = 1; i <= this.n; i++) {
this.p[0] = i;
let j0 = 0;
const minv = new Array(this.n + 1).fill(Infinity);
const used = new Array(this.n + 1).fill(false);
do {
used[j0] = true;
const i0 = this.p[j0];
let delta = Infinity;
let j1 = 0;
for (let j = 1; j <= this.n; j++) {
if (!used[j]) {
const cur = this.cost[i0 - 1][j - 1] - this.u[i0] - this.v[j];
if (cur < minv[j]) {
minv[j] = cur;
this.way[j] = j0;
}
if (minv[j] < delta) {
delta = minv[j];
j1 = j;
}
}
}
for (let j = 0; j <= this.n; j++) {
if (used[j]) {
this.u[this.p[j]] += delta;
this.v[j] -= delta;
} else {
minv[j] -= delta;
}
}
j0 = j1;
} while (this.p[j0] !== 0);
do {
const j1 = this.way[j0];
this.p[j0] = this.p[j1];
j0 = j1;
} while (j0 !== 0);
}
const assignment = new Array(this.n).fill(-1);
for (let j = 1; j <= this.n; j++) {
if (this.p[j] !== 0) {
assignment[this.p[j] - 1] = j - 1;
}
}
return [-this.v[0], assignment];
}
}
Python
from collections import deque, defaultdict
from typing import List, Tuple, Dict
import heapq
# Ford-Fulkerson Algorithm for Maximum Flow
class MaxFlow:
def __init__(self, capacity: List[List[int]]):
self.n = len(capacity)
self.graph = [row[:] for row in capacity]
self.r_graph = [row[:] for row in capacity]
self.parent = [-1] * self.n
def bfs(self, source: int, sink: int) -> bool:
visited = [False] * self.n
queue = deque([source])
visited[source] = True
while queue:
u = queue.popleft()
for v in range(self.n):
if not visited[v] and self.r_graph[u][v] > 0:
visited[v] = True
self.parent[v] = u
queue.append(v)
if v == sink:
return True
return False
def ford_fulkerson(self, source: int, sink: int) -> int:
max_flow = 0
while self.bfs(source, sink):
path_flow = float('inf')
# Find minimum residual capacity along the path
s = sink
while s != source:
path_flow = min(path_flow, self.r_graph[self.parent[s]][s])
s = self.parent[s]
# Add path flow to overall flow
max_flow += path_flow
# Update residual capacities
v = sink
while v != source:
u = self.parent[v]
self.r_graph[u][v] -= path_flow
self.r_graph[v][u] += path_flow
v = self.parent[v]
return max_flow
# Dinic's Algorithm for Maximum Flow
class Dinic:
def __init__(self, n: int):
self.n = n
self.graph = defaultdict(lambda: defaultdict(int))
self.level = [-1] * n
self.iter = [0] * n
def add_edge(self, from_node: int, to_node: int, capacity: int):
self.graph[from_node][to_node] += capacity
self.graph[to_node][from_node] += 0 # reverse edge
def bfs(self, source: int, sink: int) -> bool:
self.level = [-1] * self.n
self.level[source] = 0
queue = deque([source])
while queue:
v = queue.popleft()
for to_node, capacity in self.graph[v].items():
if self.level[to_node] < 0 and capacity > 0:
self.level[to_node] = self.level[v] + 1
queue.append(to_node)
return self.level[sink] >= 0
def dfs(self, v: int, sink: int, pushed: int) -> int:
if v == sink or pushed == 0:
return pushed
edges = list(self.graph[v].items())
for i in range(self.iter[v], len(edges)):
to_node, capacity = edges[i]
if self.level[v] + 1 != self.level[to_node] or capacity <= 0:
continue
tr = self.dfs(to_node, sink, min(pushed, capacity))
if tr > 0:
self.graph[v][to_node] -= tr
self.graph[to_node][v] += tr
return tr
return 0
def max_flow(self, source: int, sink: int) -> int:
flow = 0
while self.bfs(source, sink):
self.iter = [0] * self.n
while True:
pushed = self.dfs(source, sink, float('inf'))
if pushed == 0:
break
flow += pushed
return flow
# Hungarian Algorithm for Bipartite Matching
class HungarianAlgorithm:
def __init__(self, cost_matrix: List[List[int]]):
self.n = len(cost_matrix)
self.cost = [row[:] for row in cost_matrix]
self.u = [0] * (self.n + 1)
self.v = [0] * (self.n + 1)
self.p = [0] * (self.n + 1)
self.way = [0] * (self.n + 1)
def solve(self) -> Tuple[int, List[int]]:
for i in range(1, self.n + 1):
self.p[0] = i
j0 = 0
minv = [float('inf')] * (self.n + 1)
used = [False] * (self.n + 1)
while True:
used[j0] = True
i0 = self.p[j0]
delta = float('inf')
j1 = 0
for j in range(1, self.n + 1):
if not used[j]:
cur = self.cost[i0 - 1][j - 1] - self.u[i0] - self.v[j]
if cur < minv[j]:
minv[j] = cur
self.way[j] = j0
if minv[j] < delta:
delta = minv[j]
j1 = j
for j in range(self.n + 1):
if used[j]:
self.u[self.p[j]] += delta
self.v[j] -= delta
else:
minv[j] -= delta
j0 = j1
if self.p[j0] == 0:
break
while j0 != 0:
j1 = self.way[j0]
self.p[j0] = self.p[j1]
j0 = j1
assignment = [-1] * self.n
for j in range(1, self.n + 1):
if self.p[j] != 0:
assignment[self.p[j] - 1] = j - 1
return -self.v[0], assignment
OCaml
open Printf
(* Ford-Fulkerson Algorithm for Maximum Flow *)
module MaxFlow = struct
type t = {
n: int;
graph: int array array;
r_graph: int array array;
parent: int array;
}
let create capacity =
let n = Array.length capacity in
{
n;
graph = Array.map Array.copy capacity;
r_graph = Array.map Array.copy capacity;
parent = Array.make n (-1);
}
let bfs flow source sink =
let visited = Array.make flow.n false in
let queue = Queue.create () in
Queue.add source queue;
visited.(source) <- true;
flow.parent.(source) <- -1;
let found = ref false in
while not (Queue.is_empty queue) && not !found do
let u = Queue.take queue in
for v = 0 to flow.n - 1 do
if not visited.(v) && flow.r_graph.(u).(v) > 0 then begin
visited.(v) <- true;
flow.parent.(v) <- u;
Queue.add v queue;
if v = sink then found := true
end
done
done;
!found
let ford_fulkerson flow source sink =
let max_flow = ref 0 in
while bfs flow source sink do
let path_flow = ref max_int in
(* Find minimum residual capacity along the path *)
let s = ref sink in
while !s <> source do
let u = flow.parent.(!s) in
path_flow := min !path_flow flow.r_graph.(u).(!s);
s := flow.parent.(!s)
done;
(* Add path flow to overall flow *)
max_flow := !max_flow + !path_flow;
(* Update residual capacities *)
let v = ref sink in
while !v <> source do
let u = flow.parent.(!v) in
flow.r_graph.(u).(!v) <- flow.r_graph.(u).(!v) - !path_flow;
flow.r_graph.(!v).(u) <- flow.r_graph.(!v).(u) + !path_flow;
v := flow.parent.(!v)
done
done;
!max_flow
end
(* Hungarian Algorithm *)
module Hungarian = struct
type t = {
n: int;
cost: int array array;
u: int array;
v: int array;
p: int array;
way: int array;
}
let create cost_matrix =
let n = Array.length cost_matrix in
{
n;
cost = Array.map Array.copy cost_matrix;
u = Array.make (n + 1) 0;
v = Array.make (n + 1) 0;
p = Array.make (n + 1) 0;
way = Array.make (n + 1) 0;
}
let solve hungarian =
for i = 1 to hungarian.n do
hungarian.p.(0) <- i;
let j0 = ref 0 in
let minv = Array.make (hungarian.n + 1) max_int in
let used = Array.make (hungarian.n + 1) false in
while hungarian.p.(!j0) <> 0 do
used.(!j0) <- true;
let i0 = hungarian.p.(!j0) in
let delta = ref max_int in
let j1 = ref 0 in
for j = 1 to hungarian.n do
if not used.(j) then begin
let cur = hungarian.cost.(i0 - 1).(j - 1) - hungarian.u.(i0) - hungarian.v.(j) in
if cur < minv.(j) then begin
minv.(j) <- cur;
hungarian.way.(j) <- !j0
end;
if minv.(j) < !delta then begin
delta := minv.(j);
j1 := j
end
end
done;
for j = 0 to hungarian.n do
if used.(j) then begin
hungarian.u.(hungarian.p.(j)) <- hungarian.u.(hungarian.p.(j)) + !delta;
hungarian.v.(j) <- hungarian.v.(j) - !delta
end else
minv.(j) <- minv.(j) - !delta
done;
j0 := !j1
done;
let j = ref !j0 in
while !j <> 0 do
let j1 = hungarian.way.(!j) in
hungarian.p.(!j) <- hungarian.p.(j1);
j := j1
done
done;
let assignment = Array.make hungarian.n (-1) in
for j = 1 to hungarian.n do
if hungarian.p.(j) <> 0 then
assignment.(hungarian.p.(j) - 1) <- j - 1
done;
(-hungarian.v.(0), assignment)
end
🔗 Advanced Graph Concepts:
- Maximum Flow: Ford-Fulkerson, Dinic's algorithm
- Bipartite Matching: Hungarian algorithm, Hopcroft-Karp
- Network Flow: Min-cost max-flow, circulation
- Strong Components: Tarjan's and Kosaraju's algorithms
- Heavy-Light Decomposition: Tree path queries
| Algorithm | Time Complexity | Space Complexity | Use Case |
|---|---|---|---|
| Ford-Fulkerson | O(E × max_flow) | O(V²) | General maximum flow |
| Dinic's Algorithm | O(V² × E) | O(V + E) | Faster max flow |
| Hungarian Algorithm | O(V³) | O(V²) | Min-cost bipartite matching |
Advanced String Algorithms
Sophisticated string processing techniques including pattern matching, suffix structures, and string compression algorithms.
📚 Real-Life Analogy:
Think of a advanced search engine that can find patterns in billions of documents instantly, detect plagiarism, compress text efficiently, and build indexes for lightning-fast queries. Advanced string algorithms power these capabilities.
🔤 String Algorithm Techniques:
- KMP Algorithm: Linear pattern matching with prefix function
- Z-Algorithm: Linear time string matching
- Suffix Arrays: Space-efficient suffix structure
- Manacher's Algorithm: Linear palindrome detection
- Aho-Corasick: Multiple pattern matching
Geometric Algorithms
Computational geometry algorithms for solving problems involving points, lines, polygons, and higher-dimensional structures.
🎯 Real-Life Analogy:
Think of a GPS navigation system that needs to find the shortest path around obstacles, determine if you're inside a restricted area, or calculate the closest gas station. Geometric algorithms handle these spatial reasoning problems.
📐 Geometric Concepts:
- Convex Hull: Graham scan, gift wrapping
- Line Intersection: Sweep line algorithms
- Point in Polygon: Ray casting, winding number
- Closest Pair: Divide and conquer approach
- Voronoi Diagrams: Spatial partitioning
Ready to excel in interviews?
You've mastered complex problem-solving! Now let's focus on interview excellence and presentation skills.
Continue to Interview Excellence →