11 ms·

A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

146 points by braythwayt 8y ago

karthickgururaj 8y ago
Sorry - I'm not able to understand the post. I fully understand the problem - I ask this question sometimes during interviews - with two bracket characters. Say, () and []. So a string like "([)]" is not correctly balanced. Some folks try with counters - but that very quickly gets out of hand. I try to prod them to a solution - by giving patterns that will defeat their solutions. What I'm expecting is that the person can identify that use of stack here, which (and this is my source of confusion here) - is the most natural way to solve this problem. Push when we encounter an opening bracket, pop and match when we encounter a closing bracket. The function is generic, within 10 lines in C, can easily be extended to more bracket characters. So - what is the point of this post?
- poopchute 8y ago
  Its a quick intro to computability theory. There is a progression of more and more complicated 'machines' on the way from Finite Automata towards Turing Machines. This article goes over what types of things each machine can and can't solve. Its more of a theoretical topic than a practical one (and why you'll occasionally see silly things like someone implementing a turing machine in powerpoint to show that powerpoint could compute anything)
praptak 8y ago
A silly trick question: are balanced parentheses expressions palindromes?
- noir_lord 8y ago
  No because () reversed is )(
  - pygy_ 8y ago
    Also, they are not necessarily mirror images: (()())()
    - noir_lord 8y ago
      Yep but I went for the simplest case that answers the question.
      - pygy_ 8y ago
        Indeed, my comment was more "even if you count `()` as a visual palindrome, it doesn't work".
  - agumonkey 8y ago
    should we call these symmetromes ?
skybrian 8y ago
I skimmed, but feel like he should have talked about how in an interview question, you could solve this by counting parens with a 64-bit counter. There are limits on practical input size and on stack size, so arguments about infinite languages don't directly apply. A deeper question to consider: why do we study infinite languages and then apply the results to finite problems? What do we learn this way?
- Epholys 8y ago
  Yeah, that's the first solution that popped in my mind too. I think it needs just a special case at the beginning to check if the first paren is not a closing one. EDIT: yep, after reading the comments below I see that I really should have put just a little more thought before dismissing this as too trivial to think about.
  - skybrian 8y ago
    A test case: ())(
  - FreeFull 8y ago
    What you actually need is to check if the count ever goes negative.
  - braythwayt 8y ago
    The stack solution checks that the stack is non-empty before popping. The counter solution simply needs to check that the counter is non-zero before decrementing. All cases then work perfectly.
- braythwayt 8y ago
  Author here. That solution has been discussed elsewhere in my blog. If you think of the family of problems involving nested things, or tree-like things, or recognizing, or parsing, the case where we only have one kind of parentheses and nothing else is what we might call the "degenerate case." And like many degenerate cases, there is an optimization: Instead of pushing the exact same parenthesis onto the stack over and over again, we count them. Alas, this does not grow. If we want to modify our code to handle multiple types of parentheses, or parse expressions that include parentheses into trees, and so forth, we must return to the stack. So... My general thinking is that it is useful to know that for the degenerate case, we can replace a stack with a counter, but should I ever find myself writing a parser or what-not, if I used an optimization like this, I'd probably document that it's an optimization the degenerate case where we only ever put one thing on the stack. One wild way to do that is to leave the code as-is, but hack the stack itself. So you still call .push() and .pop() and so forth, but behind the scenes, the "stack" object just counts pushes and pops.
pflats 8y ago
> Asking someone who hasn’t been recently exposed to computing theory to write a balanced parentheses recognizer is asking them to reinvent the basic research of people like Kleene and von Dyck, extemporaneously. And then write code under the interviewer’s watching eye. That is unlikely to show these candidates in their best light, and the results become very uneven. > 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. > In most cases, that makes for a bad interview question. This only makes it a bad interview question if the goal of the question is to only hire the candidates that can code the solution. Otherwise, it can be a very good interview question. How do they go about "reinvent[ing] the basic research of people like Kleene and von Dyck, extemporaneously"? What questions do they ask? What ideas do they come up with? What resources do they say they would consult? Under pressure, how do they behave? If they make a mistake, are they coachable? Do they lash out or double-down on mistakes? If they mention using a language's regex, do they understand the performance tradeoffs of various different features? There is a lot to see by asking the question beyond just "whether or not candidate X can code a solution".
- pflats 8y ago
  Beyond that, I have taught theory of computation in the past, and I think the rest of the article is a solid writeup. The DPA section might need another pass; that felt the most uneven. Things that jumped out at me: - If the audience if programmers unfamiliar with automata theory, I am not sure how many would know what a Turing machine, von Neumann machine, or even a program counter is. - Clarifying what is meant by "internal" and "external" state.
  - braythwayt 8y ago
    Thank you, that's excellent feedback.
  - tropo 8y ago
    There is no program counter. Computers don't normally need to count programs. ("let's see, I have calc.exe, that's one, and notepad.exe makes two...") There is an instruction pointer. Note that it doesn't count. It frequently is incremented, but it can jump forward and even backward. It points at an instruction.
agumonkey 8y ago
after that you're ready to read about https://en.wikipedia.org/wiki/Catalan_number https://en.wikipedia.org/wiki/Catalan_number
deathanatos 8y ago
> 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. > In most cases, that makes for a bad interview question. Well, I'm going to have to disagree there. Asking the question and expecting full knowledge of the theoretics behind it, yes. But real-world "practical" 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. > 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? Someone, in a decade of SWE experience, has never needed to implement a parser? 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'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. The point of balanced-parens as an interview question is not to get you to recreate the entire history and hierarchy of languages. It'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. (I also dislike asking the single-variant form of this question, as you can solve it w/ a simple counter. If you involve a second type of matched character, e.g., {}s, then it should require a PDA.) Are other engineering disciplines so readily accepting of folks w/o training in the field in which they're applying a job to? If not this, then what? "They might not have run into this!" is why we (should…) ask more than one question in an interview. But I feel like this refrain gets used to justify never asking any question which might reveal that half the candidates that apply for "Senior Software Engineer" positions cannot express proficiency in any programming language…
- braythwayt 8y ago
  Where I work, we track statistics on our interview questions. We are retiring this one because we believe that the results are strongly skewed by whether the candidate has had exposure to the theory behind it. We only use this for people at the beginning of their career, mind you. We have completely different expectations of someone with ten years of experience than we do of someone applying for a CAP (aka "work-term") or SDE I (aka "entry-level") position. It's not that good people can't work it out from first principles, but it's clearly a lot more work for those who have to figure it out from first principles than for those who know immediately that a stack is involved and apply their focus to the loop and the stack and handling follow-up questions. The ideal question or problem from our perspective is is one that is equally challenging for everyone, that way when we're having a candidate review, we won't need a lot of, "...But then again, the candidate clearly knew nothing about parsing, so they actually did quite well, considering."
kjeetgill 8y ago
This is amazingly well written. You covered a good deal of any introduction to computational theory course in a straightforward, well motivated matter. This is definitely something I'll be passing around to some of my bootcamp friends who are curious taste some of the theory they don't get exposure to. 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.
- braythwayt 8y ago
  > 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. That is most eloquently put, thank you! There's a reason that "Food Scientist" and "Chef" are related disciplines, but not the same job.
  - kjeetgill 8y ago
    You probably know, but I should have added that the first line was a quote from Carl Sagan.
- braythwayt 8y ago
  I took your feedback seriously, tell me what you think: https://github.com/raganwald/raganwald.github.com/commit/bec3a460c0fcd8afa78502c8af79b3e19d1c6e6f https://github.com/raganwald/raganwald.github.com/commit/bec...
kerkeslager 8y ago
This is a very well-written essay which explains its computing concepts effectively and thoroughly. I upvoted. However, the bit at the end with the balanced parentheses matchers being a bad interview question seems to be missing the forest for the trees. A simple solution to this problem which has nothing to do with any of the computational theory discussed: def is_balanced_parens(s): nesting_depth = 0 contains_nesting = False for c in s: if c == '(': nesting_depth += 1 contains_nesting = True elif c == ')': nesting_depth -= 1 else: return False if nesting_depth < 0: return False return contains_nesting and nesting_depth == 0 This isn't that hard of a problem, and if an interview candidate couldn't come up with a basic solution like this, I'd very much like to know that.
- braythwayt 8y ago
  As I mentioned elsewhere, I do not find it a hard problem, and neither do most programmers that I know. BUT. Most of the people in my "tribe" had some formal education in computer science. Our experience when hiring people is that there are programmers with a lot of raw talent and potential who will need a full slot (about 45 minutes of actual problem-solving time) to come up with something like the the code you suggest. There will be no time to discuss their solution, ask them how to handle multiple types of parentheses, &c. What most of those "They seem really smart, but struggled to balance parentheses" candidates seem to have in common is coming to programming without the formal education, e.g. through a "hacker school." Whereas, the folks coming to us directly out of a university with a traditional CS curriculum grasp the basic idea right away, and we usually get past the first question and on to a follow-up in the same 45 minutes. We already know from their resumé that some of the folks are coming from Waterloo or wherever, so it adds no useful information to us for them to do a lot better than the people with less formal backgrounds. For this reason, we now only ask this question of people doing work terms from universities with a formal CS curriculum. When people are coming to us via another path, we now give them another question entirely, and we will be retiring this one outright in the near future.
  - user5994461 8y ago

146 points by braythwayt 8y ago

Sorry - I'm not able to understand the post. I fully understand the problem - I ask this question sometimes during interviews - with two bracket characters. Say, () and []. So a string like "([)]" is not correctly balanced. Some folks try with counters - but that very quickly gets out of hand. I try to prod them to a solution - by giving patterns that will defeat their solutions. What I'm expecting is that the person can identify that use of stack here, which (and this is my source of confusion here) - is the most natural way to solve this problem. Push when we encounter an opening bracket, pop and match when we encounter a closing bracket. The function is generic, within 10 lines in C, can easily be extended to more bracket characters. So - what is the point of this post?

poopchute 8y ago
Its a quick intro to computability theory. There is a progression of more and more complicated 'machines' on the way from Finite Automata towards Turing Machines. This article goes over what types of things each machine can and can't solve. Its more of a theoretical topic than a practical one (and why you'll occasionally see silly things like someone implementing a turing machine in powerpoint to show that powerpoint could compute anything)

