MathWorks·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

MathWorks software engineer interview with a meaty string manipulation problem that required algorithm explanation, correctness proof, complexity analysis, and working code. Pretty demanding for a single question but that seems to be their style.

Questions Asked (1)

You have two strings s and t of equal length over lowercase letters. In one move, you can delete any character from s and append it to s's end. What is the minimum number of such moves to turn s into t, and can you always do it? Explain your approach, prove it's correct, analyze the complexity, and write working code.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one took me a minute to even parse correctly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that the operation is a cyclic rotation of a prefix: deleting a character and appending it to the end is equivalent to moving that character to the end, so the final string is a rotation of the original. Then, determine the minimum number of moves by finding the longest suffix of s that is a subsequence of t; the answer is n minus the length of that suffix. Finally, prove correctness, analyze O(n) complexity, and provide clean code.

Pro tip: Emphasize that the operation preserves the relative order of the remaining characters, so the problem reduces to finding the longest suffix of s that appears as a subsequence in t. This insight simplifies the solution and demonstrates strong algorithmic thinking.

1. Understand the operation

Recognize that deleting a character and appending it to the end is equivalent to moving that character to the end, which is a cyclic rotation of a prefix. The final string must be a rotation of the original string.

2. Reduce to subsequence matching

The characters that are never moved must appear in the same relative order in both s and t. Therefore, the unmoved characters form a common subsequence, and to minimize moves, we want to maximize the number of unmoved characters.

3. Find the longest suffix of s that is a subsequence of t

Scan s from right to left and t from right to left to find the longest suffix of s that can be matched as a subsequence in t. The length of this suffix gives the maximum number of characters that can remain unmoved.

4. Compute the answer and prove correctness

The minimum number of moves is n minus the length of the longest matching suffix. Prove that this is optimal by showing that any valid sequence of moves leaves a suffix of s unmoved, and that suffix must be a subsequence of t.

5. Analyze complexity and write code

The algorithm runs in O(n) time and O(1) extra space. Write clean code that implements the two-pointer scan from the end.

Key Points to Mention

The operation is equivalent to moving a character to the end, so the final string is always a rotation of the original string.
The characters that are not moved must appear in the same relative order in both strings, so they form a common subsequence.
To minimize moves, maximize the number of unmoved characters by finding the longest suffix of s that is a subsequence of t.
The minimum number of moves is n minus the length of that longest suffix.
The algorithm runs in O(n) time and O(1) extra space using a two-pointer scan from the end.
It is always possible to transform s into t because we can move all characters one by one to achieve any rotation, but the minimum moves may be less.

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