6 ms·

My company always works a "Big-O" question into interview questions. It's funny how we ask about the complexity of the algorithm and maybe 50% of applicants eve

My company always works a "Big-O" question into interview questions. It's funny how we ask about the complexity of the algorithm and maybe 50% of applicants even know what Big-O notation is. It doesn't seem to impact hiring decisions though. We haven't turned anyone down because they miss that question. I think it's because anyone who has programmed for a year or so professionally already understands the concept of inefficient algorithms. They don't need to measure it mathematically, just learn how to optimize.

allan_s 10y ago
I can't agree more, when interviewing I always ask this kind of questions of "theoretical knowledge" not to have the actual answer, but to see how candidates reacts when they don't know. Because if the guy not only admits he does not know directly and is eager to know what it is briefly, then you know that giving your team and environment is favorable to learning, the guy will soon be able to catch up, and it's certainly the same guy that one day will bring in the team's "tips and tricks" channel an article or an insight that will make the team's knowledge grow too.
- erikbye 10y ago
  How can anyone applying for a programming job not know Big-O notation? That's CS101. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. If I were interviewing a candidate, and it was revealed he didn’t know Big-O notation, my next questions would be about data structures, because now I’m suspecting he wouldn’t even know how to implement the simplest of structures. What next, simple pointer arithmetic, is he unable to even walk an array? We are no longer talking about a programmer then. Not knowing these things, I usually chalk it up to either laziness, or lack of interest in understanding how things work. Either way, that’s not someone I’d want on my team. Programmers should be enthusiastic about fundamentals. Good programmers have a “hacker” mentality, a need to know and understand inner workings, a craving to dig deep. I’d say this mentality is what you want from anyone in STEM.
  - digital_ins 10y ago
    I started off disagreeing with your statement but as I read further, I became a believer. In fact, "gotcha" and other trick questions are the worst, but understanding CS fundamentals shows that you were paying attention in class and are probably interested (if not passionate) about CS. If not, there are hundreds of other openings that the candidate can apply to.
  - binarycrusader 10y ago
    How can anyone applying for a programming job not know Big-O notation? That's CS101. You pointed out exactly how someone would not know -- they may have never taken computer science classes and taught themselves programming. Or they may have taken some CS classes, not enough to have covered that particular concept. I'd guess that, especially for older programmers, anecdotally, it's not uncommon to not really understand or use it. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. Just because someone doesn't use the same terminology to describe a set of concepts doesn't mean they don't understand those concepts. Also, I wasn't aware there were were formal qualifications for someone adopting the title of "Programmer", pretty sure big-O notation isn't part of the dictionary definition.
    - ivanhoe 10y ago
      But still you had to hear about it sometimes, somewhere, it's mentioned in pretty much any serious text on algorithms. Thing is that many people see it mentioned, but never bother to stop & learn what it's all about... and that's telling something about their approach to programming (and life) in general.
      - binarycrusader 10y ago
        Sorry, but, it doesn't tell you anything. The world of computers is full of things to learn about, more than almost any one person could learn in a lifetime. People usually learn about what interests them, or what they need to know. It's entirely possible to be an accomplished programmer and never really learn big-O notation just as some programmers never learn assembly or C. Think about it differently, big-O wasn't widely discussed or well known until the 1970s, thanks to Donald Knuth who popularized it. Then consider that many programmers who learned programming may have done so before it was widely known and some may have learned programming from those same people. Are those programmers from roughly 1980 and earlier any less a programmer because they weren't aware of or didn't use big-O notation? Of course not. Is big-O notation something most programmers should consider learning? Yes. But we should not seek to exclude others from a profession simply because they don't meet arbitrary criteria we think is necessary when they are clearly already actively engaged in that profession.
user5994461 10y ago
That makes sense. Big-O notation is so overrated. A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O. http://homepages.e3.net.nz/~djm/containerchoice.png http://homepages.e3.net.nz/~djm/containerchoice.png
- bogomipz 10y ago
  > "That makes sense. Big-O notation is so overrated." Can you explain how having a classification that allows one to determine whether something is logarithmic vs vs quadratic is so overrated? Isn't that a bit like saying "Algebra is so overrated"? Also Donald Knuth introduced Big O somewhere around the mid 1970s and C++ didn't come along until 1979. https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth-12 https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth... Also your link is a visualization of ADTs not run times. And while it true that ADTs are chosen for certain guarantees it still depends on how they are used in an algorithm.
  - mikebenfield 10y ago
    I think (hope?) that user5994461's post was tongue in cheek. BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathematicians like Paul Bachmann and Landau, many decades before the 1970s.
    - BeetleB 10y ago
      Mathematicians used it for asymptotic expansions of mathematical expressions. Its use in computer science for algorithmic complexity came later. In fact, I believe in the early TAOCP, Donald did not use big O, but instead would derive the full expression where possible.
    - bogomipz 10y ago
      I didn't know the OPs post was tongue and cheek. Sometimes it hard to tell : ) Sure "O" goes back to mathematicians in the late 19th century. What I meant was that Knuth introduced Big O(mnicron) in the context of "Computer Science" literature. This is the source I am referring to from 1976 SIGACT News: http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron... On page 21 or page 4 of the PDF: "I would like to close this letter by discussing a competing way to denote the order of function growth. My library research turned up the surprising fact that this alternative approach actually antedates the O-notation itself. " On page 22 or page 5 of the PDF: "The main reason why 0 is so handy is that we can use it right in the middle of formulas (and in the middle of English sentences and in tables which show the running times for a family of related algorithms etc.)."

