Walmart·Backend Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Backend engineer screen with a string manipulation problem. Pretty focused session, just the one coding question and some back-and-forth on the space complexity constraint.

Questions Asked (1)

Given two strings that may contain a special delete character, determine whether the two strings resolve to the same final string after applying all deletions. You must do this in O(1) auxiliary space.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The naive approach is obvious: simulate a stack for each string and compare.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pointer technique starting from the end of both strings, maintaining a skip count for each to handle delete characters. Compare characters while skipping the appropriate number of characters, ensuring O(1) auxiliary space by only using a few integer variables.

Pro tip: Clarify the delete character and its behavior upfront (e.g., does it delete the previous character or itself?), and mention that this approach is optimal for space-constrained environments like embedded systems or high-performance backends.

1. Clarify the problem

Confirm the delete character (e.g., '#') and its semantics: it deletes the immediately preceding character in the string. Also confirm that multiple deletes can occur consecutively.

2. Choose the right traversal direction

Traverse from the end of both strings because deletions affect characters to the left. This allows you to process deletions naturally without needing to backtrack.

3. Implement two-pointer with skip counts

Maintain two pointers (i and j) and two skip counters. When encountering a delete character, increment the skip counter; otherwise, if skip > 0, decrement skip and move the pointer; else compare characters.

4. Handle remaining characters

After one pointer reaches the start, continue processing the other string to apply any remaining skips, then check if both pointers are exhausted.

5. Analyze complexity and edge cases

State that time complexity is O(n + m) and space is O(1). Discuss edge cases like empty strings, strings with only deletes, and different lengths.

Key Points to Mention

Two-pointer technique from the end to handle deletions efficiently.
O(1) auxiliary space by using only integer variables for indices and skip counts.
Time complexity O(n + m) where n and m are the lengths of the strings.
Handling of consecutive delete characters and their cumulative effect.
Edge cases: empty strings, strings that become empty after deletions, and strings with no deletes.
Comparison of this approach to using a stack (which would require O(n) space) to highlight the space optimization.

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