String Algorithms and Pattern Matching Questions

Advanced string algorithms for coding interviews: substring search (naive baseline, KMP including streaming use, Rabin-Karp with collision-resistant hashing, Z-algorithm, Boyer-Moore), multiple-pattern matching (Aho-Corasick, including large automata and updates under memory limits), suffix arrays (doubling construction, binary-search queries, Kasai LCP), suffix trees (Ukkonen) and suffix automata, repeated, common and distinct-substring problems (suffix array plus LCP, binary search on length with a rolling hash), the Burrows-Wheeler transform and FM-index, palindromic structures (Manacher), minimal string rotation (Booth), approximate matching beyond the textbook recurrence (banded and bit-parallel edit distance, matching with k mismatches), wildcard and regular-expression matching including backtracking engines, catastrophic backtracking and its mitigations, and string applications built on a trie (multi-pattern dictionaries, autocomplete and prefix search at scale). Also covers Unicode-aware matching and normalization, and adversarial inputs such as hash collisions and the cost of each defence. Boundary: introductory string manipulation, the trie as a data structure, edit-distance and subsequence recurrences, hash-map counting problems, generic data cleaning, NLP pipelines and test-plan design are covered elsewhere.

MediumTechnical
49 practiced

Rabin-Karp can return false positives when two different windows share a hash. Implement a version in C++ that stays correct and makes a collision unlikely even on adversarially chosen input, and explain how you chose the hashing parameters and what the expected cost is.

MediumTechnical
47 practiced

You need to count occurrences of thousands of short patterns across a very long text. Compare running a separate search per pattern against building a single automaton for all patterns. When does each win, and when is it not worth hand-writing the automaton and better to use an optimised library?

MediumTechnical
49 practiced

Implement the Aho-Corasick automaton for multiple-pattern matching. Provide an API with build(patterns: List[str]) and search(text: str) -> List[(pattern_id, index)]. Explain how failure links and output links work, and give complexity in terms of total pattern length P and text length N.

EasyTechnical
57 practiced

Explain the rolling-hash technique used in Rabin-Karp for substring search. Describe how to compute an initial hash and update it in O(1) as the window slides. Using base=256 and modulus=101, outline the hash computations for pattern 'abc' and text 'zabcp'. Explain how collisions arise and how to handle false positives in practice.

MediumTechnical
57 practiced

Implement the KMP string search algorithm in Python: def kmp_search(text: str, pattern: str) -> List[int]. Return all starting indices where the pattern appears in the text in O(n+m) time. Include computation of the prefix-function, handle empty-pattern behavior, and explain complexity.

Unlock Full Question Bank

Get access to all 18 String Algorithms and Pattern Matching interview questions and detailed answers.

Sign in to Continue

Join thousands of developers preparing for their dream job.