Eightfold AI·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Interviewed for a software engineer role at Eightfold AI and got a parentheses validation problem. Pretty standard algorithmic question but the details matter more than you'd think.

Questions Asked (1)

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

Stack-based approach is the right move here.

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, ensuring the minimum number of removals.

Pro tip: Clarify whether the input can contain other characters (e.g., digits, symbols) and whether multiple valid outputs are acceptable; this shows attention to detail and avoids assumptions.

1. Clarify requirements and edge cases

Ask about input constraints, character set, and whether any valid result is acceptable. Confirm that only parentheses need removal and that letters must remain in order.

2. Identify unmatched parentheses

Use a stack to track indices of '(' and mark unmatched ')' when encountered. After the first pass, any remaining '(' in the stack are unmatched and should be marked for removal.

3. Build the result string

Iterate through the original string and append characters that are not marked for removal. This yields a valid string with the minimum number of removals.

4. Analyze complexity and test

State that the algorithm runs in O(n) time and O(n) space. Walk through examples like 'a)b(c)d' and edge cases like empty string or all parentheses.

Key Points to Mention

Stack-based approach for matching parentheses
Two-pass algorithm: first mark invalid ')', then invalid '('
Time complexity O(n) and space complexity O(n)
Handling of edge cases: empty string, no parentheses, all parentheses
Preservation of relative order of letters
Minimum removals guaranteed by marking only unmatched parentheses

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