praptak 8y ago

A silly trick question: are balanced parentheses expressions palindromes?

noir_lord 8y ago
No because () reversed is )(
- pygy_ 8y ago
  Also, they are not necessarily mirror images: (()())()
  - noir_lord 8y ago
    Yep but I went for the simplest case that answers the question.
    - pygy_ 8y ago
      Indeed, my comment was more "even if you count `()` as a visual palindrome, it doesn't work".
- agumonkey 8y ago
  should we call these symmetromes ?

skybrian 8y ago

I skimmed, but feel like he should have talked about how in an interview question, you could solve this by counting parens with a 64-bit counter. There are limits on practical input size and on stack size, so arguments about infinite languages don't directly apply. A deeper question to consider: why do we study infinite languages and then apply the results to finite problems? What do we learn this way?

Epholys 8y ago
Yeah, that's the first solution that popped in my mind too. I think it needs just a special case at the beginning to check if the first paren is not a closing one. EDIT: yep, after reading the comments below I see that I really should have put just a little more thought before dismissing this as too trivial to think about.
- skybrian 8y ago
  A test case: ())(
- FreeFull 8y ago
  What you actually need is to check if the count ever goes negative.
- braythwayt 8y ago
  The stack solution checks that the stack is non-empty before popping. The counter solution simply needs to check that the counter is non-zero before decrementing. All cases then work perfectly.
braythwayt 8y ago
Author here. That solution has been discussed elsewhere in my blog. If you think of the family of problems involving nested things, or tree-like things, or recognizing, or parsing, the case where we only have one kind of parentheses and nothing else is what we might call the "degenerate case." And like many degenerate cases, there is an optimization: Instead of pushing the exact same parenthesis onto the stack over and over again, we count them. Alas, this does not grow. If we want to modify our code to handle multiple types of parentheses, or parse expressions that include parentheses into trees, and so forth, we must return to the stack. So... My general thinking is that it is useful to know that for the degenerate case, we can replace a stack with a counter, but should I ever find myself writing a parser or what-not, if I used an optimization like this, I'd probably document that it's an optimization the degenerate case where we only ever put one thing on the stack. One wild way to do that is to leave the code as-is, but hack the stack itself. So you still call .push() and .pop() and so forth, but behind the scenes, the "stack" object just counts pushes and pops.

pflats 8y ago

> Asking someone who hasn’t been recently exposed to computing theory to write a balanced parentheses recognizer is asking them to reinvent the basic research of people like Kleene and von Dyck, extemporaneously. And then write code under the interviewer’s watching eye. That is unlikely to show these candidates in their best light, and the results become very uneven. > 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. > In most cases, that makes for a bad interview question. This only makes it a bad interview question if the goal of the question is to only hire the candidates that can code the solution. Otherwise, it can be a very good interview question. How do they go about "reinvent[ing] the basic research of people like Kleene and von Dyck, extemporaneously"? What questions do they ask? What ideas do they come up with? What resources do they say they would consult? Under pressure, how do they behave? If they make a mistake, are they coachable? Do they lash out or double-down on mistakes? If they mention using a language's regex, do they understand the performance tradeoffs of various different features? There is a lot to see by asking the question beyond just "whether or not candidate X can code a solution".

pflats 8y ago
Beyond that, I have taught theory of computation in the past, and I think the rest of the article is a solid writeup. The DPA section might need another pass; that felt the most uneven. Things that jumped out at me: - If the audience if programmers unfamiliar with automata theory, I am not sure how many would know what a Turing machine, von Neumann machine, or even a program counter is. - Clarifying what is meant by "internal" and "external" state.
- braythwayt 8y ago
  Thank you, that's excellent feedback.
- tropo 8y ago
  There is no program counter. Computers don't normally need to count programs. ("let's see, I have calc.exe, that's one, and notepad.exe makes two...") There is an instruction pointer. Note that it doesn't count. It frequently is incremented, but it can jump forward and even backward. It points at an instruction.

agumonkey 8y ago

after that you're ready to read about https://en.wikipedia.org/wiki/Catalan_number https://en.wikipedia.org/wiki/Catalan_number

deathanatos 8y ago

> 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. > In most cases, that makes for a bad interview question. Well, I'm going to have to disagree there. Asking the question and expecting full knowledge of the theoretics behind it, yes. But real-world "practical" 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. > 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? Someone, in a decade of SWE experience, has never needed to implement a parser? 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'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. The point of balanced-parens as an interview question is not to get you to recreate the entire history and hierarchy of languages. It'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. (I also dislike asking the single-variant form of this question, as you can solve it w/ a simple counter. If you involve a second type of matched character, e.g., {}s, then it should require a PDA.) Are other engineering disciplines so readily accepting of folks w/o training in the field in which they're applying a job to? If not this, then what? "They might not have run into this!" is why we (should…) ask more than one question in an interview. But I feel like this refrain gets used to justify never asking any question which might reveal that half the candidates that apply for "Senior Software Engineer" positions cannot express proficiency in any programming language…

braythwayt 8y ago
Where I work, we track statistics on our interview questions. We are retiring this one because we believe that the results are strongly skewed by whether the candidate has had exposure to the theory behind it. We only use this for people at the beginning of their career, mind you. We have completely different expectations of someone with ten years of experience than we do of someone applying for a CAP (aka "work-term") or SDE I (aka "entry-level") position. It's not that good people can't work it out from first principles, but it's clearly a lot more work for those who have to figure it out from first principles than for those who know immediately that a stack is involved and apply their focus to the loop and the stack and handling follow-up questions. The ideal question or problem from our perspective is is one that is equally challenging for everyone, that way when we're having a candidate review, we won't need a lot of, "...But then again, the candidate clearly knew nothing about parsing, so they actually did quite well, considering."

kjeetgill 8y ago

This is amazingly well written. You covered a good deal of any introduction to computational theory course in a straightforward, well motivated matter. This is definitely something I'll be passing around to some of my bootcamp friends who are curious taste some of the theory they don't get exposure to. 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.

braythwayt 8y ago
> 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. That is most eloquently put, thank you! There's a reason that "Food Scientist" and "Chef" are related disciplines, but not the same job.
- kjeetgill 8y ago
  You probably know, but I should have added that the first line was a quote from Carl Sagan.
braythwayt 8y ago
I took your feedback seriously, tell me what you think: https://github.com/raganwald/raganwald.github.com/commit/bec3a460c0fcd8afa78502c8af79b3e19d1c6e6f https://github.com/raganwald/raganwald.github.com/commit/bec...

kerkeslager 8y ago

This is a very well-written essay which explains its computing concepts effectively and thoroughly. I upvoted. However, the bit at the end with the balanced parentheses matchers being a bad interview question seems to be missing the forest for the trees. A simple solution to this problem which has nothing to do with any of the computational theory discussed: def is_balanced_parens(s): nesting_depth = 0 contains_nesting = False for c in s: if c == '(': nesting_depth += 1 contains_nesting = True elif c == ')': nesting_depth -= 1 else: return False if nesting_depth < 0: return False return contains_nesting and nesting_depth == 0 This isn't that hard of a problem, and if an interview candidate couldn't come up with a basic solution like this, I'd very much like to know that.

braythwayt 8y ago
As I mentioned elsewhere, I do not find it a hard problem, and neither do most programmers that I know. BUT. Most of the people in my "tribe" had some formal education in computer science. Our experience when hiring people is that there are programmers with a lot of raw talent and potential who will need a full slot (about 45 minutes of actual problem-solving time) to come up with something like the the code you suggest. There will be no time to discuss their solution, ask them how to handle multiple types of parentheses, &c. What most of those "They seem really smart, but struggled to balance parentheses" candidates seem to have in common is coming to programming without the formal education, e.g. through a "hacker school." Whereas, the folks coming to us directly out of a university with a traditional CS curriculum grasp the basic idea right away, and we usually get past the first question and on to a follow-up in the same 45 minutes. We already know from their resumé that some of the folks are coming from Waterloo or wherever, so it adds no useful information to us for them to do a lot better than the people with less formal backgrounds. For this reason, we now only ask this question of people doing work terms from universities with a formal CS curriculum. When people are coming to us via another path, we now give them another question entirely, and we will be retiring this one outright in the near future.
- user5994461 8y ago