3 ms·

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

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.
    - deathanatos 8y ago
      > 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.
      - deleted 8y ago
        [deleted]
      - user5994461 8y ago
- kerkeslager 8y ago
  The solution I posted doesn't use a stack, or any other data structures for that matter.
  - user5994461 8y ago
    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.
tzs 8y ago
> 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.
kerkeslager 8y ago
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.

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.
  - deathanatos 8y ago
    > 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.
    - deleted 8y ago
      [deleted]
    - user5994461 8y ago
kerkeslager 8y ago
The solution I posted doesn't use a stack, or any other data structures for that matter.
- user5994461 8y ago
  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.

tzs 8y ago

> 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.

kerkeslager 8y ago

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.