Data Structures & Algorithms

def factorial(n):
    """
    5! = 5 × 4 × 3 × 2 × 1 = 120
    
    Notice: 5! = 5 × 4!
    So: factorial(5) = 5 × factorial(4)
    """
    # Base case: stop when n is 0 or 1
    if n <= 1:
        return 1
    
    # Recursive case: n × (n-1)!
    return n * factorial(n - 1)

print(factorial(5))  # 120

# How it works:
# factorial(5) = 5 × factorial(4)
# factorial(4) = 4 × factorial(3)
# factorial(3) = 3 × factorial(2)
# factorial(2) = 2 × factorial(1)
# factorial(1) = 1  ← BASE CASE reached!
# Unwind: 2×1=2, 3×2=6, 4×6=24, 5×24=120

def fibonacci(n):
    """
    Sequence: 0, 1, 1, 2, 3, 5, 8, 13...
    Each number = sum of previous two
    """
    # Base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # fib(n) = fib(n-1) + fib(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(6))  # 8 (sequence: 0,1,1,2,3,5,8)

def fib_memo(n, memo={}):
    """
    Store results in 'memo' dictionary
    Before calculating, check if already done
    """
    if n in memo:
        return memo[n]  # Already calculated!
    
    if n <= 1:
        return n
    
    # Calculate and STORE before returning
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print(fib_memo(50))  # Now O(n) instead of O(2ⁿ)!
# Without memo: would take years
# With memo: instant!

def fib_tab(n):
    """
    Build up from base cases
    Fill a table from start to n
    """
    if n <= 1:
        return n
    
    # Create table
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    
    # Fill bottom-up
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

print(fib_tab(50))  # Also O(n)!

def knapsack(weights, values, capacity):
    """
    Given items with weights and values,
    maximize value within weight capacity.
    Each item: take it or leave it (0/1)
    """
    n = len(weights)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: Don't take item i
            dp[i][w] = dp[i - 1][w]
            
            # Option 2: Take item i (if it fits)
            if weights[i - 1] <= w:
                take = values[i - 1] + dp[i - 1][w - weights[i - 1]]
                dp[i][w] = max(dp[i][w], take)
    
    return dp[n][capacity]

weights = [1, 2, 3]
values = [6, 10, 12]
print(knapsack(weights, values, 5))  # 22

def activity_selection(activities):
    """
    activities = [(start, end), ...]
    Maximize non-overlapping activities
    
    Greedy: Always pick earliest ending activity
    """
    # Sort by end time
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]
    last_end = activities[0][1]
    
    for start, end in activities[1:]:
        if start >= last_end:  # Doesn't overlap!
            selected.append((start, end))
            last_end = end
    
    return selected

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
print(activity_selection(activities))
# [(1, 4), (5, 7), (8, 9)] - 3 activities!

def permutations(arr):
    result = []
    
    def backtrack(start):
        if start == len(arr):
            result.append(arr[:])  # Found one!
            return
        
        for i in range(start, len(arr)):
            arr[start], arr[i] = arr[i], arr[start]  # Try
            backtrack(start + 1)
            arr[start], arr[i] = arr[i], arr[start]  # Undo
    
    backtrack(0)
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]]

import heapq

def dijkstra(graph, start):
    """
    graph = {node: [(neighbor, weight), ...]}
    Returns shortest distance to each node
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    
    while pq:
        dist, node = heapq.heappop(pq)
        
        if dist > distances[node]:
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    
    return distances

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)]
}
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

import heapq

def prim(graph, start):
    """Returns edges in MST"""
    visited = set([start])
    edges = [(weight, start, neighbor) 
             for neighbor, weight in graph[start]]
    heapq.heapify(edges)
    mst = []
    
    while edges and len(visited) < len(graph):
        weight, u, v = heapq.heappop(edges)
        
        if v in visited:
            continue
            
        visited.add(v)
        mst.append((u, v, weight))
        
        for neighbor, w in graph[v]:
            if neighbor not in visited:
                heapq.heappush(edges, (w, v, neighbor))
    
    return mst

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[px] = py
            return True
        return False

def kruskal(n, edges):
    """
    edges = [(weight, u, v), ...]
    Returns MST edges
    """
    edges.sort()  # Sort by weight
    uf = UnionFind(n)
    mst = []
    
    for weight, u, v in edges:
        if uf.union(u, v):  # If no cycle
            mst.append((u, v, weight))
            if len(mst) == n - 1:
                break
    
    return mst

def bellman_ford(n, edges, start):
    """
    n = number of vertices
    edges = [(u, v, weight), ...]
    Handles negative weights!
    """
    dist = [float('inf')] * n
    dist[start] = 0
    
    # Relax ALL edges (n-1) times
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # Check for negative weight cycles
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            print("Negative weight cycle detected!")
            return None
    
    return dist

# Dynamic Programming (Top-Down Memoization)
memo = {}
def fib(n):
    if n <= 1: return n
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

# Backtracking Pattern
def backtrack(path, options):
    if is_complete(path):
        result.append(path[:])
        return
        
    for option in options:
        if is_valid(option):
            path.append(option)      # Choose
            backtrack(path, options) # Explore
            path.pop()               # Un-choose