How do you validate a parentheses string efficiently?
Reported in DoorDash interview loops. Stack-based DSA question that checks correctness under nested and mixed brackets.
Interview scenario
Context for DoorDash candidates:
Given a string containing ()[]{}, return true if every opening bracket is closed in the correct order.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at DoorDash: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Use a stack and push opening brackets as you scan left to right. For every closing bracket, check whether the stack top has the matching opening symbol; if not, the string is invalid immediately.
This gives O(n) time and O(n) space in the worst case. Mention edge handling clearly: odd length can be rejected early, and at the end the stack must be empty for the sequence to be valid.
pairs = {")":"(", "]":"[", "}":"{"}
for ch in s:
if ch in "([{": push(ch)
else if stack empty or top != pairs[ch]: return false
return stack empty
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.