Meta·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Meta SWE interview with a single coding problem. Not much to report beyond the problem itself.

Questions Asked (1)

Given a string of parentheses, what is the minimum number of parentheses you need to add to make it valid?

Algorithms & Data Structures

Author's notes

Classic stack-based problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a single-pass counter approach: track the number of unmatched closing parentheses and the number of unmatched opening parentheses. The minimum additions equal the sum of these two counts. Alternatively, use a stack to match pairs and count the remaining unmatched parentheses.

Pro tip: Clarify that the problem asks for the minimum number of parentheses to add anywhere, not just at the ends. Mention that a stack-based solution is intuitive but a counter-based solution achieves O(1) space, which is optimal.

1. Understand the problem

Confirm that you need to add parentheses (either '(' or ')') to make the string valid, and you want the minimum number. A valid string has balanced parentheses with no unmatched ones.

2. Choose an approach

Decide between a stack-based method (O(n) space) and a counter-based method (O(1) space). The counter method is more efficient and simpler to implement.

3. Implement the counter method

Initialize open_needed = 0 and close_needed = 0. Iterate through each character: if '(', increment open_needed; if ')', check if open_needed > 0, then decrement open_needed, else increment close_needed. At the end, return open_needed + close_needed.

4. Test with examples

Walk through examples like '())', '(((', and '())((' to verify the counts. For '())', open_needed=0, close_needed=1, total=1. For '(((', open_needed=3, close_needed=0, total=3.

5. Analyze complexity

State that the time complexity is O(n) and space complexity is O(1) for the counter method. Mention that the stack method uses O(n) space in the worst case.

Key Points to Mention

Definition of a valid parentheses string: every opening parenthesis has a matching closing parenthesis in the correct order.
The minimum number of additions equals the number of unmatched closing parentheses plus the number of unmatched opening parentheses.
Counter-based approach: track unmatched opens and unmatched closes in one pass.
Stack-based approach: push '(' onto stack, pop for ')', count remaining stack size and unmatched ')'.
Time complexity O(n) and space complexity O(1) for counter method, O(n) for stack method.
Edge cases: empty string, all opening, all closing, already valid.

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