Data Structures & Algorithms Cheatsheet

1. Introduction: The Ultimate Reference Guide

When you are weeks into studying for technical interviews, the sheer volume of information can blur together. Does a PriorityQueue insert in $O(1)$ or $O(\log N)$ time? What's the space complexity of Quick Sort? What is the template for Topological Sort?

This cheatsheet serves as a high-density, university-grade reference guide. It condenses the mathematical complexities, core Java APIs, and standard algorithm templates into a single, quickly scannable document. Bookmark this page for rapid review right before your technical interviews.

2. Big-O Complexity Chart

Data Structures

| Data Structure | Access (Avg) | Search (Avg) | Insertion (Avg) | Deletion (Avg) | Space (Worst) | | :--- | :--- | :--- | :--- | :--- | :--- | | Array | $O(1)$ | $O(N)$ | $O(N)$ | $O(N)$ | $O(N)$ | | Stack / Queue | $O(N)$ | $O(N)$ | $O(1)$ | $O(1)$ | $O(N)$ | | Singly Linked List | $O(N)$ | $O(N)$ | $O(1)$ | $O(1)$ | $O(N)$ | | Hash Table | N/A | $O(1)$ | $O(1)$ | $O(1)$ | $O(N)$ | | BST | $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(N)$ | | AVL / Red-Black Tree| $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(\log N)$ | $O(N)$ | | Min/Max Heap | N/A | $O(N)$ | $O(\log N)$ | $O(\log N)$ | $O(N)$ | | Trie | $O(L)$ | $O(L)$ | $O(L)$ | $O(L)$ | $O(N \times L)$ |

(Note: $L$ represents the length of the string).

Sorting Algorithms

| Algorithm | Time (Best) | Time (Average) | Time (Worst) | Space (Worst) | Stable? | | :--- | :--- | :--- | :--- | :--- | :--- | | Merge Sort | $O(N \log N)$ | $O(N \log N)$ | $O(N \log N)$ | $O(N)$ | Yes | | Quick Sort | $O(N \log N)$ | $O(N \log N)$ | $O(N^2)$ | $O(\log N)$ | No | | Heap Sort | $O(N \log N)$ | $O(N \log N)$ | $O(N \log N)$ | $O(1)$ | No | | Insertion Sort| $O(N)$ | $O(N^2)$ | $O(N^2)$ | $O(1)$ | Yes | | Counting Sort | $O(N+K)$ | $O(N+K)$ | $O(N+K)$ | $O(K)$ | Yes |

(Note: $K$ represents the range of the integers).

3. Java Data Structure Syntax

Array & String

// Arrays
int[] arr = new int[5];
Arrays.sort(arr);           // O(N log N) Dual-Pivot Quicksort
Arrays.fill(arr, -1);       // O(N)
int[] copy = Arrays.copyOf(arr, arr.length); // O(N)

// Strings
String s = "hello";
char c = s.charAt(0);       // O(1)
char[] chars = s.toCharArray(); // O(N)
String sub = s.substring(1, 3); // O(N)

Collections

// HashMap
Map<String, Integer> map = new HashMap<>();
map.put("A", 1);            // O(1)
map.getOrDefault("B", 0);   // O(1)
for (Map.Entry<String, Integer> entry : map.entrySet()) { ... }

// HashSet
Set<Integer> set = new HashSet<>();
set.add(1);                 // O(1)
set.contains(1);            // O(1)

// Queue (LinkedList)
Queue<Integer> q = new LinkedList<>();
q.offer(1);                 // O(1) Enqueue
q.poll();                   // O(1) Dequeue (returns null if empty)

// Stack (ArrayDeque is preferred over legacy Stack)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);              // O(1) Push
stack.pop();                // O(1) Pop (throws exception if empty)

// Min-Heap (PriorityQueue)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);           // O(log N)
minHeap.poll();             // O(log N) - Removes minimum

// Max-Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
// Or: Collections.reverseOrder()

4. Standard Algorithm Templates

1. Sliding Window (Variable)

Used for finding the longest/shortest subarray that meets a condition.

int left = 0, maxLength = 0;
for (int right = 0; right < arr.length; right++) {
    // Add arr[right] to window state
    
    while (/* window state violates condition */) {
        // Remove arr[left] from window state
        left++;
    }
    
    maxLength = Math.max(maxLength, right - left + 1);
}

2. Binary Search

Used for finding an element in a sorted array in $O(\log N)$ time.

int left = 0, right = arr.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

3. Graph DFS

Used for exploring all paths or counting connected components.

boolean[] visited = new boolean[N];
public void dfs(int node, List<List<Integer>> adj) {
    if (visited[node]) return;
    visited[node] = true;
    for (int neighbor : adj.get(node)) {
        dfs(neighbor, adj);
    }
}

4. Graph BFS

Used for finding the shortest path in an unweighted graph.

Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[N];

q.offer(startNode);
visited[startNode] = true;
int steps = 0;

while (!q.isEmpty()) {
    int size = q.size(); // Process level by level
    for (int i = 0; i < size; i++) {
        int curr = q.poll();
        if (curr == target) return steps;
        
        for (int neighbor : adj.get(curr)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.offer(neighbor);
            }
        }
    }
    steps++;
}

5. Backtracking (Combinations/Permutations)

Used for generating all mathematically possible states.

public void backtrack(List<List<Integer>> res, List<Integer> curr, int[] nums, int start) {
    // Base Case / Add to result
    res.add(new ArrayList<>(curr)); // ALWAYS Deep Copy!
    
    for (int i = start; i < nums.length; i++) {
        curr.add(nums[i]);          // MAKE CHOICE
        backtrack(res, curr, nums, i + 1); // RECURSE
        curr.remove(curr.size() - 1); // UNDO CHOICE
    }
}

6. Union-Find (Disjoint Set)

Used for instantly checking if two nodes are in the same component.

int[] parent = new int[N];
for(int i = 0; i < N; i++) parent[i] = i;

public int find(int i) {
    if (parent[i] == i) return i;
    return parent[i] = find(parent[i]); // Path compression
}

public void union(int i, int j) {
    int rootI = find(i);
    int rootJ = find(j);
    if (rootI != rootJ) parent[rootI] = rootJ;
}

5. Identifying the Right Pattern

If you are stuck in an interview, check the constraints and the goal:

1. Top/Maximum/Minimum $K$ elements $\rightarrow$ Heap (Priority Queue)
2. "Contiguous" Subarray/Substring $\rightarrow$ Sliding Window
3. Sorted Array + Target Sum $\rightarrow$ Two Pointers
4. Sorted Array + $O(\log N)$ requirement $\rightarrow$ Binary Search
5. Shortest Path in Unweighted Graph/Matrix $\rightarrow$ BFS
6. Shortest Path in Weighted Graph $\rightarrow$ Dijkstra's
7. Find all combinations/permutations $\rightarrow$ Backtracking
8. Overlapping subproblems (Max/Min ways) $\rightarrow$ Dynamic Programming
9. String matching / prefix tracking $\rightarrow$ Trie
10. Monotonically increasing/decreasing conditions $\rightarrow$ Monotonic Stack

6. Interview Checklist

1. Clarify: Ask about edge cases. Are there negative numbers? Empty arrays? Can the graph have cycles?
2. Brute Force: State the naive solution and its Big-O immediately so you have a baseline.
3. Optimize: Discuss trade-offs (Time vs. Space). Suggest HashMaps, Heaps, or Sorting.
4. Code: Write clean, modular code. Use descriptive variable names (currNode not c).
5. Test: Dry-run your code with a small example on the whiteboard before the interviewer points out bugs.