Data Structures & Algorithms

Arrays Contiguous memory, O(1) access by index. Best for sequential data with known size.

Linked Lists Nodes with pointers. O(1) insert/delete at head, O(n) search. Singly vs Doubly linked.

Stacks LIFO. Operations: push, pop, peek. Use cases: undo/redo, call stack, DFS.

Queues FIFO. Operations: enqueue, dequeue. Use cases: BFS, task scheduling, print queues.

Hash Tables Key-value pairs with O(1) average access. Collision handling: chaining, open addressing.

Trees Hierarchical structure. Binary Tree, BST (O(log n) search), AVL, Red-Black, Trie.

Heaps Complete binary tree. Min-Heap / Max-Heap. Priority Queue implementation.

Graphs Vertices + Edges. Directed/Undirected, Weighted/Unweighted. Adjacency list vs matrix.

Sorting
• Bubble Sort O(n²) educational
• Merge Sort O(n log n) stable, divide and conquer
• Quick Sort O(n log n) avg in-place, partition-based
• Heap Sort O(n log n) uses heap structure
• Counting / Radix Sort O(n) non-comparison based

Searching
• Linear Search O(n)
• Binary Search O(log n) requires sorted data

Graph Traversal
• BFS (Breadth-First Search) level by level, shortest path in unweighted
• DFS (Depth-First Search) recursive/iterative, cycle detection

Shortest Path
• Dijkstra's O((V+E) log V) non-negative weights
• Bellman-Ford O(VE) handles negative weights
• Floyd-Warshall O(V³) all-pairs shortest path

Dynamic Programming
• Memoization (top-down) vs Tabulation (bottom-up)
• Classic problems: Fibonacci, Knapsack, LCS, Coin Change, Edit Distance

Big O Notation measures worst-case time/space complexity.

Space Complexity memory used relative to input size. Recursive calls add to call stack.

Two Pointers for sorted arrays, palindrome checks, container problems.

Sliding Window for subarray/substring problems with variable or fixed window size.

Fast & Slow Pointers cycle detection in linked lists (Floyd's algorithm).

Binary Search on Answer when answer lies in a monotonic search space.

Backtracking explore all possibilities with pruning. Used in N-Queens, Sudoku, permutations.

Union-Find (Disjoint Set) for connectivity problems, Kruskal's MST.

Monotonic Stack for next greater element, histogram problems.

# Two Sum O(n) with hash map
def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i

# Longest Substring Without Repeating Characters O(n) sliding window def length_of_longest_substring(s): char_index = {} left = max_len = 0 for right, char in enumerate(s): if char in char_index and char_index[char] >= left: left = char_index[char] + 1 char_index[char] = right max_len = max(max_len, right - left + 1) return max_len

# Binary Search O(log n) def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1

# Merge Sort O(n log n) stable def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right)

def merge(left, right): result, i, j = [], 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]); i += 1 else: result.append(right[j]); j += 1 return result + left[i:] + right[j:]

# LRU Cache O(1) get/put with OrderedDict from collections import OrderedDict

class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict()

def get(self, key): if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key]

def put(self, key, value): if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) ```