← Intuit Interview InsightsSoftware Engineer

Intuit·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate
Jun 2026

Summary

Got a coding problem from Intuit that was more math-heavy than I expected. One of those string manipulation questions that looks approachable until you realize the palindrome angle adds a whole layer of complexity.

Questions Asked (1)

Q1

Given a string of DNA characters, for every possible substring, find the minimum number of character changes needed to make that substring a palindrome. Return the total sum of these minimums across all substrings.

Algorithms & Data Structures
Author's notes

I stared at this for a bit before realizing the key insight: for any substring, you only need to fix characters that don't match their mirror position, and each mismatch costs one change.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem and constraints first, then propose an efficient solution using dynamic programming to compute the minimum changes for all substrings in O(n^2) time. Explain how to build a 2D DP table where dp[i][j] represents the minimum changes for substring s[i..j], and sum these values.

Pro tip: Mention that you can optimize space by only keeping the previous diagonal, but be prepared to discuss trade-offs between time and space. Also, emphasize that you would test with edge cases like empty string, single character, and all same characters.

1. Clarify the problem

Confirm the definition of 'minimum changes' (e.g., changing one character to another) and that substrings are contiguous. Ask about input size to determine expected complexity.

2. Define DP state and recurrence

Let dp[i][j] be the minimum changes to make s[i..j] a palindrome. If s[i] == s[j], dp[i][j] = dp[i+1][j-1]; else dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]).

3. Determine base cases and iteration order

Base cases: dp[i][i] = 0 for length 1, and dp[i][i+1] = 0 if characters equal else 1. Iterate by increasing substring length to ensure subproblems are solved.

4. Compute and sum results

Fill the DP table for all substrings of length 2 to n, and accumulate the sum of dp[i][j] for all i <= j. Return the total sum.

5. Analyze complexity and optimize

Time complexity is O(n^2) and space O(n^2). Discuss possible space optimization to O(n) by using two arrays, and mention that O(n^2) is optimal for this problem.

Key Points to Mention

  • Dynamic programming approach with state dp[i][j] for substring s[i..j]
  • Recurrence relation: if s[i] == s[j], dp[i][j] = dp[i+1][j-1]; else 1 + min(dp[i+1][j], dp[i][j-1])
  • Base cases: single character (0 changes) and two characters (0 if equal, 1 otherwise)
  • Iteration by increasing substring length to avoid recomputation
  • Time complexity O(n^2) and space complexity O(n^2), with possible space optimization to O(n)
  • Handling edge cases: empty string, single character, and all same characters

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.