4 ms·

When have you ever needed to know the exact complexity function for bubble sort (beyond the simple fact that it's in a class well above that of any algorithm yo

When have you ever needed to know the exact complexity function for bubble sort (beyond the simple fact that it's in a class well above that of any algorithm you'd typically want to use) in order to solve a real, actual work-related problem? Right there, on the spot? That's the point of the "hate" behind these questions.

eveningcoffee 10y ago
If you do not know the complexity class of the bubble sort then you probably do not a have formal CS education. It also follows that it is possible that when you see a similar bad solution then you are not able to recognize it as such. I think that these three questions showed are quite good and fair (for example I did not what is Hopscotch hashing, but it looks quite important after looking it up, so thanks for this). Some of such questions might be possibly indifferent for the position you were applying, but seeing some hate behind these questions is in my opinion quite unjustified.
- kafkaesq 10y ago
  If you do not know the complexity class of the bubble sort then you probably do not a have formal CS education. No, it means you're smart and have learned to sift out unimportant matters of detail ("Was bubble sort, which I only ever had to think about for a week or two the first half of my sophomore algorithms class, and was only ever brought up as a negative example anyway, O(n^2) or O(n^3)?") in order to focus on much more interesting and useful stuff.
  - eveningcoffee 10y ago
    Pretty much spot on and that was my point. You can answer to this question, you know what is complexity class, you know that it is a negative example and it is rather bad. See, I am not a recruiter or interviewer, but this question feels to me like an useful one to prune out ignorant fools who start to lament how unfair is to ask such questions instead of giving more or less correct answer. Naturally if short direct answer is the only accepted answer and there is no way to discuss these things with the interviewer then I would also walk away.
- hnbroseph 10y ago
  > If you do not know the complexity class of the bubble sort not knowing or remembering doesn't preclude one from understanding that one approach or technique can be more (or less) costly than another.
- wutbrodo 10y ago
  > If you do not know the complexity class of the bubble sort then you probably do not a have formal CS education. It also follows that it is possible that when you see a similar bad solution then you are not able to recognize it as such. This is absolutely absurd. I have a CS degree from Berkeley (universally considered one of the best CS programs in the world), and I spent the last few years on an unusually CS-focused team within Google (specifically, artificial intelligence). Off the top of my head, I could easily imagine not remembering what exactly bubble sort is. What's the use of retaining the details of an algorithm that's literally held up as the "don't do this" solution to sorting? The most I can imagine being useful is knowing the theoretical best case average complexity of a sort. And my job is wayyy more CS-focused than the average engineering job at Google (let alone elsewhere). You heavily overestimate how useful rote memorization is to real-world productivity. Whether a candidate _understands_ these concepts, on the other hand, can actually be illuminating. If you described bubble sort to someone and asked him to describe the complexity, then you're getting all the signals you're describing about CS understanding and education. (though there's controversy about the usefulness of these skills as well)
  - ubernostrum 10y ago
    You're not going to get anywhere arguing with people who believe these are useful questions. Though to be honest, Google uses those kinds of questions and apparently treats them as useful, so I'm not sure why you'd have wanted to work there.
    - wutbrodo 10y ago
      I've been on both sides of the interview process at Google over the last half decade (I no longer work there) and I can tell you that asking people to recite random facts by rote was not part of their interview guidelines for as long as I was there. This includes a couple dozen interviews I conducted and the candidate notes of the other interviewers.
      - ubernostrum 10y ago
        I got hit with a barrage of random trivia during one of the phone screens I did last year. Eventually got fed up with their process, told the interviewer what I thought of it and hung up. (which, to point out at least one upside, is the only way I've ever discovered of getting a company I don't want to work for to stop bugging me with recruiter spam)
GFK_of_xmaspast 10y ago
I've had at least one point in my career where bubble sort was the right tool for the job.
- kafkaesq 10y ago
  But that's the whole point -- it's a corner case. And hence, kind of silly to use as material to grill people on.
  - eveningcoffee 10y ago
    I do not think that these questions probe some corner cases. Rather these probe the general knowledge about the field. Bubble sort question probes the understanding about the complexity theory, hopscotch hashing about concurrent algorithms and CAP theorem about problems with distributed databases. Naturally when these questions are not open for discussion and instead only a short answer is expected then there is in my opinion something wrong with the interviewer or with the company. You have to understand that the other side knowns in fact nothing about you and I find these questions to be quite fair to improve the situation.
    - kafkaesq 10y ago
      Bubble sort question probes the understanding about the complexity theory, It's just that, again, you're picking a very marginal example to do that with. And more fundamentally -- simply asking someone "What's the complexity of $foo"? doesn't tell you anything about whether they "understand" complexity. It only tells you whether they've adequately memorized that particular cell on their crib sheet. As they are thoroughly incentivized to do, thanks to people employing interview techniques like these.
      - eveningcoffee 10y ago
        I definitely agree with you that shallow quizzes are not very informative and are alone not a good methodology for job interviews. Naturally this question in isolation is not very informative and it is hard to differentiate if the answer to it comes from a more general understanding or is just memorized. It has to be supported with other questions and wider discussion. What I want to say is that in a larger context this question is still not unfounded and it is hard for me to consider this or any other listed questions as a signalling a dominant status.
varjag 10y ago
OK, I'll bite. Point one, it checks if you understand the most primitive sorting algorithm out there. Pretty low bar assessment of your general CS knowledge. Point two, it checks whether the candidate has understanding of computational complexity. Now you might argue that you don't need any of that in the day job, but that's on you. If the interviewer wants to check you have fairly basic minimum of understanding of very basic CS concepts, that's a suitable question to ask.
- kafkaesq 10y ago
  Do you see any problem with the idea that: "Has memorized the complexity class for one particular, indisputably marginal sorting algorithm" is equivalent to "Has an understanding of computational complexity"? Now you might argue that you don't need any [understanding of complexity] in the day job That is quite clearly not what what said.
  - varjag 10y ago
    In theory there is a difference, in practice - none. People would at least know what that is (and hence have no problem gauging bubblesort complexity), or you'd have blank stare back. Just wonder what would you suggest as an alternative, if you need to confirm basic algorithms proficiency and understanding of big-O? You inevitably arrive to an algorithm question, and bubblesort is as good as any.
    - kafkaesq 10y ago
      Or you'd have blank stare back. Actually the blank stare means "What is this, sophomore year again? I can't believe anyone still cares about bubble sort." Just wonder what would you suggest as an alternative? Look at their GitHub/Mercurial account (which you've been ignoring all this time in your desperate search for something to nail them on, but if you would spend a second or two looking, you'd find is chuck full of algorithm stuff -- much of it way more intricate than bubble sort). And ask as many questions as you like based on some project you find there. Or, pick a problem you're working on that's algorithm-related (but which you genuinely don't fully know how to solve). Use that as discussion material. What approach they'd suggest, given that the data are sparse / not evenly distributed, whatever. You know, as if they were a peer. Not an interrogation subject.

eveningcoffee 10y ago

If you do not know the complexity class of the bubble sort then you probably do not a have formal CS education. It also follows that it is possible that when you see a similar bad solution then you are not able to recognize it as such. I think that these three questions showed are quite good and fair (for example I did not what is Hopscotch hashing, but it looks quite important after looking it up, so thanks for this). Some of such questions might be possibly indifferent for the position you were applying, but seeing some hate behind these questions is in my opinion quite unjustified.

kafkaesq 10y ago
If you do not know the complexity class of the bubble sort then you probably do not a have formal CS education. No, it means you're smart and have learned to sift out unimportant matters of detail ("Was bubble sort, which I only ever had to think about for a week or two the first half of my sophomore algorithms class, and was only ever brought up as a negative example anyway, O(n^2) or O(n^3)?") in order to focus on much more interesting and useful stuff.
- eveningcoffee 10y ago
  Pretty much spot on and that was my point. You can answer to this question, you know what is complexity class, you know that it is a negative example and it is rather bad. See, I am not a recruiter or interviewer, but this question feels to me like an useful one to prune out ignorant fools who start to lament how unfair is to ask such questions instead of giving more or less correct answer. Naturally if short direct answer is the only accepted answer and there is no way to discuss these things with the interviewer then I would also walk away.
hnbroseph 10y ago
> If you do not know the complexity class of the bubble sort not knowing or remembering doesn't preclude one from understanding that one approach or technique can be more (or less) costly than another.
wutbrodo 10y ago
> If you do not know the complexity class of the bubble sort then you probably do not a have formal CS education. It also follows that it is possible that when you see a similar bad solution then you are not able to recognize it as such. This is absolutely absurd. I have a CS degree from Berkeley (universally considered one of the best CS programs in the world), and I spent the last few years on an unusually CS-focused team within Google (specifically, artificial intelligence). Off the top of my head, I could easily imagine not remembering what exactly bubble sort is. What's the use of retaining the details of an algorithm that's literally held up as the "don't do this" solution to sorting? The most I can imagine being useful is knowing the theoretical best case average complexity of a sort. And my job is wayyy more CS-focused than the average engineering job at Google (let alone elsewhere). You heavily overestimate how useful rote memorization is to real-world productivity. Whether a candidate _understands_ these concepts, on the other hand, can actually be illuminating. If you described bubble sort to someone and asked him to describe the complexity, then you're getting all the signals you're describing about CS understanding and education. (though there's controversy about the usefulness of these skills as well)
- ubernostrum 10y ago
  You're not going to get anywhere arguing with people who believe these are useful questions. Though to be honest, Google uses those kinds of questions and apparently treats them as useful, so I'm not sure why you'd have wanted to work there.
  - wutbrodo 10y ago
    I've been on both sides of the interview process at Google over the last half decade (I no longer work there) and I can tell you that asking people to recite random facts by rote was not part of their interview guidelines for as long as I was there. This includes a couple dozen interviews I conducted and the candidate notes of the other interviewers.
    - ubernostrum 10y ago
      I got hit with a barrage of random trivia during one of the phone screens I did last year. Eventually got fed up with their process, told the interviewer what I thought of it and hung up. (which, to point out at least one upside, is the only way I've ever discovered of getting a company I don't want to work for to stop bugging me with recruiter spam)

GFK_of_xmaspast 10y ago

I've had at least one point in my career where bubble sort was the right tool for the job.

kafkaesq 10y ago
But that's the whole point -- it's a corner case. And hence, kind of silly to use as material to grill people on.
- eveningcoffee 10y ago
  I do not think that these questions probe some corner cases. Rather these probe the general knowledge about the field. Bubble sort question probes the understanding about the complexity theory, hopscotch hashing about concurrent algorithms and CAP theorem about problems with distributed databases. Naturally when these questions are not open for discussion and instead only a short answer is expected then there is in my opinion something wrong with the interviewer or with the company. You have to understand that the other side knowns in fact nothing about you and I find these questions to be quite fair to improve the situation.
  - kafkaesq 10y ago
    Bubble sort question probes the understanding about the complexity theory, It's just that, again, you're picking a very marginal example to do that with. And more fundamentally -- simply asking someone "What's the complexity of $foo"? doesn't tell you anything about whether they "understand" complexity. It only tells you whether they've adequately memorized that particular cell on their crib sheet. As they are thoroughly incentivized to do, thanks to people employing interview techniques like these.
    - eveningcoffee 10y ago
      I definitely agree with you that shallow quizzes are not very informative and are alone not a good methodology for job interviews. Naturally this question in isolation is not very informative and it is hard to differentiate if the answer to it comes from a more general understanding or is just memorized. It has to be supported with other questions and wider discussion. What I want to say is that in a larger context this question is still not unfounded and it is hard for me to consider this or any other listed questions as a signalling a dominant status.

varjag 10y ago

OK, I'll bite. Point one, it checks if you understand the most primitive sorting algorithm out there. Pretty low bar assessment of your general CS knowledge. Point two, it checks whether the candidate has understanding of computational complexity. Now you might argue that you don't need any of that in the day job, but that's on you. If the interviewer wants to check you have fairly basic minimum of understanding of very basic CS concepts, that's a suitable question to ask.

kafkaesq 10y ago
Do you see any problem with the idea that: "Has memorized the complexity class for one particular, indisputably marginal sorting algorithm" is equivalent to "Has an understanding of computational complexity"? Now you might argue that you don't need any [understanding of complexity] in the day job That is quite clearly not what what said.
- varjag 10y ago
  In theory there is a difference, in practice - none. People would at least know what that is (and hence have no problem gauging bubblesort complexity), or you'd have blank stare back. Just wonder what would you suggest as an alternative, if you need to confirm basic algorithms proficiency and understanding of big-O? You inevitably arrive to an algorithm question, and bubblesort is as good as any.
  - kafkaesq 10y ago
    Or you'd have blank stare back. Actually the blank stare means "What is this, sophomore year again? I can't believe anyone still cares about bubble sort." Just wonder what would you suggest as an alternative? Look at their GitHub/Mercurial account (which you've been ignoring all this time in your desperate search for something to nail them on, but if you would spend a second or two looking, you'd find is chuck full of algorithm stuff -- much of it way more intricate than bubble sort). And ask as many questions as you like based on some project you find there. Or, pick a problem you're working on that's algorithm-related (but which you genuinely don't fully know how to solve). Use that as discussion material. What approach they'd suggest, given that the data are sparse / not evenly distributed, whatever. You know, as if they were a peer. Not an interrogation subject.