Data Structures & Algorithms Specialized Algorithms & Interview Prep Syllabus

Specialized Algorithms & Interview Prep syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Specialized Algorithms & Interview Prep in Data Structures & Algorithms, not a summary of it.

1. 1

   String Algorithms

   4 topics

   • Pattern Matching Overview
   • KMP Algorithm
   • Rabin-Karp Algorithm
   • Z-Algorithm and Suffix Structures
2. 2

   Computational Complexity

   3 topics

   • Complexity Classes
   • Reductions
   • Approximation Algorithms
3. 3

   Problem-Solving Patterns

   3 topics

   • Common Patterns
   • Top-K Elements Pattern
   • Subsets and Permutations Pattern
4. 4

   Interview Strategy

   4 topics

   • Approaching Problems
   • Communicating Complexity Tradeoffs
   • Coding Best Practices
   • Mock Interviews and Practice Plans

Specialized Algorithms & Interview Prep flashcards for Data Structures & Algorithms

25 of 56 cards from the Specialized Algorithms & Interview Prep deck — real questions with worked answers.

1. What is the goal of a string pattern matching algorithm?

   To find all occurrences (or the first occurrence) of a pattern string $P$ of length $m$ inside a text string $T$ of length $n$, typically with $m \leq n$.

2. What is the time complexity of the naive (brute-force) string matching algorithm in the worst case?

   $O(n \cdot m)$, because for each of the $n - m + 1$ alignments it may compare up to $m$ characters (e.g., $T = a^{n}$, $P = a^{m-1}b$).

3. Name the three canonical linear-time single-pattern string matching algorithms and their shared complexity.

   KMP, Rabin-Karp (expected), and the Z-Algorithm, each achieving $O(n + m)$ time.

4. What does the KMP algorithm precompute, and what does it represent?

   The failure/prefix function $\pi$, where $\pi[i]$ is the length of the longest proper prefix of $P[0..i]$ that is also a suffix of $P[0..i]$.

5. What is the overall time and space complexity of the KMP algorithm?

   Time $O(n + m)$ (preprocessing $O(m)$ plus search $O(n)$) and auxiliary space $O(m)$ for the prefix table.

6. In KMP, when a mismatch occurs at pattern index $j > 0$, how is $j$ updated?

   Set $j \gets \pi[j-1]$, avoiding re-comparison of already-matched characters; the text pointer $i$ never moves backward.

7. Why does KMP never re-examine text characters, giving linear time?

   The text index only advances; the prefix function lets the pattern shift so that previously matched characters are reused rather than re-scanned, so total character comparisons are $O(n)$.

8. Compute the KMP prefix function $\pi$ for the pattern "ABABAC".

   $\pi = [0, 0, 1, 2, 3, 0]$ for positions of A, B, A, B, A, C respectively.

9. What is the core idea of the Rabin-Karp algorithm?

   Compare hash values of the pattern and each length-$m$ substring of the text using a rolling hash; only when hashes match is a full character-by-character verification done.

10. Give the polynomial rolling hash formula for a string $s$ of length $m$ with base $b$ modulo $q$.

    $$H(s) = \left( \sum_{i=0}^{m-1} s[i] \cdot b^{\,m-1-i} \right) \bmod q.$$

11. In Rabin-Karp, how is the hash updated when the window slides by one character (from $T[i..i+m-1]$ to $T[i+1..i+m]$)?

    $$H_{new} = \left( (H_{old} - T[i] \cdot b^{m-1}) \cdot b + T[i+m] \right) \bmod q,$$ an $O(1)$ update.

12. What are the average-case and worst-case time complexities of Rabin-Karp?

    Average/expected $O(n + m)$ with a good modulus; worst case $O(n \cdot m)$ when many hash collisions (spurious hits) force full verifications.

13. Why is Rabin-Karp especially well suited to multiple-pattern search?

    Multiple patterns of the same length can be stored in a hash set; each text window hash is checked against the set in $O(1)$ expected time, giving efficient multi-pattern matching.

14. What is the Z-array $Z[i]$ of a string $S$?

    $Z[i]$ is the length of the longest substring starting at index $i$ that matches a prefix of $S$ (with $Z[0]$ conventionally 0 or $|S|$).

15. How is pattern matching performed using the Z-algorithm?

    Build $Z$ for the concatenation $P + \$ + T$ (with a separator $\$$ not in either string); any position where $Z[i] = m$ (the pattern length) marks an occurrence of $P$ in $T$.

16. What is the time complexity of computing the Z-array?

    $O(n)$ for a string of length $n$, maintained via the current $[l, r]$ Z-box window.

17. What is a suffix array and its typical construction complexity?

    A sorted array of the starting indices of all suffixes of a string; it can be built in $O(n \log n)$ (or $O(n)$ with advanced algorithms like DC3/SA-IS).

18. What is a suffix tree and what query does it enable in $O(m)$ time?

    A compressed trie of all suffixes of a string; it lets you test whether a pattern of length $m$ occurs in $O(m)$ time, and is built in $O(n)$ (Ukkonen's algorithm).

19. Define the complexity class $\mathbf{P}$.

    The set of decision problems solvable by a deterministic Turing machine in polynomial time, i.e., in $O(n^{k})$ for some constant $k$.

20. Define the complexity class $\mathbf{NP}$.

    The set of decision problems whose 'yes' instances have certificates verifiable by a deterministic machine in polynomial time (equivalently, solvable by a nondeterministic machine in polynomial time).

21. What does it mean for a problem to be NP-hard?

    Every problem in $\mathbf{NP}$ reduces to it in polynomial time; it is at least as hard as every NP problem but need not itself be in $\mathbf{NP}$.

22. What does it mean for a problem to be NP-complete?

    It is both in $\mathbf{NP}$ and NP-hard; it is among the hardest problems in $\mathbf{NP}$, and a polynomial algorithm for any one would put all of $\mathbf{NP}$ in $\mathbf{P}$.

23. State the central open question relating P and NP and the known containment.

    It is unknown whether $\mathbf{P} = \mathbf{NP}$; it is known that $\mathbf{P} \subseteq \mathbf{NP}$, and most researchers conjecture $\mathbf{P} \neq \mathbf{NP}$.

24. Which problem was the first proven NP-complete, and by which theorem?

    Boolean satisfiability (SAT), by the Cook-Levin theorem.

25. What is a polynomial-time (Karp) reduction from problem $A$ to problem $B$, written $A \leq_{p} B$?

    A polynomial-time computable function $f$ mapping instances of $A$ to instances of $B$ such that $x$ is a yes-instance of $A$ iff $f(x)$ is a yes-instance of $B$.

See more Specialized Algorithms & Interview Prep flashcards →

Planning Specialized Algorithms & Interview Prep for Data Structures & Algorithms

Specialized Algorithms & Interview Prep (Data Structures & Algorithms) FAQ