PPractick

The problem

Back at the plagiarism-detection system you designed the hashing theory for — now your tech lead wants the actual search algorithm implemented: given a text and a pattern, find all starting indices where pattern occurs in text, using a rolling hash so you don't recompute the hash from scratch at every window position. This is Rabin-Karp — average-case O(n+m), with a worst-case fallback to verify matches character-by-character to guard against hash collisions.

Example: text = "ABABDABACDABABCABAB", pattern = "ABABCABAB" → pattern occurs at index 10.

Function signature

vector<int> rabinKarp(string text, string pattern);

Test cases

text	pattern	Output (indices)	Explanation
"ABABDABACDABABCABAB"	"ABABCABAB"	[10]	Single occurrence at index 10
"AAAAA"	"AA"	[0,1,2,3]	Overlapping matches allowed
"ABCABCABC"	"ABC"	[0,3,6]	Multiple non-overlapping matches
"ABCDEF"	"XYZ"	[]	No occurrence
"AAAA"	"AAAAA"	[]	Pattern longer than text
"hello world hello"	"hello"	[0,12]	Two separate matches
"aaa"	"a"	[0,1,2]	Single-char pattern, every position matches

How interviewers phrase it

• "Find all occurrences of a pattern in a text using a rolling hash technique."
• "Implement Rabin-Karp."
• Sometimes the interviewer first asks the hashing theory question (prefix hash, polynomial hash), then escalates to "now apply that to search for a pattern" — be ready for this two-step flow.

Clarifying questions to ask

1. Are overlapping matches allowed (e.g., pattern "AA" in "AAAA")? (Yes typically — confirm.)
2. Should I verify hash matches with an actual character-by-character comparison to rule out false positives (collisions), or is approximate/probabilistic correctness acceptable for this discussion? (Always verify in production-quality code — state this explicitly even if the interviewer says it's optional.)
3. Single hash or double hashing? (Mention double hashing reduces collision risk significantly — confirm if they want you to implement it or just discuss it.)
4. What are the size constraints on text and pattern? (Large inputs reinforce need for O(n+m) average case via rolling hash, not recomputing each window's hash from scratch — which would be O(n*m).)
5. Is pattern guaranteed non-empty? Behavior on empty text/pattern?

Follow-ups to expect

1. "Why do you need to verify with character comparison after a hash match? Doesn't that ruin the time complexity benefit?"
2. "Derive the rolling hash update formula — how do you go from hash(s[i..i+m-1]) to hash(s[i+1..i+m]) in O(1)?"
3. "Compare Rabin-Karp vs KMP — when would you actually prefer Rabin-Karp in practice?"
4. "What happens with a fixed/known modulus in a competitive programming judge — could someone construct an adversarial test case against you?"
5. "Can you extend this to search for multiple patterns simultaneously in one pass?"
6. "What if pattern length varies among multiple patterns you're searching for?"

Related questions

• Wildcard matching Hard
• Z function Hard
• KMP Algorithm or LPS array Hard
• Hashing In Strings | Theory Easy
• Letter Combinations of a Phone Number Hard
• Palindrome partitioning Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in