Module 10: Advanced Data Structures & Algorithms

Goal: Master production-grade advanced structures: Tries & Bitwise Tries, Disjoint Set Union (DSU / Union-Find) with Path Compression & Rank, Segment Trees for $O(\log N)$ range queries, Bit Manipulation hacks, Greedy optimization invariants, and Backtracking search trees.
Language: C++ (C++17/C++20)
Prerequisites: Modules 01 to 09.

📑 Table of Contents

Trie (Prefix Tree) & Bitwise Tries
Disjoint Set Union (DSU / Union-Find)
Segment Trees & Range Queries
Bit Manipulation Mastery & Bit Tricks
Greedy Algorithms: The Invariant Framework
Backtracking Masterclass & Search Tree Pruning
6 Practice Problems with Detailed Solutions
Top 10 FAANG Interview Questions

1. Trie (Prefix Tree) & Bitwise Tries

A Trie is a tree-like search structure where nodes represent characters along string paths, enabling $O(L)$ insertion, search, and prefix matching (where $L$ is word length).

Trie containing: "apple", "app", "apt", "bat"

                   (Root)
                  /      \
               ['a']    ['b']
                │         │
              ['p']     ['a']
                │         │
              ['p']*    ['t']*
             /     \
          ['l']   ['t']*
            │
          ['e']*
(* denotes isEndOfWord = true)

1.1 Trie Implementation in C++

#include <string>
#include <vector>

class Trie {
private:
    struct TrieNode {
        TrieNode* children[26];
        bool isEndOfWord;
        TrieNode() : isEndOfWord(false) {
            for (int i = 0; i < 26; ++i) children[i] = nullptr;
        }
    };
    TrieNode* root;

public:
    Trie() { root = new TrieNode(); }

    void insert(const std::string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) {
                curr->children[idx] = new TrieNode();
            }
            curr = curr->children[idx];
        }
        curr->isEndOfWord = true;
    }

    bool search(const std::string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!curr->children[idx]) return false;
            curr = curr->children[idx];
        }
        return curr->isEndOfWord;
    }

    bool startsWith(const std::string& prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!curr->children[idx]) return false;
            curr = curr->children[idx];
        }
        return true;
    }
};
// Time Complexity: O(L) for all operations
// Space Complexity: O(Total Characters * 26)

2. Disjoint Set Union (DSU / Union-Find)

Tracks partitioned disjoint sets with two operations:

find(i): Determine which subset element $i$ belongs to.
unite(i, j): Merge the subsets containing $i$ and $j$.

Path Compression:                          Union by Rank:
Before find(4):       After find(4):       Attach shallower tree under deeper tree:
     (1)                   (1)                  (Root1, Rank=2)      (Root2, Rank=1)
      │                  /  │  \                       ▲                    │
     (2)               (2) (3) (4)                     └────────────────────┘
      │
     (3)
      │
     (4)

2.1 Complete DSU Implementation in C++

#include <vector>
#include <numeric>

class DisjointSetUnion {
private:
    std::vector<int> parent;
    std::vector<int> rank;
    int componentsCount;

public:
    DisjointSetUnion(int n) : parent(n), rank(n, 0), componentsCount(n) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    // Find with Path Compression: O(alpha(N)) ≈ O(1)
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    // Union by Rank: O(alpha(N)) ≈ O(1)
    bool unite(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        
        if (rootI == rootJ) return false; // Already in same set
        
        if (rank[rootI] < rank[rootJ]) {
            parent[rootI] = rootJ;
        } else if (rank[rootI] > rank[rootJ]) {
            parent[rootJ] = rootI;
        } else {
            parent[rootJ] = rootI;
            rank[rootI]++;
        }
        componentsCount--;
        return true;
    }

    int getComponentsCount() const { return componentsCount; }
};

Complexity: $\alpha(N)$ is the Inverse Ackermann Function, which satisfies $\alpha(N) < 5$ for all universe-scale values of $N \le 10^{80}$.

