Algorithms

📚 Overview

Algorithms are systematic methods for solving problems, measured by:

• Correctness: Produces the correct result
• Efficiency: Time & Space complexity
• Simplicity: Easy to understand and implement

🎯 Two Pointers

Technique using 2 pointers to traverse an array, typically O(n) time and O(1) space.

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None

Use cases:

• Sorted array search
• Reverse array
• Palindrome check

🔍 Binary Search

Search a sorted array in O(log n).

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Variations:

• Find first/last occurrence
• Search in rotated sorted array
• Find minimum in rotated sorted array

🎨 Sliding Window

Solve problems involving contiguous subarrays.

Fixed Size Window

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(len(arr) - k):
        window_sum = window_sum - arr[i] + arr[i + k]
        max_sum = max(max_sum, window_sum)
    return max_sum

Variable Size Window

def min_substring_with_chars(s, chars):
    from collections import Counter
    target = Counter(chars)
    window = Counter()
    formed = required = len(target)
    left = 0
    min_len = float('inf')

    for right, char in enumerate(s):
        window[char] += 1
        if char in target and window[char] == target[char]:
            formed += 1

        while left <= right and formed == required:
            char_left = s[left]
            if right - left + 1 < min_len:
                min_len = right - left + 1

            window[char_left] -= 1
            if char_left in target and window[char_left] < target[char_left]:
                formed -= 1
            left += 1

    return min_len

🏔️ Divide & Conquer

Break a large problem into smaller subproblems.

Classic examples:

• Merge Sort: O(n log n)
• Quick Sort: O(n log n) average
• Binary Search: O(log n)

🧩 Greedy

Choose the local optimum at each step, hoping to reach the global optimum.

# Activity Selection Problem
def activity_selection(activities):
    # 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:
            selected.append((start, end))
            last_end = end
    return selected

When to use:

• Greedy choice property
• Optimal substructure
• Sorting often involved

🔄 Recursion + Backtracking

Solve problems by trying all possibilities.

def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

Common patterns:

• Subsets: 2^n
• Permutations: n!
• Combinations: C(n,k)
• Palindrome partitioning

📊 Dynamic Programming

Optimization by storing subproblem results.

Top-Down (Memoization)

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

Bottom-Up (Tabulation)

def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Classic DP Problems:

Problem	Pattern
Climbing Stairs	Fibonacci
Coin Change	Unbounded Knapsack
Longest Increasing Subsequence	Patience sorting
Longest Common Subsequence	2D DP
Edit Distance	2D DP
House Robber	Include/Exclude

🗺️ Graph Algorithms

BFS (Breadth-First Search)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Use cases: Shortest path in unweighted graph

DFS (Depth-First Search)

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Use cases: Path finding, cycle detection, topological sort

Dijkstra's Algorithm

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    heap = [(0, start)]

    while heap:
        current_dist, node = heapq.heappop(heap)
        if current_dist > distances[node]:
            continue
        for neighbor, weight in graph[node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))
    return distances

❓ Interview Questions

Easy

1. Two Sum - Hash table
2. Valid Palindrome - Two pointers
3. Climbing Stairs - DP

Medium

1. 3Sum - Two pointers
2. Longest Substring Without Repeating Characters - Sliding window
3. Coin Change - DP

Hard

1. Median of Two Sorted Arrays - Binary search
2. Trapping Rain Water - Two pointers
3. N-Queens - Backtracking

🔗 Related Topics

• Data Structures
• System Design - Load Balancing