This page needs a newer browser to run its tools. You can still read everything here.

String patterns interview questions

Interview questions on string patterns: short warm-ups, then what each harder question tests, the first step of a good answer and its follow-ups.

20 questions: 4 warm-ups and 16 with model answers · Levels: Fresher to staff

Warm-up questions

Short questions with short answers, each answered in full.

Fresher to mid

Why does "😀".length give 2 in JavaScript and Java, while len("😀") gives 1 in Python and 4 in Go?

Answered in the lesson Strings in five languages
Fresher to mid

Is building a string with += in a loop quadratic in Python?

Answered in the lesson Strings in five languages
Fresher to mid

Why does centre expansion try 2n − 1 centres on a string of n letters, and what goes wrong with only the n letters?

Answered in the lesson Longest palindromic substring
Fresher to mid

What does π[i] of the prefix function hold, and what is the prefix function of abaab?

π[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of it, called a border; proper means shorter than s[0..i] itself, which would trivially qualify. For abaab: a single letter has no proper border, so π[0] = 0; ab has none either, 0; aba has a, 1; abaa has a, 1; abaab has ab, 2. So π is [0, 0, 1, 1, 2]. The last value says that abaab starts and ends with ab, so its smallest period is 5 − 2 = 3, and a matcher that fails after matching all of abaab tries the border ab next instead of starting again.
From the lesson Shortest palindrome with the KMP prefix function

Questions with model answers

What each question tests, the first step of a good answer and the follow-ups to expect.

Mid to senior

Display names may have at most 20 characters. The browser checks [...name].length, a Java service checks name.length(), and a Go service stores name[:20] of longer names. Some names with emoji pass the browser but fail in Java, and some are stored with a broken last character. Explain why, and define one rule for all three layers.
What it tests

What each language's length counts, why slicing UTF-8 by bytes breaks characters, and a limit defined in grapheme clusters, with a separate byte cap for storage, enforced the same way in every layer.

First step

Count one failing name the way each layer does. "Priya" with a space and four flags of India is 14 code points, so the browser accepts it; 22 UTF-16 code units, so Java rejects it; and 38 UTF-8 bytes, so Go keeps the first 20, which ends inside the fourth flag. A reader sees 10 characters. The layers disagree because they count three different units, and none of them counts what the reader sees.
Follow-ups
- Why do some stored names end with a replacement character?
- Which unit should the limit count, and why not code points?
- How would you shorten a name in Go without a third-party package?
- How do you test that the three layers agree?
From the lesson Strings in five languages
Model answer, Pro. Model answers open with any pass; prices are in the notice on this page.
Opening the model answers with your pass…
Model answers open with any MySmartCoPilot pass.
Pro pass · 1 week₹79$2.99
30 days₹179$5.99
1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so the model answers can’t be opened at the moment. If you have a pass, enter your licence key.
Choose a pass I have a licence key
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 4 minutes
Mid to senior

A teammate finds the longest palindromic substring of a 50,000-character log line with an n × n table of booleans, is_pal[i][j], filled by dynamic programming, and the job runs out of memory. Estimate what the table needs, and say what you would use instead and why.
What it tests

Estimating the memory of a quadratic table in two languages, seeing that the answer needs no table, and choosing centre expansion or Manacher's algorithm from the size of the input.

First step

Count the cells: 50,000² is 2.5 × 10⁹. At one byte each that is 2.5 GB; in a Python list of lists every cell is an 8-byte reference, so about 20 GB. Then ask what the table is used for: the answer only needs the longest palindrome around each centre, which needs no table at all.
Follow-ups
- Does filling only the upper half of the table fix it?
- How long does centre expansion take on 50,000 characters?
- When is a table of palindromes still the right tool?
From the lesson Longest palindromic substring
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

A Java method counts the palindromic substrings of a status log with centre expansion and an int counter. On a log of 120,000 identical heartbeat characters it takes minutes and then prints a negative number. Explain both with numbers, and fix the method.
What it tests

Knowing that equal letters make every substring a palindrome, the 32-bit int limit, the quadratic time of centre expansion on repeated letters, and the linear count from Manacher's radii.

First step

With identical characters every substring is a palindrome: 120,000 × 120,001 / 2 = 7,200,060,000, more than three times 2,147,483,647, so the int wraps around. The same input makes every centre expand to an end of the log, about n²/2 = 7.2 × 10⁹ comparisons.
Follow-ups
- What exactly does the int counter print?
- Is a long enough for every n up to 10⁶?
- How do Manacher's radii give the count in O(n)?
From the lesson Longest palindromic substring
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

Your centre-expansion solution for the longest palindromic substring passes every sample test but times out on a hidden test with n = 200,000. What did that test probably contain, how do you confirm it without seeing it, and what do you change?
What it tests

Knowing that centre expansion is near-linear on random text and quadratic on repetitive text, building worst cases on purpose, and moving to a linear method that is checked against the slow one.

First step

On random letters palindromes are short, so centre expansion is close to linear; a timeout means long palindromes. Build "A" × 200,000 and "AC" × 100,000 and count comparisons: about 2 × 10¹⁰ and 10¹⁰, against about 4 × 10⁵ for Manacher's algorithm.
Follow-ups
- How do you check Manacher's algorithm against the slow method?
- Can centre expansion be kept, with a shortcut, and still pass?
- What else could make a Python solution time out here?
From the lesson Longest palindromic substring
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A solution for the shortest palindrome computes the prefix function of s + reverse(s), with no separator, and takes its last value as the length of the longest palindromic prefix. It fails hidden tests. Find a failing input, explain the failure, and fix it so that it works even if s may contain any character.
What it tests

What a border of the joined string measures, why it can be longer than s, and fixes that do not depend on a character being absent.

First step

Try a word with a long run at its start, such as aaba. The joined string aabaabaa has the border aabaa, five letters, more than the word's four, so the code claims the whole word is a palindrome and returns aaba unchanged.
Follow-ups
- Why can a border of the joined string be longer than s?
- How do you fix it if s may contain every possible character?
- Can you avoid building the joined string at all?
From the lesson Shortest palindrome with the KMP prefix function
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

The prefix-function loop has a while loop inside a for loop. Prove that it makes O(n) comparisons in total, and give a string on which a single letter makes about n of them.
What it tests

An amortised argument with the current border length as the measure, the bound of fewer than 2n comparisons, and a worst case for one step.

First step

Follow k, the length of the border being extended. Each letter raises k by at most 1, every fallback lowers it by at least 1, and k never goes below 0, so the fallbacks over the whole string cannot outnumber the rises.
Follow-ups
- Which string makes one letter cost about n comparisons?
- Does the same bound hold for the matcher that reads a text?
- How can every letter be made to cost O(1) in the worst case?
From the lesson Shortest palindrome with the KMP prefix function
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

A service must raise an alert whenever a 2,000-byte signature appears in a 10 GB stream of network bytes, including overlapping and back-to-back appearances, with little memory and bounded time per byte. Design the matcher and give its memory and time.
What it tests

Using the prefix function as a streaming matcher, keeping overlaps, sizing the memory, and trading memory for a worst-case bound per byte when latency matters.

First step

Store only the signature and its prefix function: 2,000 bytes and 2,000 integers, about 10 KB with 32-bit integers. Read the stream byte by byte, keeping k, the number of signature bytes that end at the current byte.
Follow-ups
- How are overlapping and back-to-back appearances kept?
- What is the longest one byte can take, and how do you bound it?
- The stream arrives in chunks. What must survive between them?
From the lesson Shortest palindrome with the KMP prefix function
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

In the Z-algorithm, why may z[i] start at min(r − i, z[i − l]) when position i lies inside the window [l, r)? When can it grow beyond that value, and why does the whole computation stay linear? Use aabxaabxaab or an example of your own.
What it tests

Reasoning about the copy inside the window, the case where the copy stops before the window's end, and the amortised argument on the window's right end.

First step

Write the window as a copy: s[l:r] equals s[:r − l], so s[i:r] equals s[i − l:r − l], whose match length z[i − l] is already known. Cut at the window's end, that match holds at i too.
Follow-ups
- What happens when z[i − l] is smaller than r − i?
- What happens when it is larger?
- Why does the right end of the window give a linear bound?
From the lesson Z-function: matching, prefix counts and periods
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

Would you use the Z-function or the prefix function for (a) every occurrence of a 50-character pattern in a 2 GB log read from disk in blocks, and (b) how often each prefix of a 100,000-letter string occurs? Defend each choice with the memory and the passes it needs.
What it tests

Knowing what each function's values describe, streaming against whole-string access, estimating memory, and computing one function's answer with the other when needed.

First step

For (a), the prefix function of the pattern is 50 integers, and its matcher keeps one number between blocks, so the log never sits in memory. The Z-function would need pattern, separator and log in one array of about 2 × 10⁹ values.
Follow-ups
- Can the Z-function be made to work on a stream?
- How would you answer (b) with the prefix function instead?
- Which would you write in an interview with twenty minutes left?
From the lesson Z-function: matching, prefix counts and periods
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

Find every start where a 10,000-note jingle plays in a 10,000,000-note transcript with at most one wrong note. A teammate compares every window and the job takes hours. Design a linear method, show it finds exactly the right starts, and give its memory.
What it tests

Combining forward and backward match lengths, the condition for one mismatch and why it is exact, and planning the memory of arrays with ten million values.

First step

Estimate the brute force: about 10⁷ windows of 10⁴ notes, 10¹¹ comparisons. Then split a window at its first wrong note: the notes before it agree with the jingle's start, and the notes after it with the jingle's end.
Follow-ups
- Why is ahead[i] + back[i + m − 1] ≥ m − 1 exactly the right test?
- How much memory do the arrays take, and how can you reduce it?
- How would you allow up to k wrong notes?
From the lesson Z-function: matching, prefix counts and periods
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

Write the overflow check of a 32-bit string-to-integer parser that never holds a value outside the int range, and show it is exact at both ends, including −2147483648. Why do many solutions get the negative end wrong?
What it tests

Turning value · 10 + d ≤ MAX into a check that cannot overflow, the asymmetry of the 32-bit range, and the boundary readings every test list needs.

First step

Rewrite value · 10 + d ≤ 2,147,483,647 as value ≤ (2,147,483,647 − d) / 10. Both sides stay inside the range, and because value is an integer, rounding the right side down changes nothing.
Follow-ups
- Why is returning MIN on a negative overflow right even for −2147483648?
- What does the check look like if you accumulate the value as a negative number?
- Which readings must the tests contain?
From the lesson String to integer (atoi) and run-length encoding
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

A form sends quantities to three services: a Java service calls Integer.parseInt, a Python job calls int(), and a C++ importer calls atoi. Give inputs on which they disagree, explain each difference, and define one rule that all three should share.
What it tests

What each library accepts, from spaces and underscores to other scripts' digits and out-of-range values, the undefined behaviour of atoi, and turning a shared rule into code and tests.

First step

Try " 42", "42 kg", "1_000", "२३" and "3000000000". Java accepts only an optional sign and digits, Python also spaces and underscores, and atoi stops at the first non-digit, with no defined result out of range.
Follow-ups
- Which of the three accept digits from other scripts?
- What happens to 3000000000 in each one?
- How do you make all three follow one rule?
From the lesson String to integer (atoi) and run-length encoding
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

Compress a character array in place into runs of a letter and its count, the count left out when it is 1, and prove the writer never overwrites unread input. A new format writes the count even when it is 1: can that still be done in place, and how?
What it tests

An invariant on two pointers and its arithmetic, recognising when an encoding can grow, and a second pass that writes from the right into spare room.

First step

Compare how far each pointer moves for one run of k letters: the reader moves k, the writer 1 when k is 1 and 1 + digits(k) otherwise. Then show 1 + digits(k) ≤ k for every k ≥ 2.
Follow-ups
- Why does writing counts of 1 break the invariant?
- How much room does the new format need, and can you compute it first?
- Can the decoder work in place too?
From the lesson String to integer (atoi) and run-length encoding
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Fresher to mid

A justified line holds four words with 13 letters in all and must be 24 characters wide. How many spaces go in each gap, which gaps get the extra ones, and how do you compute it without a loop? Which lines must not be justified, and why?
What it tests

Computing a line's spaces and gaps, division with remainder for the distribution, and the rules for the last line and for one-word lines.

First step

The spaces are 24 − 13 = 11 and the gaps 4 − 1 = 3. divmod(11, 3) gives 3 with a remainder of 2: every gap gets 3 spaces, and the first two gaps get one more.
Follow-ups
- What changes if the extra spaces must go to the right?
- Why does a line with one word need its own rule?
- How would you centre a line instead?
From the lesson Text justification and word wrap
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Mid to senior

Prove that putting as many words as fit on each line gives the fewest lines possible. Then explain why the same rule can leave a very uneven right margin, and what you would use when an even margin matters.
What it tests

A proof that greedy stays ahead of any layout, by induction over lines, the difference between the number of lines and the evenness of the margin, and dynamic programming for the most even layout.

First step

Compare greedy with any other valid layout and show by induction that after k lines greedy has placed at least as many words. The key fact: the tail of a line that fits always fits.
Follow-ups
- Give words where greedy leaves a noticeably uneven margin.
- What does the dynamic program cost?
- Why is the last line left out of the measure?
From the lesson Text justification and word wrap
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes
Senior to staff

A justifier that works on English notices misaligns lines on a monospace screen for notices in Japanese and for names with accents. Explain why with an example, and change the width measurement so that every line is exactly as wide as the board.
What it tests

Knowing East Asian Width, combining marks and normalisation, and measuring every step of packing and padding in display columns instead of characters.

First step

Measure one word both ways: 日本語 has 3 characters but fills 6 columns, and é written as e plus a combining accent is 2 characters but 1 column. The justifier counts characters, so its lines come out too long or too short.
Follow-ups
- Where in the algorithm does the width measurement appear?
- Does normalising to NFC solve it?
- What about emoji and flags?
From the lesson Text justification and word wrap
Model answer, Pro.
In the answer:
- Model answer
- Follow-up answers
- Common mistakes
- Rubric
- Variants
- about 3 minutes

The lessons of this module

Strings in five languages Free lesson, Pro answers: 35 minutes
Longest palindromic substring Free core, Pro depth: 10 of 30 minutes free
Shortest palindrome with the KMP prefix function Free intro, Pro: 9 of 35 minutes free
Z-function: matching, prefix counts and periods Free intro, Pro: 7 of 30 minutes free
String to integer (atoi) and run-length encoding Free intro, Pro: 8 of 30 minutes free
Text justification and word wrap Free intro, Pro: 8 of 30 minutes free

All Coding Interview Patterns interview questions · The Coding Interview Patterns track

Warm-up questions

Why does "😀".length give 2 in JavaScript and Java, while len("😀") gives 1 in Python and 4 in Go?

Is building a string with += in a loop quadratic in Python?

Why does centre expansion try 2n − 1 centres on a string of n letters, and what goes wrong with only the n letters?

What does π[i] of the prefix function hold, and what is the prefix function of abaab?

Questions with model answers

A teammate finds the longest palindromic substring of a 50,000-character log line with an n × n table of booleans, is_pal[i][j], filled by dynamic programming, and the job runs out of memory. Estimate what the table needs, and say what you would use instead and why.

A Java method counts the palindromic substrings of a status log with centre expansion and an int counter. On a log of 120,000 identical heartbeat characters it takes minutes and then prints a negative number. Explain both with numbers, and fix the method.

Your centre-expansion solution for the longest palindromic substring passes every sample test but times out on a hidden test with n = 200,000. What did that test probably contain, how do you confirm it without seeing it, and what do you change?

The prefix-function loop has a while loop inside a for loop. Prove that it makes O(n) comparisons in total, and give a string on which a single letter makes about n of them.

A service must raise an alert whenever a 2,000-byte signature appears in a 10 GB stream of network bytes, including overlapping and back-to-back appearances, with little memory and bounded time per byte. Design the matcher and give its memory and time.

In the Z-algorithm, why may z[i] start at min(r − i, z[i − l]) when position i lies inside the window [l, r)? When can it grow beyond that value, and why does the whole computation stay linear? Use aabxaabxaab or an example of your own.

Would you use the Z-function or the prefix function for (a) every occurrence of a 50-character pattern in a 2 GB log read from disk in blocks, and (b) how often each prefix of a 100,000-letter string occurs? Defend each choice with the memory and the passes it needs.

Find every start where a 10,000-note jingle plays in a 10,000,000-note transcript with at most one wrong note. A teammate compares every window and the job takes hours. Design a linear method, show it finds exactly the right starts, and give its memory.

Write the overflow check of a 32-bit string-to-integer parser that never holds a value outside the int range, and show it is exact at both ends, including −2147483648. Why do many solutions get the negative end wrong?

A form sends quantities to three services: a Java service calls Integer.parseInt, a Python job calls int(), and a C++ importer calls atoi. Give inputs on which they disagree, explain each difference, and define one rule that all three should share.

Compress a character array in place into runs of a letter and its count, the count left out when it is 1, and prove the writer never overwrites unread input. A new format writes the count even when it is 1: can that still be done in place, and how?

A justified line holds four words with 13 letters in all and must be 24 characters wide. How many spaces go in each gap, which gaps get the extra ones, and how do you compute it without a loop? Which lines must not be justified, and why?

Prove that putting as many words as fit on each line gives the fewest lines possible. Then explain why the same rule can leave a very uneven right margin, and what you would use when an even margin matters.

A justifier that works on English notices misaligns lines on a monospace screen for notices in Japanese and for names with accents. Explain why with an example, and change the width measurement so that every line is exactly as wide as the board.