10 Mar
2025
10 Mar
'25
8:49 p.m.
Perhaps the interviewer was looking for something dumb like the following
and not a full RD parser?
int count = 0;
while (*cp) {
char c = *cp++;
count += c == '(' ? 1 : c == ')' ? -1 : 0;
if (count < 0) return -1; // FAIL: one too many )
}
if (count > 0) return -1; // FAIL: too many (
return 0; // SUCCESS
Though this will fall apart if you also want to also balance braces &/or
brackets and must catch invalid cases like "(..[..)..]"!
On Mar 10, 2025, at 8:19 AM, John Cowan
<cowan(a)ccil.org> wrote:
I was working at the whiteboard during a job interview once. I had been asked to write a
function to report if its input had balanced parentheses. No problem: I wrote an RD
parser in Python (which I prefer for whiteboarding) to detect balance and return True if
the parse was successful and False if EOF was reached.
I was starting to write some tests when the interviewer interrupted me.
"What is that?"
"It's a recursive descent parser. It detects if the input is
well-formed."
Blank look.
I started to walk him through the code.
He interrupted me. "Excuse me, I'll be back in a few minutes."
Long wait, maybe 15-20 minutes. Someone else comes in. "Thank you, the recruiter
will get back to you." That's the last I hear from them.