Advanced Data Structures: Practice Problems
Time to put the advanced structures to work. Solve each problem yourself first — pick the right tool (union-find, segment/Fenwick tree, LRU cache, or KMP), code it, trace a small example, and reason about complexity. Only then open the answer sheet. Every View answer link jumps to a full, multi-language solution on the advanced solutions page.
How to practice: Set a timer (20–30 min per problem). If you’re stuck, re-read the matching concept page before peeking. The goal is to recognize which structure a new problem needs.
Warm-ups
Q1. Number of Provinces. Given an n × n matrix isConnected where isConnected[i][j] == 1 means cities i and j are directly connected, return the number of provinces (connected groups of cities). Target O(n²·α(n)) with union-find.
Q2. Redundant Connection. A graph started as a tree with n nodes (labeled 1..n) and had one extra edge added. Given the list of n edges, return the edge that can be removed so the graph becomes a tree again. If several qualify, return the one that appears last in the input.
Core problems
Q3. Range Sum Query — Mutable. Design a structure over an integer array supporting update(index, value) (set one element) and sumRange(left, right) (inclusive sum), each in O(log n). Use a Fenwick tree or segment tree.
Q4. Design an LRU Cache. Implement LRUCache(capacity) with get(key) and put(key, value), both running in O(1). On overflow, evict the least recently used entry. get on a missing key returns -1.
Q5. Implement strStr() (KMP). Return the index of the first occurrence of needle in haystack, or -1 if it is not present. Aim for O(n + m) using the KMP prefix function.
Challenge
Q6. Repeated Substring Pattern. Given a string s, return true if it can be built by taking some substring and repeating it two or more times. Solve it in O(n) using the prefix function.
Q7. Count of Smaller Numbers After Self. Given nums, return an array counts where counts[i] is the number of elements to the right of nums[i] that are smaller than it. Target O(n log n) with a Fenwick tree over compressed values.
Done? Review every solution on the advanced answer sheet — even the ones you solved, since there’s often a cleaner approach. Then explore the problem-solving patterns.