5 ms·

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 pa

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
  Matching parenthesis is a puzzle question. Either the candidate knows to use a stack, or he's gonna spend one hour to figure it out.
  - deathanatos 8y ago
    I disagree that it's a puzzle. A reasonable person could look at it, and go, okay, so a parenthesized string is made up of some sequence of ( <more balanced parens> ) possibly repeated, to get things like "()()()". i.e., do that check in a loop. That is, for whatever position you're at, check that the first character is "(". Check that at position+1 there is a balanced parentheses string. Check that at position+1+len(the balanced paren string) there is a ")". Consume as many of those as you can in your loop; return the consumed data as the "balanced string". Now, this function has to return the string (since our use of it above needs the length to know where the inner string ends). It stops after it can't consume anything further. The whole string is balanced if we consumed everything. That's it. The stack is implicit here. Yeah, you have to know recursion, but that's the thing about interview questions: at some point you have to know something. I asked elsewhere, and it hasn't been answered in this thread: if this is a bad question, what would make it a good one? I would love to see what the author's idea of a good question is. For the real-world applicability of this: I deal primarily w/ HTTP APIs. Sometimes, that requires me to make use of certain HTTP headers, and a great deal of web "frameworks" out there do not parse HTTP headers; they just give you back the raw key-value map as strings or somesuch. Several of HTTP's headers are context-free. (They require at least a stack to parse.)
    - user5994461 8y ago
      It's a bad interview question IMO because it's a puzzle question. Either you know the magic trick to use a stack and you'll be done in a few minutes, or you could spend an hour to come up with a solution struggling to cover the basic edge cases. As the interviewer, all you can do is watch the developer suffers for a while, without being able to give help or shift to a different problem. That doesn't give you any indication of the ability to code or solve problems.
Twisol 8y ago
I really like this solution, because it generalizes in (what might be) a surprising way. The basic approach works by associating '(' with the number 1, ')' with the number -1, and replacing string concatenation with addition. The empty string is just 0. A balanced string of parenthesis is one where every prefix has a non-negative valuation and the whole string has a zero valuation. This valuation function is a monoid homomorphism: the sum of the values of two strings is the same as the value of their concatenation. Membership in our language is a matter of checking the valuation of some set of related strings (here, all prefixes). Converting the problem into this valuation monoid ends up being super convenient. This solution breaks down into three interwoven but logically separate pieces: identifying the related strings to check, computing their valuations, and validating the valuations. You can tweak any of these steps individually and get a different language. import operator def scan(f, initial, iterable): accumulator = initial for value in iterable: accumulator = f(accumulator, value) yield accumulator def valuation(ch): return {'(': 1, ')': -1}[ch] def is_balanced_parentheses(s): values = map(valuation, s) for value in scan(operator.add, 0, values): if value < 0: return False return (value == 0)
- braythwayt 8y ago
  > A balanced string of parenthesis is one where every prefix has a non-negative valuation and the whole string has a zero valuation. Speaking of coming up with solutions from first principles, I had a candidate come up with the following: Map the opening and closing parentheses to indices, in two arrays. Example: For the string `(())()`, the two arrays would be `[0, 1, 4]` for `(` and `[2, 3, 5]` for `)`. If the arrays of indices are not the same length, it isn't balanced. If they are the same length, go through the two arrays in pairs. The candidate didn't express it this way, but I thought "zip the arrays" in my mind, so I'll express it that way, we get `[[0, 2], [1, 3], [4, 5]]`. The candidate then said, if in each of these pairs, the index for `)` is greater than the index for `(`, the parentheses are balanced. Which is mathematically equivalent to a stack or a counter (the optimized degenerate case) or the prefix valuation. Of course it's not as efficient as other solutions, and I don't see it generalizing, but hey... It was inventive, in my mind.
munificent 8y ago
Your solution is actually an optimized implementation of a pushdown automata. nesting_depth is the stack. There is only one kind of symbol that can be pushed, so it's represented as a simple count of the number of symbols that are on the stack.
- kerkeslager 8y ago
  Okay, but I don't need to know the concept of a PDA to implement that, nor would I assume a candidate understands PDAs from reading that code.
UncleEntity 8y ago
> 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. def is_balanced_parens(s): return s.count('(') == s.count(')') Think I'd fail the interview test...
- deleted 8y ago
  [deleted]
- Anon84 8y ago
  So you claim that ")(" is balanced?
