← Eightfold AI Interview Insights

Eightfold AI·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Interviewed for a software engineering role at Eightfold AI and got a parentheses validation problem. Pretty standard coding round, nothing too wild, but the stack-based approach took me a minute to fully work through.

Questions Asked (1)

Q1

Given a string containing parentheses and lowercase letters, remove the minimum number of parentheses to make the string valid, and return any valid result.

Algorithms & Data Structures
Author's notes

I knew right away it was a stack problem but fumbled explaining the removal step.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack-based approach to identify unmatched parentheses: first pass marks invalid closing parentheses, second pass marks invalid opening parentheses. Then build the result by including only characters that are not marked for removal. Alternatively, use a counter-based method to track balance and remove excess parentheses.

Pro tip: Clarify that the problem allows any valid result, so you don't need to find the longest valid string or all possibilities. Also, mention that the solution runs in O(n) time and O(n) space, which is optimal.

1. Understand the problem

Restate the problem: remove the minimum number of parentheses to make the string valid, where valid means every opening parenthesis has a matching closing parenthesis in the correct order. Note that letters are ignored and can be kept.

2. Choose an approach

Decide between a stack-based method (to track indices of unmatched parentheses) or a two-pass counter method (to count invalid parentheses). Both are O(n) time and O(n) space, but the stack method is more intuitive for many.

3. Identify invalid parentheses

First pass: scan left to right, use a stack to match closing parentheses with opening ones; mark unmatched closing parentheses for removal. Second pass: scan right to left to mark unmatched opening parentheses.

4. Construct the result

Build a new string by including only characters that are not marked for removal. Return this string as a valid result.

5. Analyze complexity and edge cases

State that time complexity is O(n) and space complexity is O(n). Discuss edge cases: empty string, all parentheses, no parentheses, already valid string, and strings with only invalid parentheses.

Key Points to Mention

  • Stack-based approach to track indices of unmatched parentheses
  • Two-pass method: left-to-right for closing, right-to-left for opening
  • Marking invalid parentheses and then filtering them out
  • Time and space complexity: O(n) time, O(n) space
  • Edge cases: empty string, no parentheses, all parentheses, already valid
  • Any valid result is acceptable, so no need to optimize for longest valid string

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