Advanced Data Structures & Algorithms quiz

Question 1

What is a Fenwick tree (Binary Indexed Tree) and what operations does it support?

Accepted Answer

O(log n) update, O(log n) query

Answer

O(n) update, O(1) query

Answer

O(1) update, O(log n) query

Answer

O(log n) update, O(n) query

Question 2

What is a Trie's time and space complexity for inserting and searching n words of average length L?

Accepted Answer

O(L) per search

Answer

O(1) per search

Answer

O(n) per search

Answer

O(L·n) per search

Question 3

How does a Red-Black tree differ from an AVL tree in balancing guarantees and practical performance?

Accepted Answer

Red-Black trees require at most 2 rotations on insert

Answer

AVL trees are used in std::map

Answer

Red-Black trees are strictly height-balanced

Answer

AVL trees require more rotations on insert than Red-Black

Question 4

What is a Bloom filter, and what are its false positive and false negative guarantees?

Accepted Answer

False positives are possible, false negatives are not

Answer

False negatives are possible, false positives are not

Answer

Both false positives and negatives are possible

Answer

Neither false positives nor negatives occur

Question 5

How does the Bellman-Ford algorithm handle negative edge weights differently from Dijkstra?

Accepted Answer

O(V·E)

Answer

O(V²)

Answer

O(E log V)

Answer

O(V + E)

Question 6

What is the A* algorithm and how does it improve on Dijkstra?

Accepted Answer

A* requires an admissible heuristic for optimal paths

Answer

A* is always faster than Dijkstra regardless of heuristic

Answer

A* cannot handle weighted graphs

Answer

A* uses h=0, same as Dijkstra

Question 7

How does Prim's MST algorithm work and when is it preferred over Kruskal's?

Accepted Answer

Prim's is preferred for dense graphs

Answer

Prim's is always faster than Kruskal's

Answer

Prim's cannot use a priority queue

Answer

Prim's runs in O(E log E)

Question 8

What is the KMP string matching algorithm and how does it achieve O(n+m) complexity?

Accepted Answer

O(n + m)

Answer

O(n·m)

Answer

O(m log n)

Answer

O(n log m)

Question 9

What is the Z-algorithm for string matching and how does it compute the Z-array?

Accepted Answer

O(n)

Answer

O(n²)

Answer

O(n log n)

Answer

O(n·m)

Question 10

What is the Aho-Corasick algorithm and what problem does it solve in O(n + m_total + z)?

Accepted Answer

O(n + m_total + z)

Answer

O(n·k)

Answer

O(n·m_total)

Answer

O(k·n log n)

Question 11

What is a B-tree and why is it used in database indexing instead of AVL or Red-Black trees?

Accepted Answer

B-trees minimize disk I/O with high-fanout nodes

Answer

B-trees are used because they have O(1) search

Answer

B-trees are simpler to implement than AVL trees

Answer

B-trees only store data at internal nodes

Question 12

What is a van Emde Boas tree and what operations does it support in O(log log U)?

Accepted Answer

O(log log U)

Answer

O(log n)

Answer

O(sqrt(U))

Answer

O(1)

Question 13

What is the Hungarian algorithm and what problem does it solve?

Accepted Answer

O(n³)

Answer

O(n²)

Answer

O(n⁴)

Answer

O(n² log n)

Question 14

What is the Cartesian tree and how is it constructed in O(n) using a stack?

Accepted Answer

O(n)

Answer

O(n log n)

Answer

O(n²)

Answer

O(log n)

Question 15

What is heavy-light decomposition and what queries does it optimize?

Accepted Answer

O(log² n) per path query

Answer

O(n) per path query

Answer

O(sqrt(n)) per path query

Answer

O(n log n) per path query

Question 16

What is the Sieve of Eratosthenes and its time complexity?

Accepted Answer

O(n log log n)

Answer

O(n²)

Answer

O(n log n)

Answer

O(n)

Question 17

What is the sparse table data structure and what query does it answer in O(1)?

Accepted Answer

O(1) query

Answer

O(log n) query

Answer

O(sqrt n) query

Answer

O(n) query

Question 18

What is a persistent data structure and how is a persistent segment tree implemented?

Accepted Answer

O(log n) new nodes per update

Answer

O(n) nodes per update

Answer

O(n log n) nodes per update

Answer

O(1) new nodes per update

Question 19

How does Quickselect find the k-th smallest element in O(n) average time?

Accepted Answer

O(n) average

Answer

O(n log n) average

Answer

O(n²) average

Answer

O(log n) average

Question 20

How does Tarjan's algorithm find all SCCs in O(V + E)?

Accepted Answer

O(V + E)

Answer

O(V²)

Answer

O(E log V)

Answer

O(V·E)

Question 21

Explain Manacher's algorithm for finding all palindromic substrings in O(n).

Accepted Answer

O(n)

Answer

O(n²)

Answer

O(n log n)

Answer

O(n·m)

Question 22

What is the Convex Hull Trick in DP optimization and when does it apply?

Accepted Answer

Reduces O(n²) DP to O(n) or O(n log n)

Answer

Only works for maximization problems

Answer

Requires all slopes to be positive

Answer

Reduces O(n³) DP to O(n²)

Question 23

Describe the Divide and Conquer optimization for DP problems.

Accepted Answer

Reduces O(n²) to O(n log n) per DP layer

Answer

Requires opt(i) to be non-monotone

Answer

Only works for 1D DP

Answer

Reduces O(n³) to O(n)

Question 24

How does the Small-to-Large merging technique achieve O(n log n) for tree set queries?

Accepted Answer

O(n log n)

Answer

O(n²)

Answer

O(n log² n)

Answer

O(n sqrt n)

Question 25

What is the Fast Fourier Transform (FFT) and how does it speed up polynomial multiplication?

Accepted Answer

O(n log n)

Answer

O(n²)

Answer

O(n)

Answer

O(n² log n)

Question 26

What are amortized analysis and the three techniques for computing amortized cost?

Accepted Answer

Aggregate, Accounting, Potential

Answer

Best-case, Average-case, Worst-case

Answer

Induction, Substitution, Master Theorem

Answer

Greedy, DP, Divide and Conquer

Question 27

How does the sqrt decomposition technique solve range queries in O(sqrt n) time?

Accepted Answer

O(sqrt n)

Answer

O(n)

Answer

O(log n)

Answer

O(n/sqrt n)

Question 28

How does the DSU on tree (small-to-large DFS) technique solve subtree query problems in O(n log n)?

Accepted Answer

O(n log n)

Answer

O(n²)

Answer

O(n log² n)

Answer

O(n)

Test yourself