Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Meta coding round focused entirely on a string DP problem. Nothing behavioral, just one meaty algorithm question with a bunch of follow-ups on optimization. Left feeling okay but not great.

Questions Asked (1)

Given a string and an integer k, can the string be turned into a palindrome by deleting at most k characters? What is the minimum number of deletions needed, and how does your algorithm determine whether that minimum is within k?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is a classic longest palindromic subsequence reframing and I knew that going in, which helped.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the minimum deletions to make the string a palindrome, which equals the string length minus the length of the longest palindromic subsequence (LPS). Use dynamic programming to compute the LPS length in O(n^2) time, then check if n - LPS <= k. Explain the recurrence and how it captures the deletion decisions.

Pro tip: Mention that you can optimize space to O(n) by using a 1D DP array, and clarify that the problem asks for the minimum deletions, not just whether it's possible within k. This shows you understand both correctness and efficiency.

1. Clarify the problem and constraints

Confirm that the goal is to find the minimum number of deletions to make the string a palindrome, and that we need to check if that minimum is <= k. Discuss input size to determine if O(n^2) is acceptable.

2. Relate to longest palindromic subsequence

Explain that the minimum deletions equals n - LPS length, because the characters not in the LPS must be deleted. This reduces the problem to computing the LPS.

3. Define the DP recurrence

Let dp[i][j] be the LPS length for substring s[i..j]. If s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2; else dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Base cases: dp[i][i] = 1, dp[i][i-1] = 0.

4. Compute and check against k

Fill the DP table in increasing order of substring length. After computing, the minimum deletions is n - dp[0][n-1]. Return whether this value is <= k.

5. Discuss complexity and optimizations

State time complexity O(n^2) and space O(n^2), but mention that space can be reduced to O(n) by only keeping the previous row. Also note that if k is small, early termination or other approaches might be possible.

Key Points to Mention

Minimum deletions = n - length of longest palindromic subsequence (LPS).
Dynamic programming recurrence for LPS: match ends or take max of skipping one end.
Base cases: single character is a palindrome of length 1; empty substring length 0.
Time complexity O(n^2) and space complexity O(n^2), with O(n) space optimization.
Comparison of minimum deletions with k to answer the yes/no question.
Edge cases: empty string, k >= n, already palindrome.

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