3. Segment Trees & Range Queries

A Segment Tree allows $O(\log N)$ range queries (sum, min, max, GCD) and $O(\log N)$ point updates over an array of size $N$.

Array: [1, 3, 5, 7]
Segment Tree Array (Size 4N):
                         [0..3: Sum=16]  (Index 1)
                        /              \
            [0..1: Sum=4]              [2..3: Sum=12]  (Indices 2, 3)
            /           \              /            \
     [0..0: 1]       [1..1: 3]   [2..2: 5]        [3..3: 7]

3.1 Segment Tree Implementation

#include <vector>

class SegmentTree {
private:
    int n;
    std::vector<int> tree;

    void build(const std::vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    void updateHelper(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        if (idx <= mid) updateHelper(2 * node, start, mid, idx, val);
        else updateHelper(2 * node + 1, mid + 1, end, idx, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

    int queryHelper(int node, int start, int end, int l, int r) {
        if (r < start || end < l) return 0; // Out of range
        if (l <= start && end <= r) return tree[node]; // Total overlap
        
        int mid = start + (end - start) / 2;
        return queryHelper(2 * node, start, mid, l, r) +
               queryHelper(2 * node + 1, mid + 1, end, l, r);
    }

public:
    SegmentTree(const std::vector<int>& arr) {
        n = arr.size();
        tree.assign(4 * n, 0);
        build(arr, 1, 0, n - 1);
    }

    void update(int idx, int val) { updateHelper(1, 0, n - 1, idx, val); }
    int query(int l, int r) { return queryHelper(1, 0, n - 1, l, r); }
};
// Build: O(N)
// Query / Update: O(log N)
// Space: O(4N)

4. Bit Manipulation Mastery & Bit Tricks

┌──────────────────────────────────────┬────────────────────────────────────────────────────────┐
│ Bit Operation                        │ Meaning / Code                                         │
├──────────────────────────────────────┼────────────────────────────────────────────────────────┤
│ Check if k-th bit is set             │ (n & (1 << k)) != 0                                    │
│ Set k-th bit                         │ n |= (1 << k)                                          │
│ Clear k-th bit                       │ n &= ~(1 << k)                                         │
│ Toggle k-th bit                      │ n ^= (1 << k)                                          │
│ Clear lowest set bit (Kernighan)     │ n = n & (n - 1)  (e.g., 01100 -> 01000)                │
│ Isolate lowest set bit               │ lowest = n & (-n)                                      │
│ Check if power of 2                  │ (n > 0) && ((n & (n - 1)) == 0)                        │
│ Count set bits (Popcount)            │ __builtin_popcount(n) or std::popcount (C++20)         │
│ Number of leading zeros              │ __builtin_clz(n)                                       │
└──────────────────────────────────────┴────────────────────────────────────────────────────────┘

5. Greedy Algorithms: The Invariant Framework

A greedy algorithm makes the best choice at the current moment without reconsidering.

Proving Correctness (Greedy-Stays-Ahead Technique)

Let $G = (g_1, g_2, \dots, g_k)$ be the greedy choices.
Let $O = (o_1, o_2, \dots, o_m)$ be an optimal solution.
Prove by induction that at every step $i$, greedy is at least as good as optimal ($g_i \ge o_i$).
Conclude that $|G| \ge |O|$, proving greedy is optimal.

6. Backtracking Masterclass & Search Tree Pruning

// Universal Backtracking Template
void backtrack(State& state, const Candidates& candidates, Result& result) {
    if (isGoal(state)) {
        result.push_back(state.formatResult());
        return;
    }
    
    for (const auto& candidate : candidates) {
        if (!isValid(candidate, state)) continue; // PRUNING!
        
        state.makeChoice(candidate);   // 1. Choose
        backtrack(state, candidates, result); // 2. Explore
        state.undoChoice(candidate);   // 3. Unchoose (Backtrack)
    }
}

7. 6 Practice Problems with Detailed Solutions

Problem 1: Maximum XOR of Two Numbers in an Array (LeetCode #421 - Medium)

Problem: Return the maximum XOR value among all pairs in an integer array using a Bitwise Trie.

#include <vector>
#include <algorithm>

class BitwiseTrie {
private:
    struct Node {
        Node* bit[2] = {nullptr, nullptr};
    };
    Node* root = new Node();

public:
    void insert(int num) {
        Node* curr = root;
        for (int i = 31; i >= 0; --i) {
            int b = (num >> i) & 1;
            if (!curr->bit[b]) curr->bit[b] = new Node();
            curr = curr->bit[b];
        }
    }

    int getMaxXOR(int num) {
        Node* curr = root;
        int maxXor = 0;
        for (int i = 31; i >= 0; --i) {
            int b = (num >> i) & 1;
            int opposite = 1 - b;
            if (curr->bit[opposite]) {
                maxXor |= (1 << i);
                curr = curr->bit[opposite];
            } else {
                curr = curr->bit[b];
            }
        }
        return maxXor;
    }
};

int findMaximumXOR(std::vector<int>& nums) {
    BitwiseTrie trie;
    for (int x : nums) trie.insert(x);
    
    int maxVal = 0;
    for (int x : nums) {
        maxVal = std::max(maxVal, trie.getMaxXOR(x));
    }
    return maxVal;
}
// Time: O(32 * N) = O(N)
// Space: O(32 * N)

Problem 2: Accounts Merge (LeetCode #721 - Medium)

Problem: Merge accounts having overlapping email addresses using DSU.

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

std::vector<std::vector<std::string>> accountsMerge(std::vector<std::vector<std::string>>& accounts) {
    int n = accounts.size();
    DisjointSetUnion dsu(n);
    std::unordered_map<std::string, int> emailToAccount;
    
    for (int i = 0; i < n; ++i) {
        for (size_t j = 1; j < accounts[i].size(); ++j) {
            const std::string& email = accounts[i][j];
            if (emailToAccount.count(email)) {
                dsu.unite(i, emailToAccount[email]);
            } else {
                emailToAccount[email] = i;
            }
        }
    }
    
    std::unordered_map<int, std::vector<std::string>> mergedEmails;
    for (const auto& [email, accIdx] : emailToAccount) {
        int root = dsu.find(accIdx);
        mergedEmails[root].push_back(email);
    }
    
    std::vector<std::vector<std::string>> result;
    for (auto& [rootIdx, emails] : mergedEmails) {
        std::sort(emails.begin(), emails.end());
        std::vector<std::string> acc;
        acc.push_back(accounts[rootIdx][0]); // Name
        acc.insert(acc.end(), emails.begin(), emails.end());
        result.push_back(std::move(acc));
    }
    
    return result;
}
// Time Complexity: O(N * K log K)
// Space Complexity: O(N * K)

Problem 3: N-Queens (LeetCode #51 - Hard)

Problem: Place $N$ queens on an $N \times N$ chessboard such that no two attack each other.

#include <vector>
#include <string>

class SolutionNQueens {
private:
    std::vector<std::vector<std::string>> solutions;
    std::vector<bool> cols;
    std::vector<bool> diag1; // r + c
    std::vector<bool> diag2; // r - c + n - 1

    void solve(int row, int n, std::vector<std::string>& board) {
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; ++col) {
            if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) continue; // Prune
            
            // Choose
            board[row][col] = 'Q';
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = true;
            
            // Explore
            solve(row + 1, n, board);
            
            // Unchoose
            board[row][col] = '.';
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = false;
        }
    }

public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        solutions.clear();
        cols.assign(n, false);
        diag1.assign(2 * n, false);
        diag2.assign(2 * n, false);
        
        std::vector<std::string> board(n, std::string(n, '.'));
        solve(0, n, board);
        return solutions;
    }
};
// Time Complexity: O(N!)
// Space Complexity: O(N^2)

Problem 4: Non-overlapping Intervals (LeetCode #435 - Medium)

Problem: Return minimum number of intervals to remove to make the rest non-overlapping.

#include <vector>
#include <algorithm>

int eraseOverlapIntervals(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    
    // Greedy: Sort by end time
    std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
        return a[1] < b[1];
    });
    
    int nonOverlapCount = 1;
    int end = intervals[0][1];
    
    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] >= end) {
            nonOverlapCount++;
            end = intervals[i][1];
        }
    }
    
    return intervals.size() - nonOverlapCount;
}
// Time Complexity: O(N log N)
// Space Complexity: O(1)