bboreham 8y ago
Fails on the first example in TFA.
- deathanatos 8y ago
  I think your parent's solution simply considers the empty string not part of the language. The article thinks it is. It's a trivial adjustment to the solution to include it.
  - bboreham 8y ago
    Consider the context: parent is talking about how easy the problem is to solve in an interview. Coding interviews serve to check _how_ a candidate goes about solving a problem - if they submit without checking the solution meets the spec, or choose to solve a different problem without mentioning it up front, then this tells me plenty about their working style.
antidesitter 8y ago
Two purely-functional versions (written in Haskell): balanced1 input = let partialsums = scanl (+) 0 $ map (\x -> if x == '(' then 1 else -1) input in all (>= 0) partialsums && last partialsums == 0 balanced2 = balanced' 0 where balanced' count [] = count == 0 balanced' count ('(':rest) = balanced' (count + 1) rest balanced' count (')':rest) = balanced' (count - 1) rest && count > 0 A more general version with multiple types of brackets: balanced = balanced' [] where balanced' stack [] = null stack balanced' stack ('(':rest) = balanced' ('(':stack) rest balanced' stack ('[':rest) = balanced' ('[':stack) rest balanced' stack ('{':rest) = balanced' ('{':stack) rest balanced' stack (')':rest) = head stack == '(' && balanced' (tail stack) rest balanced' stack (']':rest) = head stack == '[' && balanced' (tail stack) rest balanced' stack ('}':rest) = head stack == '{' && balanced' (tail stack) rest balanced' stack (_:rest) = balanced' stack rest
- Tarean 8y ago
  My naive version would be import Control.Monad (foldM) checkBalanced :: [Char] -> Bool checkBalanced = isStackEmpty . foldM step mempty where step (x:xs) c | x == c = Just xs step ls c | Just r <- inverse c = Just (r : ls) step _ _ = Nothing inverse = flip lookup [( '(', ')' )] isStackEmpty stack = stack == Just []
jejones3141 8y ago
I think that '()))((' will be judged balanced by the above code.
- db48x 8y ago
  No, he checks each time through the loop to see if the counter ever goes below zero; if it does, then the string is unbalanced.
- kerkeslager 8y ago
  Why don't you write a unit test and see? :)
somacert 8y ago
Scary, that is almost the exact code I came up with. The funny thing is balanced parens can be recognized with with a state machine it is just ugly. state_data = { '0p':{ '(':'1p', ')':'fail', 'END':'pass', 'OTHER':'0p', }, '1p':{ '(':'2p', ')':'1p', 'END': 'fail', 'OTHER':'1p', }, '2p':{ '(':'3p', ')':'2p', 'END': 'fail', 'OTHER':'2p', } ... } Just make sure the state machine has as many states as you need paren levels. I admit the moment that the math vernacular appears my brain seems to shut down, however after reading the proof that balanced parens cannot be described several times. It seems to depend on a couple things. 1 The string is allowed to be infinite the state machine not. 2 "But state(B, start, p) is the same state as state(B, start, q)!" why? the strings are defined to be different I see no reason they would be in the same state. EDIT added analysis of article proof.
- deleted 8y ago
  [deleted]
- braythwayt 8y ago
  The proof rest on feeding a nested parenthesis string to a hypothetical DFA called “B.” Since these are nested parentheses, a string that is recognized will be of the form `pp’`, where `p` is a string of open parentheses, and `p’` is a string of closed parentheses the same length as `p`. e.g. (((((((((()))))))))) In that example, `p` is length ten. After reading `p`, the recognizer must be in one of its states. It can’t have halted, and it can’t have recognized. Let’s say that the recognizer has `n` states. Consider the strings (), (()), ((())), ... After (, the machine is in some state. Let’s give that a number, 0. If we start all over and give it ((, it must be in another state, state 1, or we must accept that two different strings end up in the same state. Then we can start all over and give it (((, and we must end up in state 2. And so we can go, adding a parenthesis each time, and the machine must end up in a different state after reading a different number of opening parentheses. Eventually we reach state n-1, after starting from scratch and giving it n opening parentheses. We must now know that all the strings from 0 to n-1 in length lead to n different states in an n-state DFA. So what happens when we give it n+1 opening parentheses? It must end in one of its states, but we already know that the strings with one through n opening parentheses have ended up in each of its n states. So the string with n+1 opening parentheses must end up in the same states as one of the shorter strings with opening parentheses, we just don’t know which. Back to the proof. The shorter of the two strings is p from the proof. The longer is q.
arthurcolle 8y ago
https://github.com/stochastic-thread/balanced_parentheses/blob/master/Balanced%20Parentheses.ipynb https://github.com/stochastic-thread/balanced_parentheses/bl... What do you think of this implementation I just wrote? It is generalized to work with parentheses, brackets and braces, and to handle the different types of braces I just used different scores that offset each other depending on the direction of the symbol. Couldn't really think of a better way to handle this other than using numbers that don't add up to one another (in a momentary fugue state, I used 1,-1,2,-2,3,-3 as the score values but that obviously doesn't work as [}) would be false flagged as matched. Doesn't seem elegant to use random floats to accomplish this. It's a pretty trivial problem, but I think coming up with a clever solution to the generalization is a little more interesting. P.S. your site is down
- kerkeslager 8y ago
  > https://github.com/stochastic-thread/balanced_parentheses/bl.. https://github.com/stochastic-thread/balanced_parentheses/bl.... > What do you think of this implementation I just wrote? It is generalized to work with parentheses, brackets and braces, and to handle the different types of braces I just used different scores that offset each other depending on the direction of the symbol. Couldn't really think of a better way to handle this other than using numbers that don't add up to one another (in a momentary fugue state, I used 1,-1,2,-2,3,-3 as the score values but that obviously doesn't work as [}) would be false flagged as matched. Doesn't seem elegant to use random floats to accomplish this. Two critiques, one minor, and one major: Minor critique: is_balanced is a pure function. It doesn't need to be wrapped in a class, and an object doesn't need to be instantiated to call it. This adds complexity and in general is a bad habit. Languages like Java require classes, but that's Java exposing details of its underlying implementation, not a pattern to be imitated. Major critique: try your function with the string "((((((]]]]]". In general, your approach doesn't work, because for whatever numbers you use (such as x=1 and y=1.2) the scores will "collide" at when there are lcm(x,y) where lcm is the least common multiple function. There's an even subtler bug for the string "{)(}". > It's a pretty trivial problem, but I think coming up with a clever solution to the generalization is a little more interesting. Yes, once you're generalizing I think the PDA becomes basically the simplest solution. > P.S. your site is down Thanks! It actually wasn't down, my HN profile was just linking to an old URL. I fixed it. :)

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
Matching parenthesis is a puzzle question. Either the candidate knows to use a stack, or he's gonna spend one hour to figure it out.
- deathanatos 8y ago
  I disagree that it's a puzzle. A reasonable person could look at it, and go, okay, so a parenthesized string is made up of some sequence of ( <more balanced parens> ) possibly repeated, to get things like "()()()". i.e., do that check in a loop. That is, for whatever position you're at, check that the first character is "(". Check that at position+1 there is a balanced parentheses string. Check that at position+1+len(the balanced paren string) there is a ")". Consume as many of those as you can in your loop; return the consumed data as the "balanced string". Now, this function has to return the string (since our use of it above needs the length to know where the inner string ends). It stops after it can't consume anything further. The whole string is balanced if we consumed everything. That's it. The stack is implicit here. Yeah, you have to know recursion, but that's the thing about interview questions: at some point you have to know something. I asked elsewhere, and it hasn't been answered in this thread: if this is a bad question, what would make it a good one? I would love to see what the author's idea of a good question is. For the real-world applicability of this: I deal primarily w/ HTTP APIs. Sometimes, that requires me to make use of certain HTTP headers, and a great deal of web "frameworks" out there do not parse HTTP headers; they just give you back the raw key-value map as strings or somesuch. Several of HTTP's headers are context-free. (They require at least a stack to parse.)
  - user5994461 8y ago
    It's a bad interview question IMO because it's a puzzle question. Either you know the magic trick to use a stack and you'll be done in a few minutes, or you could spend an hour to come up with a solution struggling to cover the basic edge cases. As the interviewer, all you can do is watch the developer suffers for a while, without being able to give help or shift to a different problem. That doesn't give you any indication of the ability to code or solve problems.

Twisol 8y ago

I really like this solution, because it generalizes in (what might be) a surprising way. The basic approach works by associating '(' with the number 1, ')' with the number -1, and replacing string concatenation with addition. The empty string is just 0. A balanced string of parenthesis is one where every prefix has a non-negative valuation and the whole string has a zero valuation. This valuation function is a monoid homomorphism: the sum of the values of two strings is the same as the value of their concatenation. Membership in our language is a matter of checking the valuation of some set of related strings (here, all prefixes). Converting the problem into this valuation monoid ends up being super convenient. This solution breaks down into three interwoven but logically separate pieces: identifying the related strings to check, computing their valuations, and validating the valuations. You can tweak any of these steps individually and get a different language. import operator def scan(f, initial, iterable): accumulator = initial for value in iterable: accumulator = f(accumulator, value) yield accumulator def valuation(ch): return {'(': 1, ')': -1}[ch] def is_balanced_parentheses(s): values = map(valuation, s) for value in scan(operator.add, 0, values): if value < 0: return False return (value == 0)

braythwayt 8y ago
> A balanced string of parenthesis is one where every prefix has a non-negative valuation and the whole string has a zero valuation. Speaking of coming up with solutions from first principles, I had a candidate come up with the following: Map the opening and closing parentheses to indices, in two arrays. Example: For the string `(())()`, the two arrays would be `[0, 1, 4]` for `(` and `[2, 3, 5]` for `)`. If the arrays of indices are not the same length, it isn't balanced. If they are the same length, go through the two arrays in pairs. The candidate didn't express it this way, but I thought "zip the arrays" in my mind, so I'll express it that way, we get `[[0, 2], [1, 3], [4, 5]]`. The candidate then said, if in each of these pairs, the index for `)` is greater than the index for `(`, the parentheses are balanced. Which is mathematically equivalent to a stack or a counter (the optimized degenerate case) or the prefix valuation. Of course it's not as efficient as other solutions, and I don't see it generalizing, but hey... It was inventive, in my mind.

munificent 8y ago

Your solution is actually an optimized implementation of a pushdown automata. nesting_depth is the stack. There is only one kind of symbol that can be pushed, so it's represented as a simple count of the number of symbols that are on the stack.

kerkeslager 8y ago
Okay, but I don't need to know the concept of a PDA to implement that, nor would I assume a candidate understands PDAs from reading that code.

UncleEntity 8y ago

> 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. def is_balanced_parens(s): return s.count('(') == s.count(')') Think I'd fail the interview test...

deleted 8y ago
[deleted]
Anon84 8y ago
So you claim that ")(" is balanced?

bboreham 8y ago

Fails on the first example in TFA.

deathanatos 8y ago
I think your parent's solution simply considers the empty string not part of the language. The article thinks it is. It's a trivial adjustment to the solution to include it.
- bboreham 8y ago
  Consider the context: parent is talking about how easy the problem is to solve in an interview. Coding interviews serve to check _how_ a candidate goes about solving a problem - if they submit without checking the solution meets the spec, or choose to solve a different problem without mentioning it up front, then this tells me plenty about their working style.

antidesitter 8y ago

Two purely-functional versions (written in Haskell): balanced1 input = let partialsums = scanl (+) 0 $ map (\x -> if x == '(' then 1 else -1) input in all (>= 0) partialsums && last partialsums == 0 balanced2 = balanced' 0 where balanced' count [] = count == 0 balanced' count ('(':rest) = balanced' (count + 1) rest balanced' count (')':rest) = balanced' (count - 1) rest && count > 0 A more general version with multiple types of brackets: balanced = balanced' [] where balanced' stack [] = null stack balanced' stack ('(':rest) = balanced' ('(':stack) rest balanced' stack ('[':rest) = balanced' ('[':stack) rest balanced' stack ('{':rest) = balanced' ('{':stack) rest balanced' stack (')':rest) = head stack == '(' && balanced' (tail stack) rest balanced' stack (']':rest) = head stack == '[' && balanced' (tail stack) rest balanced' stack ('}':rest) = head stack == '{' && balanced' (tail stack) rest balanced' stack (_:rest) = balanced' stack rest

Tarean 8y ago
My naive version would be import Control.Monad (foldM) checkBalanced :: [Char] -> Bool checkBalanced = isStackEmpty . foldM step mempty where step (x:xs) c | x == c = Just xs step ls c | Just r <- inverse c = Just (r : ls) step _ _ = Nothing inverse = flip lookup [( '(', ')' )] isStackEmpty stack = stack == Just []

jejones3141 8y ago

I think that '()))((' will be judged balanced by the above code.

db48x 8y ago
No, he checks each time through the loop to see if the counter ever goes below zero; if it does, then the string is unbalanced.
kerkeslager 8y ago
Why don't you write a unit test and see? :)

somacert 8y ago

Scary, that is almost the exact code I came up with. The funny thing is balanced parens can be recognized with with a state machine it is just ugly. state_data = { '0p':{ '(':'1p', ')':'fail', 'END':'pass', 'OTHER':'0p', }, '1p':{ '(':'2p', ')':'1p', 'END': 'fail', 'OTHER':'1p', }, '2p':{ '(':'3p', ')':'2p', 'END': 'fail', 'OTHER':'2p', } ... } Just make sure the state machine has as many states as you need paren levels. I admit the moment that the math vernacular appears my brain seems to shut down, however after reading the proof that balanced parens cannot be described several times. It seems to depend on a couple things. 1 The string is allowed to be infinite the state machine not. 2 "But state(B, start, p) is the same state as state(B, start, q)!" why? the strings are defined to be different I see no reason they would be in the same state. EDIT added analysis of article proof.

deleted 8y ago
[deleted]
braythwayt 8y ago
The proof rest on feeding a nested parenthesis string to a hypothetical DFA called “B.” Since these are nested parentheses, a string that is recognized will be of the form `pp’`, where `p` is a string of open parentheses, and `p’` is a string of closed parentheses the same length as `p`. e.g. (((((((((()))))))))) In that example, `p` is length ten. After reading `p`, the recognizer must be in one of its states. It can’t have halted, and it can’t have recognized. Let’s say that the recognizer has `n` states. Consider the strings (), (()), ((())), ... After (, the machine is in some state. Let’s give that a number, 0. If we start all over and give it ((, it must be in another state, state 1, or we must accept that two different strings end up in the same state. Then we can start all over and give it (((, and we must end up in state 2. And so we can go, adding a parenthesis each time, and the machine must end up in a different state after reading a different number of opening parentheses. Eventually we reach state n-1, after starting from scratch and giving it n opening parentheses. We must now know that all the strings from 0 to n-1 in length lead to n different states in an n-state DFA. So what happens when we give it n+1 opening parentheses? It must end in one of its states, but we already know that the strings with one through n opening parentheses have ended up in each of its n states. So the string with n+1 opening parentheses must end up in the same states as one of the shorter strings with opening parentheses, we just don’t know which. Back to the proof. The shorter of the two strings is p from the proof. The longer is q.

arthurcolle 8y ago

https://github.com/stochastic-thread/balanced_parentheses/blob/master/Balanced%20Parentheses.ipynb https://github.com/stochastic-thread/balanced_parentheses/bl... What do you think of this implementation I just wrote? It is generalized to work with parentheses, brackets and braces, and to handle the different types of braces I just used different scores that offset each other depending on the direction of the symbol. Couldn't really think of a better way to handle this other than using numbers that don't add up to one another (in a momentary fugue state, I used 1,-1,2,-2,3,-3 as the score values but that obviously doesn't work as [}) would be false flagged as matched. Doesn't seem elegant to use random floats to accomplish this. It's a pretty trivial problem, but I think coming up with a clever solution to the generalization is a little more interesting. P.S. your site is down

kerkeslager 8y ago
> https://github.com/stochastic-thread/balanced_parentheses/bl.. https://github.com/stochastic-thread/balanced_parentheses/bl.... > What do you think of this implementation I just wrote? It is generalized to work with parentheses, brackets and braces, and to handle the different types of braces I just used different scores that offset each other depending on the direction of the symbol. Couldn't really think of a better way to handle this other than using numbers that don't add up to one another (in a momentary fugue state, I used 1,-1,2,-2,3,-3 as the score values but that obviously doesn't work as [}) would be false flagged as matched. Doesn't seem elegant to use random floats to accomplish this. Two critiques, one minor, and one major: Minor critique: is_balanced is a pure function. It doesn't need to be wrapped in a class, and an object doesn't need to be instantiated to call it. This adds complexity and in general is a bad habit. Languages like Java require classes, but that's Java exposing details of its underlying implementation, not a pattern to be imitated. Major critique: try your function with the string "((((((]]]]]". In general, your approach doesn't work, because for whatever numbers you use (such as x=1 and y=1.2) the scores will "collide" at when there are lcm(x,y) where lcm is the least common multiple function. There's an even subtler bug for the string "{)(}". > It's a pretty trivial problem, but I think coming up with a clever solution to the generalization is a little more interesting. Yes, once you're generalizing I think the PDA becomes basically the simplest solution. > P.S. your site is down Thanks! It actually wasn't down, my HN profile was just linking to an old URL. I fixed it. :)