If it is a compiler gig, I don't think we can get much mileage out out of the balance parentheses problem. Language implementors either just deal with paren balancing as part of the parser or, if they want better error recovery, write a simple paren balancer as a separate pass between lexing and real parsing. In the latter case, implementors will just go with the most simplest solution available and won't bother with a PDA (since it really isn't necessary).
If you really want to test a language implementor, ask them how they would implement a parser for a language that allows < and > to be used as both comparison operators and generic type parentheses.
https://github.com/raganwald/raganwald.github.com/commit/bec...
> An obvious question is, _Do you need to know the difference between a regular language and a context-free language if all you want to do is write some code that recognizes balanced parentheses?_
You have a real talent for motivating the conversation around theory. I like the subject matter so I rarely need more than: hey, I think this is cool. But when I share it with others it says all the things I can't!
> ...
> But if I ask you to make an apple pie I'm not going to ding you for starting with apples, flour, sugar, and butter.
That is most eloquently put, thank you! There's a reason that "Food Scientist" and "Chef" are related disciplines, but not the same job.
Ironically, what I thought what made this so effective and interesting was that it dug into the theory of a really really easy programming problem. This is a reasonable homework assignment for any first year student. Maybe not month one, but year one for sure.
> That suggests the question: Is balanced parentheses a good interview question?
If you just needed a solution to solve the problem and maybe check a few edge cases; yeah, it's great because it's simple. If you're using it to broach a conversation on automata, regular expressions, and context free languages well yeah delving into that is bad unless you're writing real parsers/compilers at this gig.
I was really put off my the musing over whether it's a good interview question. For such a beautifully written piece it seems to say: if you don't expect candidates to know as much as this don't ask it at all.
If you want to make an apple pie from scratch, you must first create the universe.
...
But if I ask you to make an apple pie I'm not going to ding you for starting with apples, flour, sugar, and butter.