Problem 5: Subsets (LeetCode #78 - Medium)

#include <vector>

std::vector<std::vector<int>> subsets(const std::vector<int>& nums) {
    int n = nums.size();
    int totalSubsets = 1 << n; // 2^N
    std::vector<std::vector<int>> result;
    result.reserve(totalSubsets);
    
    for (int mask = 0; mask < totalSubsets; ++mask) {
        std::vector<int> currentSubset;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                currentSubset.push_back(nums[i]);
            }
        }
        result.push_back(std::move(currentSubset));
    }
    return result;
}
// Time Complexity: O(N * 2^N)
// Space Complexity: O(1) auxiliary

Problem 6: Sudoku Solver (LeetCode #37 - Hard)

#include <vector>

class SolutionSudoku {
private:
    bool isValid(const std::vector<std::vector<char>>& board, int r, int c, char val) {
        for (int i = 0; i < 9; ++i) {
            if (board[r][i] == val) return false;
            if (board[i][c] == val) return false;
            if (board[3 * (r / 3) + i / 3][3 * (c / 3) + i % 3] == val) return false;
        }
        return true;
    }

    bool solve(std::vector<std::vector<char>>& board) {
        for (int r = 0; r < 9; ++r) {
            for (int c = 0; c < 9; ++c) {
                if (board[r][c] == '.') {
                    for (char ch = '1'; ch <= '9'; ++ch) {
                        if (isValid(board, r, c, ch)) {
                            board[r][c] = ch;
                            if (solve(board)) return true;
                            board[r][c] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

public:
    void solveSudoku(std::vector<std::vector<char>>& board) {
        solve(board);
    }
};

8. Top 10 FAANG Interview Questions

Q1: Why does Trie beat Hash Table for autocomplete and dictionary prefix lookups?

Answer:

Hash tables require hashing the entire string and cannot efficiently answer prefix queries like "find all words starting with 'ant'".
Tries naturally group words sharing prefixes, allowing prefix matching in $O(L)$ where $L = \text{prefix length}$, independent of dictionary size $N$.

Q2: What is Lazy Propagation in Segment Trees?

Answer: When performing range updates $[L, R, +V]$, updating all individual leaf nodes takes $O(N)$. With Lazy Propagation, we update only the root of the interval in $O(\log N)$ and store the pending update in a lazy[] array. The update is pushed down to children only when those children are explicitly queried or modified later.

Q3: What is the Fenwick Tree (Binary Indexed Tree) vs Segment Tree?

Answer:

Fenwick Tree: Uses array indexing math (i += i & -i and i -= i & -i). Requires only $O(N)$ space, has much smaller constant factor and simpler code. Limited mostly to invertible operations (sum, XOR).
Segment Tree: Requires $O(4N)$ space, but can support arbitrary associative operations (range min/max, GCD, range assignment) and range updates via lazy propagation.

Q4: How does Path Compression affect the depth of a DSU tree?

Answer: Path compression flattens the tree so every node along the find path points directly to the root. While a sequence of unions without compression could create a linear degenerate tree of depth $O(N)$, path compression combined with union by rank ensures the average tree height remains strictly $\le \alpha(N) \approx O(1)$.

Q5: How do you swap two integers using XOR without temporary variables?

Answer:

a ^= b;
b ^= a; // b is now original a
a ^= b; // a is now original b

Note: a and b must not refer to the same memory address, or the value will be zeroed.

Q6: What is the meet-in-the-middle technique in Backtracking?

Answer: For problems with search space $O(2^N)$ where $N \approx 40$ (too large for direct recursion):

Split the array into two halves of size $N/2 = 20$.
Generate all $2^{20} \approx 10^6$ combinations for each half.
Sort one half and use binary search / two pointers to match elements across halves. Reduces time from $O(2^{40}) \approx 10^{12}$ to $O(2^{20} \log(2^{20})) \approx 2 \times 10^7$ operations.

Q7: When does the Greedy choice fail in Interval Scheduling?

Answer: Sorting by start time or shortest duration fails to maximize non-overlapping intervals (counterexamples exist). Sorting by earliest finish time is mathematically proven to always be optimal.

Q8: What is a Bitwise Trie and why is it useful?

Answer: A Trie where each node has at most 2 branches (0 and 1), storing binary representations of numbers from most significant bit (MSB) to least significant bit (LSB). It allows finding the pair with maximum XOR in $O(32 \cdot N) = O(N)$ time by greedily branching towards the opposite bit at each level.

Q9: How can bitmasks be used to represent visited states on a grid with up to 10 keys?

Answer: Use a 10-bit integer bitmask. Collecting key $k$ sets bit $k$: mask | (1 << k). BFS state becomes a tuple (row, col, mask), visiting up to $R \times C \times 2^{10}$ states in $O(R \cdot C \cdot 2^K)$ time.

Q10: How do you enumerate all submasks of a bitmask in $O(3^N)$ instead of $O(4^N)$?

Answer:

for (int mask = 0; mask < (1 << n); ++mask) {
    for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
        // Process submask
    }
}

The expression (submask - 1) & mask efficiently jumps to the next valid submask without inspecting non-submask bit combinations.

10-advanced-data-structures-and-algorithms.md

Module 10: Advanced Data Structures & Algorithms

📑 Table of Contents

1. Trie (Prefix Tree) & Bitwise Tries

1.1 Trie Implementation in C++

2. Disjoint Set Union (DSU / Union-Find)

2.1 Complete DSU Implementation in C++

3. Segment Trees & Range Queries

3.1 Segment Tree Implementation

4. Bit Manipulation Mastery & Bit Tricks

5. Greedy Algorithms: The Invariant Framework

Proving Correctness (Greedy-Stays-Ahead Technique)

6. Backtracking Masterclass & Search Tree Pruning

7. 6 Practice Problems with Detailed Solutions

Problem 1: Maximum XOR of Two Numbers in an Array (LeetCode #421 - Medium)

Problem 2: Accounts Merge (LeetCode #721 - Medium)

Problem 3: N-Queens (LeetCode #51 - Hard)

Problem 4: Non-overlapping Intervals (LeetCode #435 - Medium)

Problem 5: Subsets (LeetCode #78 - Medium)

Problem 6: Sudoku Solver (LeetCode #37 - Hard)

8. Top 10 FAANG Interview Questions

Q1: Why does Trie beat Hash Table for autocomplete and dictionary prefix lookups?

Q2: What is Lazy Propagation in Segment Trees?

Q3: What is the Fenwick Tree (Binary Indexed Tree) vs Segment Tree?

Q4: How does Path Compression affect the depth of a DSU tree?

Q5: How do you swap two integers using XOR without temporary variables?

Q6: What is the meet-in-the-middle technique in Backtracking?

Q7: When does the Greedy choice fail in Interval Scheduling?

Q8: What is a Bitwise Trie and why is it useful?

Q9: How can bitmasks be used to represent visited states on a grid with up to 10 keys?

Q10: How do you enumerate all submasks of a bitmask in $O(3^N)$ instead of $O(4^N)$?