Ace strStr(): Rabin-Karp Interview Prep: A Complete Guide

Look, I've sat across from enough whiteboard-wielding interviewers to tell you this: the strstr() problem, or string searching in general, despite its apparent simplicity, separates the wheat from the chaff. It's not just about getting an answer; it's about understanding why certain algorithms shine. And when they hit you with "optimize this," your mind better jump to things like Rabin-Karp. I bombed an interview once because I couldn't articulate the intuition behind its rolling hash effectively enough. Don't make my mistake.

This isn't about memorizing code. It's about understanding the core idea, the trade-offs, and how to talk about them under pressure. Rabin-Karp, at its heart, is a probabilistic algorithm that uses hashing to quickly filter out impossible matches, then performs character-by-character comparisons only on promising candidates. It's elegant. It's also often misunderstood.

Why Rabin-Karp, Seriously?

You're probably thinking, "Why Rabin-Karp? Isn't KMP faster in the worst case?" You're right, KMP is $O(N+M)$ worst-case, where N is the text length and M is the pattern length, while Rabin-Karp can degrade to $O(NM)$ if you have terrible hash collisions. But here's the kicker: average case, Rabin-Karp often performs just as well, if not better, especially with a good hash function and large alphabet sizes. More importantly for interviews, it demonstrates a different class of algorithmic thinking—using hashing for speed, probabilistic approaches, and modular arithmetic. Interviewers love seeing that versatility.

Think about it: you want to find a pattern "ABC" in "XYZABCDEF". A naive approach checks "XYZ", then "YZA", then "ZAB", then "ABC". Each check might be M comparisons. That's $O(NM)$. Rabin-Karp says, "Let's calculate a hash for 'ABC'. Now, let's calculate a hash for 'XYZ'. Different? Move on. Calculate hash for 'YZA'. Different? Move on." It only does a full character comparison when the hashes match. This drastically cuts down on the character comparisons.

The Core Idea: Rolling Hashes

The magic of Rabin-Karp lies in its "rolling hash" function. You don't recalculate the hash of each substring from scratch. That would be too slow, $O(M)$ for each substring, bringing you back to $O(NM)$ territory. Instead, you update the hash in constant time.

Imagine we have a string "ABCDEF" and a pattern "CDE".

1. Calculate the hash for "ABC". Let's say it's H("ABC").
2. To get the hash for "BCD", you don't re-hash. You subtract the contribution of 'A', multiply by some base (like a prime number), and add the contribution of 'D'. H("BCD") = (H("ABC") - value('A') * base^(M-1)) * base + value('D') (all modulo some large prime Q).

This constant-time update is crucial. It lets you compute hashes for all N-M+1 substrings of length M in $O(N)$ time, after an initial $O(M)$ hash calculation for the first window.

The hash function itself is usually a polynomial rolling hash. Each character c gets a numeric value (e.g., c - 'a' + 1). hash = (char_val1 * base^(M-1) + char_val2 * base^(M-2) + ... + char_valM * base^0) % Q

You'll need a large prime Q to minimize collisions. 10^9 + 7 or 10^9 + 9 are common choices. A good base is also important, often a prime slightly larger than your alphabet size (e.g., 31 for lowercase English).

Implementing the Beast: Key Steps and Pitfalls

Let's break down the implementation steps. When you're coding this on a whiteboard, clarity matters more than micro-optimizations.

1. Choose your base and modulus (Q): As discussed, a prime base and a large prime Q are essential.
2. Precompute base^(M-1) % Q: You'll need this value to "remove" the leading character's contribution during the hash roll. Do this once. Let's call this h_power.
3. Calculate initial pattern hash: Iterate through the pattern, applying the polynomial hash formula. Store this as pattern_hash.
4. Calculate initial text window hash: Do the same for the first M characters of the text. Store as text_hash_current.
5. Compare and slide:
   • If text_hash_current == pattern_hash, perform a character-by-character comparison between the current text window and the pattern. If they match, you've found an occurrence. This is the "verification" step.
   • For the next window, update text_hash_current: text_hash_current = (text_hash_current - text[i-M] * h_power % Q + Q) % Q (adding Q before % Q handles negative results from subtraction) text_hash_current = (text_hash_current * base % Q + text[i] % Q) % Q
   • Repeat until you've processed the entire text.

One common pitfall: handling negative results from the modulo operator. In C++/Java, (-5 % 3) might be -2. You always want a positive remainder. The + Q) % Q trick handles this robustly.

Another one: integer overflow. The hash values can get huge before the modulo. Ensure you use long long in C++ or long in Java for hash calculations, then apply the modulo.

The Interviewer's Favorite Follow-Ups

They won't just let you slide after writing the code. Be ready for these:

• "What if there's a hash collision?" This is the core weakness. Explain that a collision means hash(substring1) == hash(substring2) even if substring1 != substring2. Your full character comparison step handles false positives (hash matches, but string doesn't). It doesn't cause false negatives (missing a match).
• "How do you minimize collisions?"
  • Choose a large prime Q.
  • Choose a good base (often a prime, slightly larger than your alphabet size).
  • Sometimes, using two different hash functions with different base and Q values. If both hashes match, the probability of a true match skyrockets. This is a great point to bring up for an "extra credit" discussion.
• "What's the worst-case time complexity, and when does it occur?" $O(NM)$. It occurs when you have catastrophic hash collisions. Think of a pattern "AAAA" and text "AAAAAABAA". If your hash function produces the same hash for "AAAA" and "AAAB", you'll do many full character comparisons. This is why the probabilistic nature is important to discuss.
• "Compare Rabin-Karp to KMP/Z-algorithm."
  • KMP: Deterministic, $O(N+M)$ worst-case. Preprocessing builds a "LPS array" (longest proper prefix suffix) to avoid re-scanning text characters. More complex to understand and implement correctly.
  • Rabin-Karp: Probabilistic, $O(N+M)$ average, $O(NM)$ worst-case. Simpler to grasp the core idea, easier to implement compared to KMP's LPS array logic. Good for multiple pattern searches (precompute pattern hashes once, then check against text hashes).
  • Z-Algorithm: Also deterministic $O(N+M)$. Builds a Z-array which stores the length of the longest substring starting at index i that is also a prefix of the string. Very powerful but also has its own complexity.

This comparison shows you understand the broader string-searching landscape, not just one algorithm.

A Word on Practicality and When to Use It

In the real world, for a single pattern search, optimized library functions (which often use hybrid approaches or advanced algorithms like Boyer-Moore) will almost always beat your hand-rolled Rabin-Karp. However, Rabin-Karp shines when you're searching for multiple patterns in a single text, or when you need to find duplicate substrings within a text. You can precompute the hash of each pattern just once, then efficiently check against text window hashes.

This also applies to problems like finding the longest common substring of two strings. Rabin-Karp can be a component in a binary search approach on the substring length.

Don't just regurgitate facts. Show them you get it. Discuss the trade-offs. Mention the probabilistic nature and how you mitigate its risks. That's what a senior engineer does. That's what shows real understanding.

Ready to Ace Your Next Interview?

Practice with AI-powered mock interviews tailored to your target role and company. Start Practicing for Free | Explore Interview Prep