Morgan Stanley·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Morgan Stanley software engineer interview that was basically one meaty dynamic programming problem. The question had enough edge cases to keep you busy for a while, and they wanted the full treatment: working solution, complexity analysis, and a follow-up optimization.

Questions Asked (1)

Given a non-empty string of digits, count the number of ways to decode it using the mapping 1→'a', 2→'b', ..., 26→'z'. Zeros can only appear as part of '10' or '20'. Implement an O(n) solution in C++, explain how you handle zeros and invalid states, analyze time and space complexity, and provide a space-optimized version.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew this was a DP problem the second I read it, but the zeros tripped me up more than I expected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by defining a DP recurrence where dp[i] represents the number of ways to decode the prefix of length i, then handle single-digit and two-digit cases while carefully managing zeros and invalid states. Implement the O(n) solution iteratively, analyze time and space complexity, and finally present a space-optimized version using two variables.

Pro tip: Emphasize that zeros are only valid when preceded by '1' or '2', and explicitly discuss how you detect and handle invalid states (e.g., leading zero or '30', '40', etc.) to show robustness. Also, mention that the space-optimized version is often preferred in production code for large inputs.

1. Define the DP state and recurrence

Let dp[i] be the number of ways to decode the first i characters. For each position, consider if the current digit can stand alone (1-9) and if the last two digits form a valid number (10-26).

2. Handle zeros and invalid states

A zero cannot be decoded alone; it must be part of '10' or '20'. If a zero appears at the start or after a digit other than 1 or 2, the entire string is invalid (return 0).

3. Implement O(n) solution in C++

Use an array dp of size n+1, initialize dp[0]=1, and iterate through the string, updating dp[i] based on single and double digit decodings, with checks for zeros.

4. Analyze time and space complexity

Time complexity is O(n) because we process each character once. Space complexity is O(n) for the dp array, but can be optimized to O(1) by keeping only the last two values.

5. Provide space-optimized version

Replace the dp array with two variables (prev and curr) to store the number of ways for the previous two positions, updating them iteratively.

Key Points to Mention

DP recurrence: dp[i] = (if s[i-1] != '0' then dp[i-1] else 0) + (if s[i-2..i-1] is between 10 and 26 then dp[i-2] else 0)
Zero handling: zeros are only valid as part of '10' or '20'; otherwise, return 0
Invalid states: leading zero, or zero preceded by a digit other than 1 or 2, or any two-digit number >26
Time complexity O(n) and space complexity O(n) for basic DP, O(1) for optimized version
Space optimization: use two variables to store previous results instead of an array
Edge cases: empty string (though problem says non-empty), string with only zeros, string with '0' at start

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