DSA interview question

String Hashing — Theory

Easy · Algorithms · Topics: string, hashing, theory

The problem

You're building a plagiarism detection system for an online coding judge (think: detecting if two submitted code files share large identical chunks, or detecting duplicate questions in a Q&A platform). Comparing substrings character-by-character every time is too slow when you need to do millions of comparisons across huge texts. Your tech lead asks you to explain — conceptually and with code — how string hashing (specifically polynomial rolling hash, as used in Rabin-Karp) lets you compare substrings in O(1) after O(n) preprocessing, and why this is risky (collisions) compared to deterministic methods like KMP/Z-function.

This is a theory/conceptual topic — interviewers use it to test whether you understand the why behind hashing, not just whether you can paste a formula.

Function signature

(Theory questions typically still expect you to implement core utilities — here are the standard ones to know cold.)

// Precompute hash array and power array for a string
void computeHashes(const string& s, vector<long long>& hashArr, vector<long long>& powArr, long long mod, long long base);

// Get hash of substring s[l..r] (inclusive) in O(1) using precomputed prefix hashes
long long getSubstringHash(int l, int r, const vector<long long>& hashArr, const vector<long long>& powArr, long long mod);

// Compare if two substrings are equal using hashing
bool compareSubstrings(int l1, int r1, int l2, int r2, const vector<long long>& hashArr, const vector<long long>& powArr, long long mod);

Test cases

Scenario	Expected Behavior
`s = "abcabc"`, compare `s[0..2]` ("abc") and `s[3..5]` ("abc")	Hashes equal → substrings equal
`s = "abcabd"`, compare `s[0..2]` ("abc") and `s[3..5]` ("abd")	Hashes differ → substrings different
Two different strings producing the same hash (collision)	False positive — hashing says "equal" but they're not — must discuss mitigation
Very large text (10⁶ chars), repeated substring queries	O(1) per query after O(n) preprocessing — show why this beats O(n) per naive compare
Single character string	Hash = value of that one character (base case)

How interviewers phrase it

"How would you efficiently compare if two substrings of a large string are equal, many times over?"
"Explain how string hashing works and where you'd use it over KMP or Z-function."
"What's Rabin-Karp, and how does it differ from KMP?"
Often asked as a discussion/whiteboard question rather than "write the code" — but be ready to write the precompute + query functions if asked.

Clarifying questions to ask

Are we looking for an algorithm to do a single pattern search (Rabin-Karp), or to answer many repeated substring-equality queries (precomputed prefix hashing)? (Different framing, same underlying math.)
Should I worry about collisions, or is this a conceptual discussion where I can mention them without full mitigation code?
What's the expected hash modulus/base — should I use a single hash or double hashing (two independent mod/base pairs) to reduce collision probability?
Is this purely theoretical, or do you want we to also code the rolling hash for pattern search (Rabin-Karp)?

Follow-ups to expect

"What is a collision, and how do you reduce the chance of one?"
"Why use a prime base and a prime modulus?"
"Explain Rabin-Karp's rolling hash — how do you update the hash in O(1) as the window slides?"
"Compare hashing vs KMP vs Z-function — when would you choose each?"
"How would you use hashing combined with binary search to find the Longest Common Prefix of two substrings in O(log n)?"
"What's the risk of using a fixed, well-known modulus like 10^9+7 in a competitive setting?"
"Can you find all occurrences of a pattern in a text using hashing (Rabin-Karp), and what's the worst-case complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview