Eightfoldai·Software Engineer·Technical Phone Screen
Jun 2026
Interviewed for a software engineering role at Eightfold AI and got a parentheses removal problem. Pretty standard coding round but the follow-ups pushed it further than I expected.
- Given a string with lowercase letters and parentheses, remove the minimum number of parentheses to make the string valid. A valid string means every closing paren has a matching opener before it and the total count is balanced. Return any valid result.
- Follow-up: instead of returning the string, can you just return the count of minimum removals needed?
- Follow-up: if there are multiple valid answers with the same minimum removals, how would you return the lexicographically smallest one?
- Follow-up: can you reduce the extra space used in your solution?
“I knew the stack-based approach going in but fumbled explaining why it works.”