Chapter 141: Data Structure Selection Cheat Sheet

Prerequisites

• Basic data structures (arrays, linked lists, trees, hash maps)
• Complexity analysis (Big-O notation)

Interview Frequency: ★★★★★

Choosing the right data structure is often the single most impactful decision in solving a problem efficiently. This chapter provides a systematic framework for making that choice.

141.1 The Decision Framework

When faced with a problem, ask these questions in order:

1. What operations do I need? (insert, delete, search, min/max, range query, etc.)
2. What are the constraints? (n ≤ 10³ vs n ≤ 10⁶ vs n ≤ 10⁹)
3. Do I need ordering? (sorted traversal, predecessor/successor)
4. Do I need persistence? (undo operations, snapshots)
5. What are the time/space trade-offs?

141.2 By Operation Needed

141.3 Detailed Comparisons

Array vs Linked List

Choose array when: You need random access, iteration, or cache performance. Choose linked list when: You need frequent insertions/deletions at arbitrary positions without shifting.

Hash Map vs BST (Ordered Map)

Choose hash map when: You only need key-value lookups and don’t care about order. Choose BST when: You need sorted order, range queries, or predecessor/successor operations.

Segment Tree vs Fenwick Tree (BIT)

Choose Fenwick when: You only need prefix sums or point updates with range queries. Choose segment tree when: You need range min/max, lazy propagation, or complex operations.

Heap vs BST

Choose heap when: You only need the min or max element (priority queue). Choose BST when: You need search, sorted traversal, or arbitrary deletions.

Stack vs Queue vs Deque

141.4 By Problem Pattern

Pattern: “Find something in a collection”

• Unsorted, many lookups → Hash set/map
• Sorted → Binary search on array, or BST
• Need order statistics → Order statistic tree or sorted set

Pattern: “Maintain running min/max”

• All elements → Heap (priority queue)
• Sliding window → Monotonic deque
• With deletion → Two heaps or balanced BST with lazy deletion

Pattern: “Range queries on array”

• Static array, range sum → Prefix sum array
• Static array, range min → Sparse table (O(1) query)
• Dynamic array, range sum → Fenwick tree
• Dynamic array, range min → Segment tree
• Range updates → Lazy segment tree

Pattern: “Grouping and connectivity”

• Merge sets, check connectivity → DSU (Union-Find)
• Graph traversal → Adjacency list + BFS/DFS

Pattern: “String operations”

• Single pattern matching → KMP or Z-algorithm
• Multiple pattern matching → Aho-Corasick
• Prefix queries → Trie
• Suffix queries → Suffix array or suffix automaton

Pattern: “Cache / Eviction”

• LRU → Hash map + doubly linked list
• LFU → Hash map + frequency buckets

141.5 Complexity Quick Reference

141.6 Example: Choosing for a Real Problem

Problem: Given an array of n integers, answer q queries of the form “what is the sum of elements from index l to r?” The array may be updated between queries.

Analysis:

• Need range sum → prefix sum (static) or Fenwick/segment tree (dynamic)
• Array is updated → prefix sum won’t work
• Only need sum (not min/max) → Fenwick tree is sufficient and simpler
• n, q ≤ 10⁵ → O(log n) per operation is fine

Decision: Fenwick tree (BIT)

C++ Implementation:

#include <vector>
using namespace std;

class FenwickTree {
    vector<int> tree;
    int n;
public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}
    
    void update(int i, int delta) {
        for (++i; i <= n; i += i & (-i))
            tree[i] += delta;
    }
    
    int query(int i) {
        int sum = 0;
        for (++i; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }
    
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
};

Python Implementation:

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, i, delta):
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)
    
    def query(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
    
    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

Java Implementation:

class FenwickTree {
    int[] tree;
    int n;
    
    FenwickTree(int n) {
        this.n = n;
        this.tree = new int[n + 1];
    }
    
    void update(int i, int delta) {
        for (i++; i <= n; i += i & (-i))
            tree[i] += delta;
    }
    
    int query(int i) {
        int sum = 0;
        for (i++; i > 0; i -= i & (-i))
            sum += tree[i];
        return sum;
    }
    
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
}

141.7 Common Mistakes

1. Using hash map when order matters — Hash maps don’t guarantee iteration order in most languages.
2. Using BST for simple lookups — If you don’t need ordering, a hash map is faster.
3. Using array when frequent insertions are needed — Each insertion shifts O(n) elements.
4. Over-engineering with segment tree — If the array is static, prefix sums are simpler and faster.
5. Forgetting about worst-case hash performance — Use balanced BSTs when worst-case guarantees matter.
6. Not considering memory constraints — Segment trees use 4x memory; hash maps have high overhead.

141.8 Exercises

1. Design a data structure that supports insert, delete, and getRandom in O(1). Hint: combine array with hash map.

2. Design a data structure for a sliding window that supports addRight, removeLeft, and getMin, all in O(1). Hint: monotonic deque.

3. Given q queries of type “add number to set” and “find number closest to x”, which data structure would you use? Hint: balanced BST (std::set in C++, TreeSet in Java).

4. Implement an LFU cache with O(1) get and put. Hint: hash map + frequency buckets + doubly linked list.

5. Given a grid of size n×m, answer queries “how many 1s in sub-rectangle (r1,c1) to (r2,c2)?” after point updates. Hint: 2D Fenwick tree.

141.9 Interview Questions

1. “Design a hit counter” that counts hits in the past 5 minutes. → Circular buffer or deque with timestamps.

2. “Find the median of a stream” as numbers arrive one by one. → Two heaps (max-heap for lower half, min-heap for upper half).

3. “Design Twitter” — show the 10 most recent tweets from people you follow. → Hash map of user → tweets + merge k sorted lists with heap.

4. “Implement a phone directory” with prefix search. → Trie.

5. “Range sum query with updates” — Fenwick tree or segment tree.

141.10 Cross-References

• Hash Maps: Chapter on Hashing
• Binary Search Trees: Chapter on BSTs
• Segment Trees: Chapter on Segment Trees
• Fenwick Trees: Chapter on Binary Indexed Trees
• Heaps: Chapter on Priority Queues
• Tries: Chapter on Trie
• DSU: Chapter on Union-Find
• Monotonic Stack/Deque: Chapter on Monotonic Structures

Summary