A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata
&gt; <i>Outside of a special-case like certain CS students, this question is likely to give very inconsistent results, and those results are going to be dominated by a candidate’s recent familiarity with the underlying problem, rather than their coding skills.</i><p>&gt; <i>In most cases, that makes for a bad interview question.</i><p>Well, I&#x27;m going to have to disagree there. Asking the question and expecting full knowledge of the theoretics behind it, yes. But real-world &quot;practical&quot; software engineering often requires writing parsers, and yes, parsers for context-free languages (whether the parser-writer realizes that or not). A simple, hand-rolled recursive descent parser would suffice for this language.<p>&gt; <i>But what if someone hasn’t seen this stuff in a decade? Or learned to program without going through a formal CS education? Is it reasonable to expect them to work out the ideas in an interview?</i><p>Someone, in a decade of SWE experience, has never needed to implement a parser?<p>Parsing, as a category of things to talk about, has stuff that someone with a theoretical background should know, but it is also so imminently practical that someone without the degree should have hit it and be able to answer it. I&#x27;m not asking that they realize this is a deterministic context free language, or that a PDA is the appropriate machine to parse such a language.<p>The point of balanced-parens as an interview question is not to get you to recreate the entire history and hierarchy of languages. It&#x27;s to get you to write a for loop that requires a moderately involved data structure (a stack) to see if you have any ability to reason and to code.<p>(I also dislike asking the single-variant form of this question, as you can solve it w&#x2F; a simple counter. If you involve a second type of matched character, e.g., {}s, then it should require a PDA.)<p>Are other engineering disciplines so readily accepting of folks w&#x2F;o training in the field in which they&#x27;re applying a job to?<p>If not this, then what? &quot;They might not have run into this!&quot; is why we (should…) ask more than one question in an interview. But I feel like this refrain gets used to justify never asking <i>any</i> question which might reveal that half the candidates that apply for &quot;Senior Software Engineer&quot; positions cannot express proficiency in <i>any</i> programming language…