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.
> 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.
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.
I like it! I think it cuts closer to what I think people generally should inow at the very least.
> 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!
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.
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)
> 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.
It actually generalizes pretty well... You just need an array for each type of parenthesis, so if your language is "(){}" you would need 4 vectors and play the same "zipped" game two by two. You can also generalize the counting solution (where "(" = +1 and ")" = -1) to this scenario using vectors ("(" = [1,0], "{" = [0, 1], ")" = [-1, 0], "}" = [0, -1]), etc. If you are only interested in pairs of tokens, there's probably a bitstring solution too...
Yes, you are both quite correct (I was thinking along the lines mentioned by Twisol).
I was looking at the basic approach as a walk in 1D. In the students representation, this means that each tuple is ordered, implying a move forward (you start with a "(" and eventually end at a ")". As a walk, this means that you return to the origin without ever becoming negative.
In my rush, I generalized too quickly for the case of the two brackets as just a similar random walk in 2D. This of course doesn't work in the example you mentioned. If () corresponds to the xx dimension and {} to the yy axis:
- With "({)}" you do return to the origin [[1, 0], [1,1], [0, 1], [0, 0]] but not in a valid path.
- You basically need one extra rule. At each step, you can move forward in any direction (open a new type of bracket), but you can only move back in the direction you just came from (close the previous one).
This of course is just a weird way of representing a stack, because you still need to keep track of the entire history anyway (which you could just store as the brackets themselves.
To paraphrase one of my idols, "More (dimensions) is different"...
No, you're right -- I had the same thought as 'Anon84 before I realized I was thinking of a different kind of language.
The language 'Anon84 is thinking of is useful for thinking about concurrent systems, where each kind of bracket is associated with a particular agent. What's important is not that the brackets are mutually well-nested, but only that each kind of bracket is independently well-nested. This independence property means that "({)}" is a well-formed string, since ignoring everything but round parentheses gives "()", and ignoring everything but curly braces gives "{}".
The Dyck language family is different. The entanglement between types of brackets means that you can't do a simple tensor like we'd like to.
If we're allowed to use more memory than a simple stack, this is my favorite super-cheaty solution. It abuses ruby's builtin string manipulation to recursively delete inner matched pairs (all that is really needed is a "slide remaining string left 2 chars" function). Since this only needs to match two-char long inner pairs, it trivially extends to multiple matched bracket types.
BRACKET_RE = /\(\)/
#BRACKET_RE = /\(\)|\[\]|\{\}/
def balanced?(str)
case str
when '' then return true
when BRACKET_RE then balanced? str.split(BRACKET_RE).join('')
else return false
end
end
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.
There are a bunch of things going on in your post:
1. If you're willing to train programmers, then all you're really looking for is an IQ test to see if they're smart enough to learn how to program. So in that case, you don't really need to ask programming questions at all. But if you're not willing to train programmers, then it makes sense to filter out programmers who aren't familiar with basic problem solving techniques, regardless of background. If they don't know how to do the job, that problem doesn't simply go away because you identify the cause (that they don't have a formal CS background). If a candidate is coming out of a "hacker school", I'd be MORE likely to ask this sort of question because I want to figure out if their lack of formal education is going to be a problem.
2. Someone with a formal CS background obviously has an advantage with this sort of question because they've seen this problem before, or a problem like it. But there's a lot of value in seeing how a candidate approaches a problem they've never seen before.
3. I'll say again that the response I posted doesn't require any formal CS education, as proven by the fact that I came up with that algorithm in an interview for an internship, before I had any formal CS education beyond for loops and if statements.
> 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."
How much of this is due to them starting coding before thinking about the problem?
I'd not be surprised at all if these people would, if given several strings of parenthesis on a whiteboard and simply asked if those specific strings were balanced, have no trouble answering. I'd also not be surprised if then asked to explain how they determined this, they could do so. Then, if asked to write a program to use the same method, they could probably readily do it.
A lot of problems that are not hard if you think about them and then start coding are a lot harder if you try to simultaneously work out how to solve it and code that.
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.)
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.
> It's a bad interview question IMO because it's a puzzle question.
You asserted this in your first message. The point of my reply is to show that it's not a "puzzle", and that a reasonable line of thinking and reasoning can guide you through the problem to an answer. The naïve answer one might get here is fairly "undisciplined", in that there's no rigor in language theory, no deep discussion, but the question is still answerable.
> the magic trick to use a stack
My suggested line of reasoning does not use a stack, beyond function calling. If using the actual stack is a "magic trick", again, I think we have removed so much material from consideration as to not be able to ask anything of use.
Again, if we simply dismiss any line of reasoning that a candidate might not see as a "puzzle", then every question is a puzzle, and nothing can be asked in an interview. Simply repeating your thesis that it's a puzzle does not advance this discussion: do you not think the line of reasoning I laid out is reasonably obtainable in an interview? And if not (since I think it's a fairly minimal one), then what types/sorts of questions should an interview ask, since it would seem like I'm left with only things that are dead obvious (b/c if it wasn't, it's now a magic trick puzzle), and that leaves me with nothing to screen candidates with.
As an interviewer, I want to see you struggle with something you might not fully understand, and I want to know your reasoning and thinking as you go along with it. The real job is not going to come with a manual, after all.
Incrementing on parenthesis and decrementing on closing parenthesis is trivial. You can surely agree that it's more of an ahah moment to get there, than a long reasoning that may or may not have lead to it.
What do you do if the candidate cannot come up with the solution in 10 minutes? I've been there and find it embarrassing. It doesn't indicate aptitude or lack of aptitude.
I find that system design, performance optimization or sometimes code review have the great advantage of being progressive. The candidate can go in multiple directions. The interviewer has the opportunity to lead to find strengths and match with experiences on the resume, while it's also possible to assist or to pull away from any particular aspect.
For coding questions, either stay on simple problems with straightforward solutions, could be as stupid as printing numbers from one to ten, to test the ability to actually write code. Or a progressive exercise that must have both trivial solutions and optimized solutions and then can be integrated into a bigger function.
It's easier with a stack and it avoids common mistakes from other algorithms. Also easier to generalize to follow up problems like multiple characters.
Push on opening parenthesis. Pop on closing parenthesis. Trivial.
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.
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 []
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.
> 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. :)
Thanks! Wow my implementation sucks! What do you mean by PDA?
The whole Solution().runFunc() thing I just kind of picked up from LeetCode-esque constructions, but I definitely see your point on it being a pure function.
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.
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.
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.
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.
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?
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.
Yes, agreed. But it does show another pitfall when it comes to using a degenerate case as an interview question: someone who doesn't know anything about parsing or stacks might solve it easily if they have a different mindset. On the other hand, half-remembering something from school could really mess you up.
A typical interview along these lines will get the candidate to the "single balanced parentheses" solution, then throw in multiple types of parentheses.
The whole script goes sideways if the candidates whips Perl or Ruby or whatever out, and provides a recursive regex.
I think that depends on the goals of the design. The very simple single-grouping type case can be used to prove that something isn't obviously false in isolation.
Once grouping starts to be an issue I think that different spans need to be broken out from the main section and each treated as isolated fragments to validate.
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.
> 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".
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.
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.
There's a lot of literature that states otherwise. Of the assembly languages I've studied (and within reach of me I have references to the Motorola 6809, 680x0, VAX, MIPS, Z80, 6502, and x86) it's only the x86 line that used the name `IP` (Instruction Pointer [1])---the rest all use `PC` (Program Counter). And (to be even more pedantic) that register (`IP` or `PC`) always points to the next instruction to be executed, never the current instruction being executed. And just to note, on the VAX, the `PC` register is also `R15`, so it can participate in any instruction as either a source or destination; whether that's a good idea is another matter.
[1] Technically, until you get to the 64-bit version, it's `CS:IP` (Code Segment, Instruction Pointer).
There's a lot of literature that repeats a harmful misnomer.
The register is always an instruction pointer, even if the hardware incorrectly calls it a program counter.
The processor that matters most, by far, is x86. At one point PowerPC wasn't too far behind, and PowerPC still dominates in high-end network gear. Both of these processors are correctly documented. For x86 the name is ip, eip, or rip. For PowerPC the name is usually nip, meaning "next instruction pointer". Sometimes the PowerPC documentation will use "current" instead of "next", or "address" instead of "pointer". All of these are correct.
And the processor that matters the most after the x86 is the ARM, which uses `PC`. I suppose all ARM documentation is incorrect then.
Also, in electrical engineering, the direction of electricity is taught backwards from what it really does. In all sources I've read, electricity flows from positive to ground, whereas in reality, it's the opposite. Good luck in changing that.
That's certainly an interesting approach, but in that case I would want to budget a fair bit of time, and not be attached to coding a solution at all.
And again, you want to be aware that you are going to have sharply different experiences depending upon the candidate's familiarity with the basic research.
It would be very interesting to walk through a candidate's thinking about this problem "raw," but it would be grossly unfair to ask the same question of an intern who had studied the problem in the last semester.
I have seen interview questions along the lines of "reinvent basic research," but they typically pick something obscure-ish to reduce the likelihood that the candidate has seen it before, and such things are usually more of the dreaded "whiteboard your thinking," rather than judging you based on the code produced.
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.
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)
> 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…
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."
> The ideal question or problem from our perspective is is one that is equally challenging for everyone
It seems like you could solve this by asking a question no one has ever been exposed to before, or by exposing each candidate to the theory relevant to the question yourself.
Except that the first strategy is guaranteed to fail some of the time, because there are no questions like that.
There is an interesting communication problem here.
If I could guarantee that every candidate would read my blog, I'd happily point them to an essay like this, and then in the interview we could work on something meaty, like pattern matching.
That would suit your second recommended strategy. But I wouldn't want to write an essay like this, and then favour those candidates who like to read Hacker News or follow me on Twitter. We're trying to select for talent, not for membership in a tribe :-)
So we're retiring this question, and we already have a few replacements that we use for many candidates. But I won't blog about them, in an attempt to hew closely to the first strategy you suggest.
I think you could pretty easily guarantee that every candidate will read email from you (where "you" are their point of contact with the company) prior to the interview. Why do you need to direct them to the essay from your blog?
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.
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.
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:
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.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.
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.
Efficiency, on the other hand, is not the best.
What about the string `({)}`? That is not balanced, so how would any counting or pairwise comparison work?
I was looking at the basic approach as a walk in 1D. In the students representation, this means that each tuple is ordered, implying a move forward (you start with a "(" and eventually end at a ")". As a walk, this means that you return to the origin without ever becoming negative.
In my rush, I generalized too quickly for the case of the two brackets as just a similar random walk in 2D. This of course doesn't work in the example you mentioned. If () corresponds to the xx dimension and {} to the yy axis:
- With "({)}" you do return to the origin [[1, 0], [1,1], [0, 1], [0, 0]] but not in a valid path.
- You basically need one extra rule. At each step, you can move forward in any direction (open a new type of bracket), but you can only move back in the direction you just came from (close the previous one).
This of course is just a weird way of representing a stack, because you still need to keep track of the entire history anyway (which you could just store as the brackets themselves.
To paraphrase one of my idols, "More (dimensions) is different"...
The language 'Anon84 is thinking of is useful for thinking about concurrent systems, where each kind of bracket is associated with a particular agent. What's important is not that the brackets are mutually well-nested, but only that each kind of bracket is independently well-nested. This independence property means that "({)}" is a well-formed string, since ignoring everything but round parentheses gives "()", and ignoring everything but curly braces gives "{}".
The Dyck language family is different. The entanglement between types of brackets means that you can't do a simple tensor like we'd like to.
If we're allowed to use more memory than a simple stack, this is my favorite super-cheaty solution. It abuses ruby's builtin string manipulation to recursively delete inner matched pairs (all that is really needed is a "slide remaining string left 2 chars" function). Since this only needs to match two-char long inner pairs, it trivially extends to multiple matched bracket types.
http://raganwald.com/2018/11/14/dyck-joke.html
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.
1. If you're willing to train programmers, then all you're really looking for is an IQ test to see if they're smart enough to learn how to program. So in that case, you don't really need to ask programming questions at all. But if you're not willing to train programmers, then it makes sense to filter out programmers who aren't familiar with basic problem solving techniques, regardless of background. If they don't know how to do the job, that problem doesn't simply go away because you identify the cause (that they don't have a formal CS background). If a candidate is coming out of a "hacker school", I'd be MORE likely to ask this sort of question because I want to figure out if their lack of formal education is going to be a problem.
2. Someone with a formal CS background obviously has an advantage with this sort of question because they've seen this problem before, or a problem like it. But there's a lot of value in seeing how a candidate approaches a problem they've never seen before.
3. I'll say again that the response I posted doesn't require any formal CS education, as proven by the fact that I came up with that algorithm in an interview for an internship, before I had any formal CS education beyond for loops and if statements.
How much of this is due to them starting coding before thinking about the problem?
I'd not be surprised at all if these people would, if given several strings of parenthesis on a whiteboard and simply asked if those specific strings were balanced, have no trouble answering. I'd also not be surprised if then asked to explain how they determined this, they could do so. Then, if asked to write a program to use the same method, they could probably readily do it.
A lot of problems that are not hard if you think about them and then start coding are a lot harder if you try to simultaneously work out how to solve it and code that.
A reasonable person could look at it, and go, okay, so a parenthesized string is made up of some sequence of
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.)
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.
You asserted this in your first message. The point of my reply is to show that it's not a "puzzle", and that a reasonable line of thinking and reasoning can guide you through the problem to an answer. The naïve answer one might get here is fairly "undisciplined", in that there's no rigor in language theory, no deep discussion, but the question is still answerable.
> the magic trick to use a stack
My suggested line of reasoning does not use a stack, beyond function calling. If using the actual stack is a "magic trick", again, I think we have removed so much material from consideration as to not be able to ask anything of use.
Again, if we simply dismiss any line of reasoning that a candidate might not see as a "puzzle", then every question is a puzzle, and nothing can be asked in an interview. Simply repeating your thesis that it's a puzzle does not advance this discussion: do you not think the line of reasoning I laid out is reasonably obtainable in an interview? And if not (since I think it's a fairly minimal one), then what types/sorts of questions should an interview ask, since it would seem like I'm left with only things that are dead obvious (b/c if it wasn't, it's now a magic trick puzzle), and that leaves me with nothing to screen candidates with.
As an interviewer, I want to see you struggle with something you might not fully understand, and I want to know your reasoning and thinking as you go along with it. The real job is not going to come with a manual, after all.
What do you do if the candidate cannot come up with the solution in 10 minutes? I've been there and find it embarrassing. It doesn't indicate aptitude or lack of aptitude.
I find that system design, performance optimization or sometimes code review have the great advantage of being progressive. The candidate can go in multiple directions. The interviewer has the opportunity to lead to find strengths and match with experiences on the resume, while it's also possible to assist or to pull away from any particular aspect.
For coding questions, either stay on simple problems with straightforward solutions, could be as stupid as printing numbers from one to ten, to test the ability to actually write code. Or a progressive exercise that must have both trivial solutions and optimized solutions and then can be integrated into a bigger function.
Push on opening parenthesis. Pop on closing parenthesis. Trivial.
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.
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
> 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. :)
The whole Solution().runFunc() thing I just kind of picked up from LeetCode-esque constructions, but I definitely see your point on it being a pure function.
The funny thing is balanced parens can be recognized with with a state machine it is just ugly.
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.
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.
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.
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?
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.
The whole script goes sideways if the candidates whips Perl or Ruby or whatever out, and provides a recursive regex.
My first thought for is_balanced_parens was something like:
Once grouping starts to be an issue I think that different spans need to be broken out from the main section and each treated as isolated fragments to validate.
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.
The counter solution simply needs to check that the counter is non-zero before decrementing.
All cases then work perfectly.
> 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".
- 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.
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.
[1] Technically, until you get to the 64-bit version, it's `CS:IP` (Code Segment, Instruction Pointer).
The register is always an instruction pointer, even if the hardware incorrectly calls it a program counter.
The processor that matters most, by far, is x86. At one point PowerPC wasn't too far behind, and PowerPC still dominates in high-end network gear. Both of these processors are correctly documented. For x86 the name is ip, eip, or rip. For PowerPC the name is usually nip, meaning "next instruction pointer". Sometimes the PowerPC documentation will use "current" instead of "next", or "address" instead of "pointer". All of these are correct.
Also, in electrical engineering, the direction of electricity is taught backwards from what it really does. In all sources I've read, electricity flows from positive to ground, whereas in reality, it's the opposite. Good luck in changing that.
And again, you want to be aware that you are going to have sharply different experiences depending upon the candidate's familiarity with the basic research.
It would be very interesting to walk through a candidate's thinking about this problem "raw," but it would be grossly unfair to ask the same question of an intern who had studied the problem in the last semester.
I have seen interview questions along the lines of "reinvent basic research," but they typically pick something obscure-ish to reduce the likelihood that the candidate has seen it before, and such things are usually more of the dreaded "whiteboard your thinking," rather than judging you based on the code produced.
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?
> 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…
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."
It seems like you could solve this by asking a question no one has ever been exposed to before, or by exposing each candidate to the theory relevant to the question yourself.
Except that the first strategy is guaranteed to fail some of the time, because there are no questions like that.
Why not go the other way?
If I could guarantee that every candidate would read my blog, I'd happily point them to an essay like this, and then in the interview we could work on something meaty, like pattern matching.
That would suit your second recommended strategy. But I wouldn't want to write an essay like this, and then favour those candidates who like to read Hacker News or follow me on Twitter. We're trying to select for talent, not for membership in a tribe :-)
So we're retiring this question, and we already have a few replacements that we use for many candidates. But I won't blog about them, in an attempt to hew closely to the first strategy you suggest.