Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Meta software engineer interview, one coding round focused on a parentheses problem. I fumbled the approach at first and had to pivot mid-interview, which wasn't a great feeling.

Questions Asked (1)

Given a string with parentheses, remove the minimum number of invalid parentheses to make it valid. Return all possible results.

Algorithms & Data Structures

Author's notes

Started with a stack because it felt intuitive for parentheses problems, but I quickly realized it wasn't getting me to all valid combinations.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use BFS level-by-level removal of parentheses to find the minimum number of deletions, stopping at the first level where valid strings appear. At each level, generate all strings by removing one parenthesis, and collect valid ones while deduplicating to avoid redundant work.

Pro tip: Mention that BFS guarantees minimal removals and that using a set for deduplication and a visited set prevents exponential blowup. Also note that if asked for optimization, you can precompute the number of misplaced parentheses to prune the search space.

1. Validate and define validity

Write a helper function to check if a string is valid: balance never negative and ends at zero. Clarify that only parentheses matter.

2. BFS with level-order traversal

Start with the original string in a queue. For each level, process all strings, check validity, and if any valid, return them. Otherwise, generate next level by removing one parenthesis at each position.

3. Deduplicate and track visited

Use a set to avoid processing the same string multiple times. Only add newly generated strings to the next level if not visited.

4. Collect and return results

When valid strings are found at a level, collect all valid ones from that level and return them immediately, as BFS ensures minimal removals.

5. Analyze complexity and edge cases

Discuss time complexity O(2^n) worst-case but pruned by BFS; space O(2^n). Handle empty string, already valid, and no valid possible (return empty list).

Key Points to Mention

BFS ensures minimum removals because it explores all strings with k removals before k+1 removals.
Use a set for deduplication and a visited set to avoid redundant work.
Validity check: balance counter never negative and ends at zero.
Time complexity is exponential in worst case, but BFS prunes many branches.
Edge cases: empty string, already valid string, string with only invalid parentheses.
Alternative approach: DFS with pruning using precomputed misplaced parentheses counts.

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