1. Big O Notation: Analyzing Algorithm Complexity

Big O notation describes how an algorithm's time or space requirements grow as the input size increases. It focuses on the growth rate, ignoring constant factors and lower-order terms. Understanding Big O is the foundation for choosing the right data structures and algorithms.

Big O in Practice

// O(1) — Constant time: same speed regardless of input size
function getFirst(arr: number[]): number {
  return arr[0]; // always one operation
}

// O(log n) — Logarithmic: halves the search space each step
function binarySearch(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// O(n) — Linear: visits every element once
function findMax(arr: number[]): number {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(n²) — Quadratic: nested loops over the same data
function hasDuplicate(arr: number[]): boolean {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(n) with hash set — optimized duplicate check
function hasDuplicateOptimized(arr: number[]): boolean {
  const seen = new Set<number>();
  for (const num of arr) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

2. Arrays: The Fundamental Data Structure

Arrays store elements contiguously in memory, providing O(1) index-based access. They are the most commonly used data structure in most programming languages. JavaScript arrays are dynamic, and Python lists are also implemented as dynamic arrays.

Essential Array Techniques

// Two-pointer technique — find pair that sums to target
function twoSum(sorted: number[], target: number): [number, number] | null {
  let left = 0, right = sorted.length - 1;
  while (left < right) {
    const sum = sorted[left] + sorted[right];
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return null;
}

// Sliding window — max sum subarray of size k
function maxSumSubarray(arr: number[], k: number): number {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i];
  let maxSum = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // slide the window
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

// Prefix sum — range sum queries in O(1)
function buildPrefixSum(arr: number[]): number[] {
  const prefix = [0];
  for (let i = 0; i < arr.length; i++) {
    prefix.push(prefix[i] + arr[i]);
  }
  return prefix;
}
function rangeSum(prefix: number[], left: number, right: number): number {
  return prefix[right + 1] - prefix[left];
}

// Example usage:
const arr = [1, 3, 5, 2, 8, 4];
const prefix = buildPrefixSum(arr);
console.log(rangeSum(prefix, 1, 3)); // 3+5+2 = 10

3. Linked Lists: Flexible Storage for Dynamic Data

A linked list consists of nodes, each containing data and a pointer to the next node. Singly linked lists traverse forward only; doubly linked lists traverse in both directions. Their strength is O(1) insertion and deletion at known positions, but access requires O(n) traversal.

// Singly Linked List implementation
class ListNode<T> {
  val: T;
  next: ListNode<T> | null = null;
  constructor(val: T) { this.val = val; }
}

class SinglyLinkedList<T> {
  head: ListNode<T> | null = null;
  size: number = 0;

  // O(1) — prepend to head
  prepend(val: T): void {
    const node = new ListNode(val);
    node.next = this.head;
    this.head = node;
    this.size++;
  }

  // O(n) — append to tail
  append(val: T): void {
    const node = new ListNode(val);
    if (!this.head) { this.head = node; }
    else {
      let curr = this.head;
      while (curr.next) curr = curr.next;
      curr.next = node;
    }
    this.size++;
  }

  // O(n) — delete first occurrence
  delete(val: T): boolean {
    if (!this.head) return false;
    if (this.head.val === val) {
      this.head = this.head.next;
      this.size--;
      return true;
    }
    let curr = this.head;
    while (curr.next) {
      if (curr.next.val === val) {
        curr.next = curr.next.next;
        this.size--;
        return true;
      }
      curr = curr.next;
    }
    return false;
  }

  // O(n) — convert to array for display
  toArray(): T[] {
    const result: T[] = [];
    let curr = this.head;
    while (curr) {
      result.push(curr.val);
      curr = curr.next;
    }
    return result;
  }
}

// Classic interview problem: reverse a linked list
function reverseList<T>(head: ListNode<T> | null): ListNode<T> | null {
  let prev: ListNode<T> | null = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

// Detect cycle with Floyd's algorithm (fast/slow pointers)
function hasCycle<T>(head: ListNode<T> | null): boolean {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

4. Stacks & Queues: Constrained but Powerful Linear Structures

Stacks and queues are linear data structures with access restrictions. Stacks follow LIFO (Last In, First Out), queues follow FIFO (First In, First Out). These constraints make them extremely efficient and useful for specific scenarios.

Stack Implementation and Applications

// Stack implementation
class Stack<T> {
  private items: T[] = [];

  push(item: T): void { this.items.push(item); }     // O(1)
  pop(): T | undefined { return this.items.pop(); }   // O(1)
  peek(): T | undefined { return this.items[this.items.length - 1]; }
  isEmpty(): boolean { return this.items.length === 0; }
  get size(): number { return this.items.length; }
}

// Application: validate balanced parentheses
function isValidParentheses(s: string): boolean {
  const stack = new Stack<string>();
  const pairs: Record<string, string> = {
    ")": "(", "]": "[", "}": "{"
  };
  for (const char of s) {
    if ("([{".includes(char)) {
      stack.push(char);
    } else if (pairs[char]) {
      if (stack.isEmpty() || stack.pop() !== pairs[char]) {
        return false;
      }
    }
  }
  return stack.isEmpty();
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("({[}])"));  // false

// Application: evaluate Reverse Polish Notation (postfix)
function evalRPN(tokens: string[]): number {
  const stack = new Stack<number>();
  for (const token of tokens) {
    if ("+-*/".includes(token)) {
      const b = stack.pop()!, a = stack.pop()!;
      switch (token) {
        case "+": stack.push(a + b); break;
        case "-": stack.push(a - b); break;
        case "*": stack.push(a * b); break;
        case "/": stack.push(Math.trunc(a / b)); break;
      }
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop()!;
}
// "3 4 + 2 *" = (3 + 4) * 2 = 14
console.log(evalRPN(["3", "4", "+", "2", "*"])); // 14

Queue Implementation and Applications

// Queue implementation (using linked list for O(1) dequeue)
class Queue<T> {
  private head: ListNode<T> | null = null;
  private tail: ListNode<T> | null = null;
  private _size = 0;

  enqueue(val: T): void {
    const node = new ListNode(val);
    if (this.tail) { this.tail.next = node; }
    else { this.head = node; }
    this.tail = node;
    this._size++;
  }

  dequeue(): T | undefined {
    if (!this.head) return undefined;
    const val = this.head.val;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    this._size--;
    return val;
  }

  peek(): T | undefined { return this.head?.val; }
  isEmpty(): boolean { return this._size === 0; }
  get size(): number { return this._size; }
}

// Application: recent counter (sliding window with queue)
class RecentCounter {
  private queue = new Queue<number>();

  ping(t: number): number {
    this.queue.enqueue(t);
    while (this.queue.peek()! < t - 3000) {
      this.queue.dequeue();
    }
    return this.queue.size;
  }
}

5. Hash Tables: The Most Practical Data Structure

Hash tables map keys to buckets (array indices) via a hash function, achieving average O(1) lookup, insert, and delete. JavaScript's Map/Object and Python's dict are hash table implementations. Collision handling is central to hash table design — common approaches include chaining and open addressing.

// Hash table implementation with chaining
class HashTable<K, V> {
  private buckets: Array<Array<[K, V]>>;
  private count = 0;

  constructor(private capacity = 16) {
    this.buckets = new Array(capacity).fill(null).map(() => []);
  }

  private hash(key: K): number {
    const str = String(key);
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
      hash = (hash * 31 + str.charCodeAt(i)) | 0;
    }
    return Math.abs(hash) % this.capacity;
  }

  set(key: K, value: V): void {
    const idx = this.hash(key);
    const bucket = this.buckets[idx];
    const existing = bucket.findIndex(([k]) => k === key);
    if (existing >= 0) {
      bucket[existing] = [key, value]; // update
    } else {
      bucket.push([key, value]);
      this.count++;
      if (this.count / this.capacity > 0.75) this.resize();
    }
  }

  get(key: K): V | undefined {
    const idx = this.hash(key);
    const pair = this.buckets[idx].find(([k]) => k === key);
    return pair ? pair[1] : undefined;
  }

  delete(key: K): boolean {
    const idx = this.hash(key);
    const bucket = this.buckets[idx];
    const i = bucket.findIndex(([k]) => k === key);
    if (i === -1) return false;
    bucket.splice(i, 1);
    this.count--;
    return true;
  }

  private resize(): void {
    const old = this.buckets;
    this.capacity *= 2;
    this.buckets = new Array(this.capacity).fill(null).map(() => []);
    this.count = 0;
    for (const bucket of old) {
      for (const [k, v] of bucket) this.set(k, v);
    }
  }
}

// Common hash table patterns

// 1. Frequency counter
function charFrequency(s: string): Map<string, number> {
  const freq = new Map<string, number>();
  for (const ch of s) {
    freq.set(ch, (freq.get(ch) || 0) + 1);
  }
  return freq;
}

// 2. Two-sum using hash map — O(n) vs O(n²) brute force
function twoSumHash(nums: number[], target: number): [number, number] | null {
  const map = new Map<number, number>(); // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }
  return null;
}

// 3. Group anagrams
function groupAnagrams(strs: string[]): string[][] {
  const map = new Map<string, string[]>();
  for (const s of strs) {
    const key = s.split("").sort().join("");
    if (!map.has(key)) map.set(key, []);
    map.get(key)!.push(s);
  }
  return Array.from(map.values());
}

6. Trees: Natural Representation of Hierarchical Data

A tree is a non-linear data structure where nodes are connected by edges, with a single root and each node having at most one parent. The Binary Search Tree (BST) is the most common tree, where each node's left subtree contains smaller values and right subtree contains larger values, supporting O(log n) search, insert, and delete when balanced.

Binary Search Tree Implementation

class TreeNode<T> {
  val: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  constructor(val: T) { this.val = val; }
}

class BST<T> {
  root: TreeNode<T> | null = null;

  // O(log n) average, O(n) worst (unbalanced)
  insert(val: T): void {
    const node = new TreeNode(val);
    if (!this.root) { this.root = node; return; }
    let curr = this.root;
    while (true) {
      if (val < curr.val) {
        if (!curr.left) { curr.left = node; return; }
        curr = curr.left;
      } else {
        if (!curr.right) { curr.right = node; return; }
        curr = curr.right;
      }
    }
  }

  // O(log n) average
  search(val: T): boolean {
    let curr = this.root;
    while (curr) {
      if (val === curr.val) return true;
      curr = val < curr.val ? curr.left : curr.right;
    }
    return false;
  }

  // In-order traversal: left -> root -> right (sorted output)
  inOrder(node: TreeNode<T> | null = this.root): T[] {
    if (!node) return [];
    return [
      ...this.inOrder(node.left),
      node.val,
      ...this.inOrder(node.right)
    ];
  }

  // Pre-order: root -> left -> right (copy/serialize)
  preOrder(node: TreeNode<T> | null = this.root): T[] {
    if (!node) return [];
    return [
      node.val,
      ...this.preOrder(node.left),
      ...this.preOrder(node.right)
    ];
  }

  // Post-order: left -> right -> root (delete/free)
  postOrder(node: TreeNode<T> | null = this.root): T[] {
    if (!node) return [];
    return [
      ...this.postOrder(node.left),
      ...this.postOrder(node.right),
      node.val
    ];
  }
}

// Level-order traversal (BFS) using a queue
function levelOrder<T>(root: TreeNode<T> | null): T[][] {
  if (!root) return [];
  const result: T[][] = [];
  const queue: TreeNode<T>[] = [root];
  while (queue.length > 0) {
    const levelSize = queue.length;
    const level: T[] = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

// Maximum depth of binary tree (DFS)
function maxDepth<T>(root: TreeNode<T> | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

7. Heaps and Priority Queues

A heap is a special complete binary tree satisfying the heap property: in a min-heap, each parent is less than or equal to its children; a max-heap is the reverse. Heaps are typically implemented with arrays and serve as the standard backing structure for priority queues. They are essential for Dijkstra's shortest path, median maintenance, and Top-K problems.

// Min-Heap implementation (array-based)
class MinHeap {
  private heap: number[] = [];

  private parent(i: number) { return Math.floor((i - 1) / 2); }
  private leftChild(i: number) { return 2 * i + 1; }
  private rightChild(i: number) { return 2 * i + 2; }

  private swap(i: number, j: number) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // O(log n) — insert and bubble up
  insert(val: number): void {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0 && this.heap[i] < this.heap[this.parent(i)]) {
      this.swap(i, this.parent(i));
      i = this.parent(i);
    }
  }

  // O(log n) — extract min and bubble down
  extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;
    const min = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  private bubbleDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = this.leftChild(i);
      const right = this.rightChild(i);
      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === i) break;
      this.swap(i, smallest);
      i = smallest;
    }
  }

  peek(): number | undefined { return this.heap[0]; } // O(1)
  get size(): number { return this.heap.length; }
}

// Application: find K largest elements
function kLargest(arr: number[], k: number): number[] {
  const minHeap = new MinHeap();
  for (const num of arr) {
    minHeap.insert(num);
    if (minHeap.size > k) minHeap.extractMin();
  }
  const result: number[] = [];
  while (minHeap.size > 0) result.push(minHeap.extractMin()!);
  return result;
}
console.log(kLargest([3, 1, 5, 12, 2, 11], 3)); // [5, 11, 12]

8. Graphs: Modeling Relationships and Networks

A graph consists of vertices (nodes) and edges, representing relationships between entities. Social networks, route planning, and dependency management are all graph applications. Graphs can be directed or undirected, weighted or unweighted. The two main representations are adjacency lists (efficient for sparse graphs) and adjacency matrices (efficient for dense graphs).

Graph Implementation and Traversal

// Adjacency List representation
class Graph {
  private adjacencyList = new Map<string, string[]>();

  addVertex(v: string): void {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v1: string, v2: string): void {
    this.addVertex(v1);
    this.addVertex(v2);
    this.adjacencyList.get(v1)!.push(v2);
    this.adjacencyList.get(v2)!.push(v1); // undirected
  }

  // BFS — finds shortest path in unweighted graph
  bfs(start: string): string[] {
    const visited = new Set<string>();
    const queue: string[] = [start];
    const result: string[] = [];
    visited.add(start);

    while (queue.length > 0) {
      const vertex = queue.shift()!;
      result.push(vertex);
      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return result;
  }

  // DFS — recursive
  dfs(start: string): string[] {
    const visited = new Set<string>();
    const result: string[] = [];

    const traverse = (vertex: string) => {
      visited.add(vertex);
      result.push(vertex);
      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) traverse(neighbor);
      }
    };

    traverse(start);
    return result;
  }

  // DFS — iterative with explicit stack
  dfsIterative(start: string): string[] {
    const visited = new Set<string>();
    const stack: string[] = [start];
    const result: string[] = [];

    while (stack.length > 0) {
      const vertex = stack.pop()!;
      if (visited.has(vertex)) continue;
      visited.add(vertex);
      result.push(vertex);
      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) stack.push(neighbor);
      }
    }
    return result;
  }

  // Shortest path (BFS) between two nodes
  shortestPath(start: string, end: string): string[] | null {
    const visited = new Set<string>();
    const queue: string[][] = [[start]];
    visited.add(start);

    while (queue.length > 0) {
      const path = queue.shift()!;
      const vertex = path[path.length - 1];
      if (vertex === end) return path;
      for (const neighbor of this.adjacencyList.get(vertex) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push([...path, neighbor]);
        }
      }
    }
    return null;
  }
}

// Usage
const g = new Graph();
g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "D");
g.addEdge("D", "E");
console.log(g.bfs("A"));            // [A, B, C, D, E]
console.log(g.shortestPath("A", "E")); // [A, B, D, E]

Topological Sort (Directed Acyclic Graph)

// Topological sort using Kahn's algorithm (BFS)
// Used for: build systems, task scheduling, course prerequisites
function topologicalSort(
  numNodes: number,
  edges: [number, number][]
): number[] {
  const adjList: number[][] = Array.from({ length: numNodes }, () => []);
  const inDegree = new Array(numNodes).fill(0);

  for (const [from, to] of edges) {
    adjList[from].push(to);
    inDegree[to]++;
  }

  // Start with nodes that have no incoming edges
  const queue: number[] = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const result: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);
    for (const neighbor of adjList[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // If result doesn't include all nodes, there's a cycle
  if (result.length !== numNodes) {
    throw new Error("Graph has a cycle — no valid topological order");
  }
  return result;
}

// Example: course prerequisites
// 0=Math, 1=Physics, 2=CS101, 3=CS201, 4=ML
const order = topologicalSort(5, [
  [0, 1], // Math -> Physics
  [0, 2], // Math -> CS101
  [2, 3], // CS101 -> CS201
  [1, 4], // Physics -> ML
  [3, 4], // CS201 -> ML
]);
console.log(order); // [0, 1, 2, 3, 4] or [0, 2, 1, 3, 4]

9. Sorting Algorithms: From Basic to Advanced

Sorting is one of the most fundamental algorithmic operations. Understanding the characteristics of different sorting algorithms — time complexity, space complexity, stability — helps you choose the best approach for your scenario. Most language built-in sorts use Timsort (a hybrid of merge sort and insertion sort) which excels on real-world data.

Merge Sort (Divide and Conquer)

// Merge Sort — O(n log n) guaranteed, stable, O(n) space
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

Quick Sort (In-Place)

// Quick Sort — O(n log n) average, O(n²) worst, in-place
function quickSort(
  arr: number[],
  low = 0,
  high = arr.length - 1
): number[] {
  if (low < high) {
    const pivotIdx = partition(arr, low, high);
    quickSort(arr, low, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, high);
  }
  return arr;
}

function partition(
  arr: number[],
  low: number,
  high: number
): number {
  // Median-of-three pivot selection for better performance
  const mid = Math.floor((low + high) / 2);
  if (arr[mid] < arr[low]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
  if (arr[high] < arr[low]) [arr[low], arr[high]] = [arr[high], arr[low]];
  if (arr[mid] < arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];

  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

const data = [10, 7, 8, 9, 1, 5];
console.log(quickSort([...data])); // [1, 5, 7, 8, 9, 10]

10. Searching Algorithms: Finding Data Efficiently

Searching is one of the most common operations in programming. Linear search works on unsorted data (O(n)), binary search works on sorted data (O(log n)). Mastering binary search variants — finding left bounds, right bounds, searching rotated arrays — is a core technical interview skill.

Binary Search Variants

// Standard binary search
function binarySearch(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2); // avoid overflow
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// Find leftmost (first) occurrence
function lowerBound(arr: number[], target: number): number {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left; // first index where arr[i] >= target
}

// Find rightmost (last) occurrence
function upperBound(arr: number[], target: number): number {
  let left = 0, right = arr.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] <= target) left = mid + 1;
    else right = mid;
  }
  return left - 1; // last index where arr[i] <= target
}

// Search in rotated sorted array
function searchRotated(arr: number[], target: number): number {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) return mid;

    // Left half is sorted
    if (arr[left] <= arr[mid]) {
      if (arr[left] <= target && target < arr[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    // Right half is sorted
    else {
      if (arr[mid] < target && target <= arr[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}

// Example
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0)); // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3)); // -1

11. Data Structures in Practice: Python Examples

Python has rich built-in data structure support. list is a dynamic array, dict is a hash table, set is a hash set, the collections module provides deque (double-ended queue), Counter (frequency counter), defaultdict, and the heapq module provides heap operations.

# Python data structure essentials

from collections import deque, Counter, defaultdict
import heapq

# ---- list (dynamic array) ----
arr = [3, 1, 4, 1, 5, 9]
arr.sort()                  # in-place sort: [1, 1, 3, 4, 5, 9]
sorted_arr = sorted(arr)    # returns new sorted list
arr.append(2)               # O(1) amortized
arr.pop()                   # O(1) remove last
arr.insert(0, 99)           # O(n) insert at index

# List comprehension (Pythonic way)
squares = [x**2 for x in range(10)]          # [0, 1, 4, 9, ..., 81]
evens = [x for x in arr if x % 2 == 0]      # filter even numbers

# ---- dict (hash table) ----
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"]}
graph.get("X", [])          # safe access with default

# ---- set (hash set) ----
seen = set()
seen.add(1)                 # O(1)
print(1 in seen)            # O(1) membership test: True

# ---- deque (double-ended queue) ----
q = deque([1, 2, 3])
q.append(4)                 # O(1) right
q.appendleft(0)             # O(1) left
q.pop()                     # O(1) right
q.popleft()                 # O(1) left — unlike list.pop(0) which is O(n)

# ---- Counter (frequency counting) ----
text = "hello world"
freq = Counter(text)
print(freq.most_common(3))  # [('l', 3), ('o', 2), ('h', 1)]

# ---- defaultdict ----
adj = defaultdict(list)
adj["A"].append("B")        # no KeyError if key missing
adj["A"].append("C")

# ---- heapq (min-heap) ----
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
print(heapq.heappop(heap))  # 1 (min element)

# Top-K largest
nums = [3, 1, 5, 12, 2, 11]
print(heapq.nlargest(3, nums))   # [12, 11, 5]
print(heapq.nsmallest(3, nums))  # [1, 2, 3]

# ---- BFS in Python ----
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return result

12. How to Choose the Right Data Structure

When choosing a data structure, consider your most frequent operations, data volume, whether ordering is needed, and space constraints. The comparison table below helps you make quick decisions.

Data Structure Complexity Cheat Sheet

* Linked list O(1) insert/delete requires a known node reference; finding the position is O(n). All hash table complexities are average case.

Conclusion

Data structures and algorithms are core skills for every developer. Arrays and hash tables cover most daily needs, stacks and queues solve specific access pattern problems, and trees and graphs handle hierarchical and network relationship data. Mastering Big O analysis lets you predict performance before writing code, and choosing sorting and searching algorithms should consider data characteristics. Remember: there is no one-size-fits-all data structure — only the best one for your current problem.

Frequently Asked Questions