DSA interview question

Z-Function (Z-Array)

Hard · Algorithms · Topics: string, pattern matching

The problem

You're optimizing the same "find in file" search engine, but this time your tech lead wants to evaluate an alternative to KMP — the Z-algorithm — because it generalizes more cleanly to multi-pattern matching and some plagiarism-detection pipelines your team is exploring. Your task: given a string s, compute its Z-array, where Z[i] is the length of the longest substring starting at index i that is also a prefix of s (with Z[0] conventionally defined as 0 or len(s), depending on convention — clarify this with your interviewer).

Example: s = "aabcaabxaaaz" → Z = [0,1,0,0,3,1,0,0,2,2,1,0].

Function signature

vector<int> zFunction(string s);

Test cases

Input `s`	Output `Z`	Explanation
`"aabcaabxaaaz"`	`[0,1,0,0,3,1,0,0,2,2,1,0]`	Z[4]=3 because "aab" at index 4 matches prefix "aab"
`"aaaa"`	`[0,3,2,1]`	Each position matches a decreasing-length prefix of all-'a's
`"abcabcabc"`	`[0,0,0,6,0,0,3,0,0]`	Z[3]=6, full repeating match of "abcabc"
`"aaa"`	`[0,2,1]`	Simple repeated character case
`"a"`	`[0]`	Single character — trivially 0 by convention
`""`	`[]`	Empty string edge case
`"abab"`	`[0,0,2,0]`	Z[2]=2 because "ab" at index 2 matches prefix "ab"

(Always verify with your actual implementation — Z[0] convention varies by source, confirm with interviewer before assuming.)

How interviewers phrase it

"Compute the Z-array for a given string, where Z[i] is the length of the longest common prefix between s and s[i:]."
"Given a string, for every position, tell me how far it matches the beginning of the string."
Less commonly asked standalone — more often as a building block for a bigger problem (e.g., "find all occurrences of pattern in text" or "find the smallest period of a string"), so be ready for the interviewer to pivot to an application immediately after.

Clarifying questions to ask

What's the expected convention for Z[0]? (Most standard implementations either leave it 0 or set it to len(s) — clarify and state your choice explicitly, since both are used in literature.)
Are we 0-indexed?
Is this meant to be a standalone problem, or will it feed into pattern matching (text + pattern concatenated with a separator)? (This affects how you frame your solution discussion.)
What's the input size constraint? (Push toward confirming O(n) is required, not O(n²) naive comparison.)
Character set / case sensitivity assumptions?

Follow-ups to expect

"How would you use the Z-array to do pattern matching (find pattern in text)?"
"How is this different from the KMP LPS array? When would you prefer one over the other?"
"Can you find the smallest period of a string using the Z-array?"
"Can you compute all occurrences of a pattern in a text using the Z-array, and compare time/space against your earlier KMP solution?"
"Walk through the O(n) proof — why doesn't the inner while loop make this O(n²)?"
"Can you extend this to 2D string matching or multiple pattern search?"

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