allan_s 10y ago

I can't agree more, when interviewing I always ask this kind of questions of "theoretical knowledge" not to have the actual answer, but to see how candidates reacts when they don't know. Because if the guy not only admits he does not know directly and is eager to know what it is briefly, then you know that giving your team and environment is favorable to learning, the guy will soon be able to catch up, and it's certainly the same guy that one day will bring in the team's "tips and tricks" channel an article or an insight that will make the team's knowledge grow too.

erikbye 10y ago
How can anyone applying for a programming job not know Big-O notation? That's CS101. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. If I were interviewing a candidate, and it was revealed he didn’t know Big-O notation, my next questions would be about data structures, because now I’m suspecting he wouldn’t even know how to implement the simplest of structures. What next, simple pointer arithmetic, is he unable to even walk an array? We are no longer talking about a programmer then. Not knowing these things, I usually chalk it up to either laziness, or lack of interest in understanding how things work. Either way, that’s not someone I’d want on my team. Programmers should be enthusiastic about fundamentals. Good programmers have a “hacker” mentality, a need to know and understand inner workings, a craving to dig deep. I’d say this mentality is what you want from anyone in STEM.
- digital_ins 10y ago
  I started off disagreeing with your statement but as I read further, I became a believer. In fact, "gotcha" and other trick questions are the worst, but understanding CS fundamentals shows that you were paying attention in class and are probably interested (if not passionate) about CS. If not, there are hundreds of other openings that the candidate can apply to.
- binarycrusader 10y ago
  How can anyone applying for a programming job not know Big-O notation? That's CS101. You pointed out exactly how someone would not know -- they may have never taken computer science classes and taught themselves programming. Or they may have taken some CS classes, not enough to have covered that particular concept. I'd guess that, especially for older programmers, anecdotally, it's not uncommon to not really understand or use it. I don't care if you're self-taught, it's audacious to even call yourself a programmer if you don't know the very basics of algorithms and data structures. Just because someone doesn't use the same terminology to describe a set of concepts doesn't mean they don't understand those concepts. Also, I wasn't aware there were were formal qualifications for someone adopting the title of "Programmer", pretty sure big-O notation isn't part of the dictionary definition.
  - ivanhoe 10y ago
    But still you had to hear about it sometimes, somewhere, it's mentioned in pretty much any serious text on algorithms. Thing is that many people see it mentioned, but never bother to stop & learn what it's all about... and that's telling something about their approach to programming (and life) in general.
    - binarycrusader 10y ago
      Sorry, but, it doesn't tell you anything. The world of computers is full of things to learn about, more than almost any one person could learn in a lifetime. People usually learn about what interests them, or what they need to know. It's entirely possible to be an accomplished programmer and never really learn big-O notation just as some programmers never learn assembly or C. Think about it differently, big-O wasn't widely discussed or well known until the 1970s, thanks to Donald Knuth who popularized it. Then consider that many programmers who learned programming may have done so before it was widely known and some may have learned programming from those same people. Are those programmers from roughly 1980 and earlier any less a programmer because they weren't aware of or didn't use big-O notation? Of course not. Is big-O notation something most programmers should consider learning? Yes. But we should not seek to exclude others from a profession simply because they don't meet arbitrary criteria we think is necessary when they are clearly already actively engaged in that profession.

user5994461 10y ago

That makes sense. Big-O notation is so overrated. A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O. http://homepages.e3.net.nz/~djm/containerchoice.png http://homepages.e3.net.nz/~djm/containerchoice.png

bogomipz 10y ago
> "That makes sense. Big-O notation is so overrated." Can you explain how having a classification that allows one to determine whether something is logarithmic vs vs quadratic is so overrated? Isn't that a bit like saying "Algebra is so overrated"? Also Donald Knuth introduced Big O somewhere around the mid 1970s and C++ didn't come along until 1979. https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth-12 https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth... Also your link is a visualization of ADTs not run times. And while it true that ADTs are chosen for certain guarantees it still depends on how they are used in an algorithm.
- mikebenfield 10y ago
  I think (hope?) that user5994461's post was tongue in cheek. BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathematicians like Paul Bachmann and Landau, many decades before the 1970s.
  - BeetleB 10y ago
    Mathematicians used it for asymptotic expansions of mathematical expressions. Its use in computer science for algorithmic complexity came later. In fact, I believe in the early TAOCP, Donald did not use big O, but instead would derive the full expression where possible.
  - bogomipz 10y ago
    I didn't know the OPs post was tongue and cheek. Sometimes it hard to tell : ) Sure "O" goes back to mathematicians in the late 19th century. What I meant was that Knuth introduced Big O(mnicron) in the context of "Computer Science" literature. This is the source I am referring to from 1976 SIGACT News: http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron.pdf http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron... On page 21 or page 4 of the PDF: "I would like to close this letter by discussing a competing way to denote the order of function growth. My library research turned up the surprising fact that this alternative approach actually antedates the O-notation itself. " On page 22 or page 5 of the PDF: "The main reason why 0 is so handy is that we can use it right in the middle of formulas (and in the middle of English sentences and in tables which show the running times for a family of related algorithms etc.)."