views:

2189

answers:

36

A colleague of mine caused a long e-mail conversation by saying:

Of the probably 30+ people I’ve given a phone interview to, not a one (including people with Masters degrees in CS!!) has been able to tell me the big O of bubble sort- or any other sort for that matter, and maybe 2-3 seemed to have an clue what I was talking about.

Am I expecting too much of people with CS degrees? Maybe. But people with undergrad and Masters degrees in CS?

The last few people with CS degree’s couldn’t even describe how bubble sort worked.

The potential developer would be working on web based line of business apps, not scientific or game programming. Some people in the conversation feel that computational theory isn't so important when using modern framworks, i.e. no one should be writing a sort after CS 101.

Personally, I think that the kind of person who would care about the underlying theory is going to be a better programmer.

What do you think?

+2  A: 

Regardless of whether it will be important during the position for them to understand this (which is debatable, even if you're 'just' doing web B2B stuff), I expect people with computer science degrees to understand this particular thing. Imho, this is something that's taught in a lot of intro CS classes.

Paul Morie
+17  A: 

It's a reasonable question to ask someone who claims to have a CS degree. It's a fairly basic and fundamental concept that they should have learned. If they don't know that it could be a sign of other problems.

However, I might not expect someone who learned to program on their own and doesn't have a CS degree to know that.

onedozenbagels
I don't know about this contention. It's like the anectodal story about the supposed software expert who uses the CD-ROM tray in his computer as a coffee holder; maybe he just learned on a machine that had no CD drives, but it's highly suspect.
McWafflestix
+1  A: 

Just In Time Learning. They should only know it if they need to know it. However, they should always be aware that it is there for them to learn.

I personally know how to deduce the growth of an algorithm, but I don't think it really helped me in writing code. Figuring out how fast or slow an algorithm is, is more intuitive than scientific, until you have to know; then it becomes scientific and you'd better have someone who knows how to do it.

Malfist
I won't vote this down, but I strongly disagree with it, because I think that people that don't have that background won't have any conception of what it entails. People that have a solid background in O() type thinking won't even follow paths that are more likely to cause some problems later...whereas (some) people without that background won't realize what the problem is or how to tackle it. You're absolutely right in that there is an intuitive side to it, but getting the rigor from studying it in detail helps enormously.
Beska
+2  A: 

It's more important to know the concept of time complexity than the specific Big-O notation. Even if someone can't tell you that a doubly nested for loop is O(n^2), they should know that using it all the time is probably going to cause slowdowns.

Marc W
it's not that "it causes slowdowns"; understanding the NATURE of the slowdowns that can occur is more important than just understanding that things run slower. the whole idea of algorithmic complexity has to do with understanding that processing 2 things takes longer than 1, but HOW MUCH longer is a critical thing, and specifically how "how much longer" increases as the number of things increase.
McWafflestix
@McWafflestix: You should add your comment to your post, because I haven't seen it put that well elsewhere.
Beska
+13  A: 

I don't require memorizing algorithms, but if the guy doesn't know what is O(n^2), I reject him, and I think You should do the same.

Reef
I think it's a little bit overly simplistic, but yeah, i generally agree with you.
McWafflestix
+8  A: 

I think you've been getting some serious duds applying for your positions. To be honest, I'd really wonder if they actually have the degrees that they claim to have. Big O notation is NOT an optional consideration in computer science; understanding it and understanding why it is important is a critical requirement for really understanding computer science.

It doesn't really matter what you're writing for; Big O notation is important to understand. Even if you're using modern frameworks, you need to know this stuff. For heaven's sake, just because modern frameworks provide you with a hashtable implementation doesn't mean that you shouldn't know what the underlying Order of using a hashtable is. In fact, the fact that they provide the tools makes it MORE important to know what the underlying theories are, because you don't have the ability to investigate the source code; you HAVE to know how a hashtable works to be able to use one, not just write one.

Seriously, if you have a person with a CS degree who can't describe how a bubble sort works, show them the door. IMMEDIATELY. No apologies, no questions... the simple fact is, they're either lying about their degree, or their knowledge is so poor that they won't be useful (most likely a combination of both).

Edit: Let me clarify. I'm not trying to indicate that any prospective candidate needs to know exactly what a bubble sort is and how it works (I'm willing to understand that some knowledge has "aged out"). But they had better (in my opinion) know what the algorithmic implications of such a sort are versus another type of sort; if they don't, they don't have the knowledge to work successfully in a software development job, in my opinion.

McWafflestix
Or...it just doesn't matter in the practical application of software development. There are so many other things that I *do* know, and Big O notation is simply not that important. I use Java, and I use HashMap and TreeMap and the underlying implementation has *never* mattered. There just too many other things that should be optimized.
Gary Kephart
NONONO! I disagree with @Gary so strongly on this that I can't say. Of course you'll use things like HashMap, TreeMap etc...but without understanding how they're implemented and what their overall O(n) complexity is, you could be making very bad choices time-wise, because from the outside they both do what you want. And you wouldn't know until you scaled it up.
Beska
You're entitled to your opinion; mine, however, is that if you don't understand Big O notation, you're missing out on some critical understanding of why some things are more doable than others. Effectively, I think you can be a good programmer without knowing Big O notation, but I don't think you can be a good software engineer without knowing it.
McWafflestix
Gary, yes, it has mattered; it's just that your software is inefficient, and you've never realized it.
mquander
@Beska: completely, absolutely, entirely agreed. As I said in a previous comment, there's something there about the difference between programming and software engineering.
McWafflestix
@mquander: yup, exactly. disturbing how many upvotes his comment has gotten, though.
McWafflestix
Waffle, I bet it's just all the code monkeys with extremely weak CS backgrounds voting that up (and downvoting your answer). They don't like to acknowledge their weakness.
dss539
This. 1000 times this. It's like someone with a European History degree that can't give you a 3 minute overview of the history of Rome (Aeneis, the Etruscans, Kingdom, Republic, Empire, Julius Caesar, the two Triumvirates, Constantine, eastern/western Empires, Byzantine empire, legacy of the Roman Empire in the Czars of Russia).
Adam Jaskiewicz
I mentioned further down that it's like a math major drawing a blank if you ask him what Pascal's Triangle is. Whether or not he's ever going to use Pascal's Triangle, it's a pretty big red flag that he doesn't give a shit about math if he doesn't know what it is.
mquander
@mquander please show me specifically where my software has been inefficient. Can't, can you, because you have never seen my [email protected] look, I know the basics of Big O notations. I learned it in college and it's never been brought up since then by anybody. However, for optimization, we all know it's bad to optimize before knowing where the problem *really* is. And in my experience, it's never been at the point where Big O has mattered.
Gary Kephart
@dss539: exactly; the number of downvotes I've gotten on this is kind of ridiculous...
McWafflestix
Using the right data structures is not some kind of "premature optimization." It's writing your code correctly. As for where your software has been inefficient, apparently you use TreeMaps and HashMaps (I don't use Java, but I see that this is a key/value binary tree versus a hashtable) interchangeably, so paste some code where you use one or the other and I suppose it'll have a 50/50 chance of being wrong.
mquander
@Gary: Entirely possible that it's never been at the point where Big O mattered for you. But that doesn't mean it's efficent, and if the work scales up past a certain point, if you're using the wrong tool for the job, it will burn you (general you). If the person doesn't know about Big O, they can't even begin to decide if that trade off makes sense. Sure premature optimization is bad, blah, blah, blah... But you still won't catch me writing many (2^n) algorithms without thinking about it reeeeal hard first, because I've got a good idea that I'm headed down a bad path.
Beska
@garykephart: you're very defensive; of course nobody can show inefficiencies in code they haven't seen.
McWafflestix
@beska: bingo. the point that it's necessary to understand what the trade offs are is exactly right.
McWafflestix
@McWafflestix not trying to be defensive, just amazed that someone would state such a broad assumption as a fact when they've never seen any of my code
Gary Kephart
It's a fact of probability that randomly applying data structures and algorithms has a high chance of producing extremely slow code. If you don't understand the complexity of data structures, how do you even go about picking one? You just use the same one in all cases?
dss539
"Hey, this one takes a key and a value, and you can put things in it. I guess I'll put my stuff in it."
mquander
I like to use an ArrayList<Object>. I can fit just about anything into one of those. See? arrayList.add("theAnswer".hashCode(), Integer.valueOf("42"));
Adam Jaskiewicz
@GaryKephart: well, I can agree that there wasn't a point in an ad hominem attack against your code. I believe what mquander was trying to say was that your code might be inefficient, and you will have no way of knowing it.
McWafflestix
I use a SortedList for everything, because if my data always stays in order, I never have to defragment it.
mquander
@mquander Do you use the generics? I use the generics... if you put <Object> after your SortedList, you can make sure you only put objects into it. You don't want things that aren't Objects in your SortedList.
Adam Jaskiewicz
I use Object for everything except for SortedList<Customer> and SortedList<Employee>. I don't believe in treating people like objects.
mquander
@mquander: lol!
McWafflestix
+48  A: 

I'd be concerned, but not because a web developer necessarily needs to know complexity theory to do their job.

My main concern would be that getting through a BS in CS without picking up at least the basics of Big O demonstrates that you weren't paying attention at all!

Ryan
This is my take on it. I don't think I'd be looking for a CS degree for web dev, but if that's on the resume, you'd better be able to explain some basic CS concepts.
Adam Jaskiewicz
I would agree with the point that they must not have been listening at all. Either that, or they're just lying about their CS degree.
McWafflestix
I don't know what possesses someone to LIE about getting a degree.
Adam Jaskiewicz
It's real easy to be an unqualified lousy programmer without knowing that you are actually unqualified or lousy. If you're in that position, you might feel like not having a degree is just a "formality" and it doesn't hurt to lie about it since you can do that job just as well anyway.
mquander
But you *HAVE* to be smart enough to realize that a cursory check on "did this person actually get this degree" is going to catch you in that lie...
Adam Jaskiewicz
No one *has* to be smart enough to do anything, unfortunately. :( They can quite easily waste every interviewer's time with their stupidity.
dss539
Like DSS said, it costs nothing but time for a candidate who knows nothing to apply to 500 programming jobs, and you only need to get accepted by one dumb interviewer to make it pay off.
mquander
@mquander: so true. I've interviewed more than a few of those candidates.
McWafflestix
@McWafflestix - and just out of interest, how many of them did you hire? :P
BenAlabaster
@balabaster: absolutely zero of them. :-)
McWafflestix
@mquander I.e. "Throw enough crap at a wall and eventually something will stick." I see that a lot.
Michael Todd
+5  A: 

Yes you should care, but you are asking the wrong questions.

Who really cares or knows about bubble/insertion/selection sort when there are libraries and better implementations like quicksort, mergesort, heapsort, radixsort?

They should know the complexity of at least 1 sort.

What they should really know is the complexity of containers which is used much more often than sorting algorithms. Knowing the difference between a linked list, array, and hash table should be required.

Unknown
+13  A: 

The big issue is that behind the scenes in these tools and frameworks they're using, routines are running that have O(whatever) impacts. When you're writing a little app to work on a small dataset, it may not matter. When you work with a database with thousands, even millions of records, the design of the schema and data stored, and how you access it from these high-level tools will have at least the potential to invoke an O(n*n) algorithm, and understanding what that is, and why they are slow, will make it less likely to get into that problem. Also, if you do, they'll understand there's likely an algorithmic issue they need to revise things to avoid, instead of dithering around the edges trying to "optimize" by reducing 'k' while ignoring 'n' and not looking for a lower O() solution.

jesup
Excellent sum-up. You go up.
Beska
Agreed; well spoken. +1.
McWafflestix
+2  A: 

A computer program is a sum of its parts. To create a program that is the best it can be, each part must be created the best way it can be.

Not knowing the nomenclature for perhaps the most fundamental and important aspect of superb programming is certainly a red flag. I don't know what types of education these people received, but perhaps they simply know the concept by another name (but I doubt it).

If it were up to me, I wouldn't hire a software engineer who can't tell me how efficient an algorithm is.

hypoxide
+1  A: 

might be worth asking, but I wouldn't make any decisions based on it. very rare that it matters unless you are hiring an algorithm coder.

phil swenson
Completely untrue. It doesn't matter until it REALLY REALLY matters, usually several years down the line, when the "little tiny loop at the heart of everything that nobody's going to care about" starts dragging down your app. I've seen this more times than I can count.
McWafflestix
I disagree. A programmer who doesn't understand this will probably cause more work than they solve (ie, do negative work)-- it will take a long time to unravel the mistakes they make because they don't understand the complexity of various algorithms.
mmr
"very rare" is subjective :(
dss539
What kind of code are you writing that doesn't on some level require algorithms?
Demi
1 in a billion happens a thousand times in your new hard disk.
Tetsujin no Oni
+1  A: 

He might not know big-O; in this case, he should know enough hot topics to cover this.

I mean, you have to know something! If someone's something approaches empty set, why would you want him in?

alamar
A: 

Rejecting people for something that they could learn on wikipedia in 5 minutes is rather pointless. But if it's important for you feel free. You may just be toss the best developer for you group over a simple topic they will never use, forgot the term of, of simplely never heard of becasue they have either never taken programming classes of been in a class that it was covered.

Matthew Whited
If they haven't heard of that notation then their CS education is quite poor. When they run in to an algorithmic complexity problem, they are not going to realize "oh I better go read up on big O notation". They have to know about it *before* they have the problem otherwise they won't even know what to search for.
dss539
If they have a CS degree, they've almost certainly covered it. They may have forgotten the term, but they should "[seem] to have an clue what I was talking about."
Adam Jaskiewicz
Goodness. God forbid he toss the best developer that's never heard of big-O notation or bubble sort. That guy must be a real catch.
mquander
Normally I'd say you are absolutely correct. Unfortunately in this case this really did diserve the -5 it got before I got here.
Joshua
Where's the jaw-drop smilie? This certainly deserves one!
Loren Pechtel
Good to see all your guys feel proud of defending a sheet of paper. The best developers I know don't have degrees and some them only have a GED.
Matthew Whited
I don't care about pieces of paper. That's no justification for not understanding something pretty darn important.
Loren Pechtel
It's not about the paper. It's about understanding the concept. You claim to have an intuitive understanding of the concept, and that's fine. However, someone who claims to have a CS degree should also know what word is used to refer to this concept. Speaking the same language is helpful when communicating concepts.
dss539
And for all the business terms that get toss around what is wrong with the 30 seconds it takes to cover that impedance gap. As well as how often does the conversation really come up with "Well what if your Big-O for that method?" You would be more likly to as were is the problem. And I can pretty much promise you it will be with deep recursion or a try at rolling your own query engine.
Matthew Whited
+7  A: 

I think it's more likely they don't remember bubble sort. Most learn that in the first year of school and it isn't important after that. It is more meaningful if they can't figure out the big O of an algoritm they know well.

Albinofrenchy
+1 - knowing how a particular named algorithm works is a pretty arbitrary and silly thing to test for. OTOH any CS grad should be able to look at a given algorithm and analyze its runtime complexity, no matter how far out of school they are.
Sarah Mei
I agree that the concept is more important than the specific case. *However*, even if you forget the complexity of bubble sort, you should be able to mentally derive it in a few seconds. If you have forgotten the algorithm for bubble sort, you must have a pretty rusty memory.
dss539
If they don't remember the algorithm, my assumption is that they would say "I don't remember exactly how that works, can you remind me", and that if the questioner is really interested in their comprehension of algorithmic complexity, they will inform them; if after being informed of the basic algorithm, they still have no clue... well, they prove that they really have no clue overall.
McWafflestix
+1  A: 

This is highly subjective and varies a lot.

For example, I work with 4 people, 3 with a Master Degree and the other with no degree at all. For those "simple" tasks, like CRUD applications, the guy with no formal education is the most productive.

The others prefer more difficult tasks and do not work with motivation if I handle them a CRUD application.

So, what I am saying is that there is no need to know certain subjects if your work is just "simple" tasks.

fbinder
AKA code monkey.
Unknown
Sounds like your tooling might be a little weak. If you do a lot of CRUD stuff, it should be very quick and efficient to create some new CRUD functionality. So quick and efficient that your top level coders get done with it before they have a chance to be bored. Of course I don't know your exact circumstances so this advice may not apply.
dss539
Sure, for some jobs, having a Masters in CS just isn't needed. But someone with a Masters (or even a BS, if they went to a school where they actually had to do *anything*) should definitely be able to talk about O() complexity very comfortably, and should be able to talk about sorting algorithms, even if they've forgotten the names of the various implementations.
Beska
CRUD was just an example. Even with the right tools, you still have to do some simple tasks.
fbinder
I love how some of these guys seem know what’s best for everyone’s projects. Maybe they should just get over themselves.
Matthew Whited
So you are taking an anti-tooling stance?
dss539
A: 

I wished that my study had involved the underlying technology. I had to do a minor to get some basic understanding of data structures and algorithms which I find a bit sad. In defence of my study they did explain the big O notation. The idea behind it should at least be known. I do agree that for writing "boring software" you do not need to know what a hashtable is. Higher lever languages and frameworks provide you with just about everything out of the box.

The general consensus seems to be, "You're not going to write a better implementation, so don't even bother with it."

Onots
But they do need to know what a hash table is. What if they decide to store CRUD data that needs fast access in a linked list instead of a hash table?
Unknown
@unknown: precisely correct.
McWafflestix
@Unknown, you're right. I should have chosen better wording. They don't need to know what tool to use, and even how to use the tool. But they don't need to know how the tool works.
Onots
+1  A: 

You fail to make a distinction between understanding Big Oh notation (or time complexity in general) and having memorized the time complexity of a bubble sort. I can give you a very thorough explanation of the former, and could not remember the latter to save my life. Of course, if you sat me down in front of (pseudo)code for a bubble sort I could tell you the time complexity of it.

Sparr
It's a good point about the original question.
McWafflestix
A: 

Big-O is hardly relevant to doing web development, so just forget about that. Instead, focus on your goal - you said:

Personally, I think that the kind of person who would care about the underlying theory is going to be a better programmer.

I think you're on the right track here, except that caring about Big-O indicates the candidate will be a good systems programmer while understanding, say, details about the HTTP stack or the internals of Ruby on Rails would indicate they'll be a good web developer.

Think of it this way, if I want to hire a mechanic to work on trucks and during the interview I start asking about the performance considerations of compact cars... would it be shocking if the guy didn't care? Probably he cares a whole lot about the equivalent topic in his area of expertise (and the kind of work you're potentially going to hire him for).

thenduks
Algorithm performance is irrelevant to web development? WTF?
dss539
@dss539: yeah, that boggles me too...
McWafflestix
If a web developer is doing any scripting or has any back-end code for their pages (e.g. ASP.NET code-behind) it is a great asset to have the capacity to analyze algorithmic complexity. Your response time (and your server load) depends on it - every ms counts.
Demi
My point is that, in the vast majority of web development work, you _aren't writing any algorithms_ but doing simple things such as iterating through collections and generating HTML. This is almost always done using libraries or language features and knowing the complexity of this is simply not necessary.
thenduks
Don't worry as you can see by the score on my respose they don't take kindly to people that don't have degrees.
Matthew Whited
Indeed Matthew. I don't have a degree, am very familiar with Big-O (from when I was doing embedded work) and currently do web development. Needless to say 'algorithm complexity' _never_ comes into play... _certainly_ not during interviews!
thenduks
The best part is becasue I don't have formal training I don't know these terms until people say them. But the best part is from the fact I have been programming since I was 5 I have dealt with more than my fair share of the problems that these magical names point too. But I guess becasue I just naturally optimize my code and don't have to worry about calculating the complexity I must be wrong.
Matthew Whited
A: 

Well i don't have a degree in CS and i'm self taught on what little i do know but even i have started to try to learn bubble sort amoungst others, just for the sheer fact that if it is widespread like it is there must be a reason to know it.

Marc Towler
Bubble sort is the "naive" implementation of sorting. It's basically the first algorithm you would invent when you decide you need to sort some data.
dss539
And there's nothing wrong with bubble sort, in it's place (which, granted, is pretty limited) If you don't have access to a library, have to roll your own, and clarity and correctness are more important than speed because you're only sorting a maximum of, say 30 values, then bubblesort could be just fine. But in the great majority of cases, you'll want to know how to write (or access from a library) more efficent sorting algorithms.
Beska
+5  A: 

First, ~10% of interviewees in a phone screening having any clue at all seems about right to me. In my experience, it's always the case that 80-90% of applicants for development jobs really shouldn't even be in the business. That's why you screen.

On the other hand, be wary of focusing on things like bubble sort. Yes, back when I learned CS it's the first sort we learned, and was the base comparison for other algorithms, but if you think about it there's no good reason for this, and it's absolutely possible for a very good algorithm course to gloss over bubble sort and start with selection sort or something. And I'd be very wary of asking directly "what's the big O of ...", that's the kind of question where someone could easily just draw a blank during an interview.

On the other hand, developers should be able talk intelligently about Big O notation and algorithm speed generally. But I think you'd be better off asking general questions about it, rather than asking about specific (largely archaic) algorithms.

tnyfst
+2  A: 

@Malfist: I agree. Give it a few years after you graduate and you will forget most of factual stuff, if you don't use it in practice. What will be left, is the basic remembrance what it was and from what opera, so that you know where to listen to it again whenever you need it. I learned and tried many kinds of algorithms as a student, but I do not even remember their names today.

Like we were taught in university: A professional is not the one who knows everything, but he who knows where to find the information he needs.

User
+3  A: 

I don't have a CS degree, but I've tried to keep up, and Big-O is a concept that I've come across constantly. If you don't know what this is and you don't have a CS degree then you either don't try to improve or all of your learning is of the form "learn widget Y with framework X" and you're not going to be very good at conceptualizing. If you don't know big-O and have a CS degree, ... well, I can't really figure out what you were doing, but it wouldn't fill me with confidence. It's chapter 1 in CLRS, it's a pretty intuitive concept.

I've been on lots of interviews, in my experience interviews that don't ask tough questions (and this is nowhere near a tough questions) mean a place where most of the coders are ... er... not so good. You don't want to be that place, and I can't imagine that you want people who aren't aware of the consequences of their decisions ("I'll just iterate through this array every time I want to find somehing...").

As a point of reference, in my (sadly unsuccessful) google interview, this kind of question would (rightly) barely rate for the phone screen.

Steve B.
Exactly. This is the sort of basic knowledge that should be just as (if not more) important as "the computer must be on for stuff you type to show up on the screen". Not knowing that the computer must be on can be wasteful of your time, but a poor understanding of Big O can be downright DESTRUCTIVE.
McWafflestix
+48  A: 

Here's my take on it.

Background Knowledge vs. Detail Knowledge

Knowing the Big-O of bubble sort, or any other sort, is a piece of "detail knowledge". Knowing what Big-O is would be "background knowledge".

Someone who is good at their chosen field will have a good supply of "background knowledge" to draw upon. Background knowledge allows for a fundamental understanding of a problem, and how best to approach it.

Detail knowledge is much less important for the problem solving process, and more important for the implementation of the solution. Obviously, the more detail knowledge you have, the faster you can work, but knowing details without background can cause someone to take an entirely incorrect approach. Knowing background without details is much preferable, as details are usually trivial to learn and implement.

How the Programmer fits the Job

I am ten years out of university. You can bet your bottom dollar that I have forgotten the big O of almost every algorithm I learned in CS 100. When was the last time I implemented a custom sort algorithm in ten years of web programming? Never. And unless you're implementing a bunch of custom sort algorithms specifically, you shouldn't put much weight on whether someone knows the "detail knowledge" behind it, as it's something they or you will probably never need to write.

On the other hand, could I tell you what Big O was? Most definitely. Could I research and come up with sorting alorgithms with a task-suitable Big O very quickly? Most definitely. Could I compare two web application process stacks and decide which one had the better Big O? Yes. Background knowledge beats out detail knowledge hands down here.

As long as a programmer (or anyone in any field) understands the fundamentals on a solid level (background knowledge), they will have the potential to be a good programmer. If they have acquired a lot of detail knowledge as well, through study or experience, then they can probably program faster, and maybe more accurately, as well. You can be a good programmer with no detail knowledge and lots of background knowledge, but the likelihood of being a good programmer with lots of detail knowledge and no background knowledge is much, much lower.

Tailor your Interview

Your interview should weigh all this accordingly to decide which candidate would be the best fit. For your particular case, I would make sure to hire someone who understood what Big-O was, as obviously they have more solid background knowledge to draw on. But dismissing them because they don't know the Big-O of bubble sort is silly, unless the job specifically deals with bubble sort in a serious capacity.

I could come up with a hundred similar detail-oriented questions to confound an interview candidate, and I guarantee that you or anyone wouldn't be able to answer all, or even most of them. When was the last time you wrote a database indexing algorithm from scratch, or even a B-tree, or took something to Backus-Naur normalized form (CS 230 in my day)? How about your own TCP/IP layer protocol (SEng 450 in my day)?

I can tell you what these things are and how to do them, but you tend to forget details after they become unimportant. However, I could find them and do them quickly if I had too. Make sure your interview weighs what background knowledge is important for the position as well as what detail knowledge is important.

zombat
Asking the Big Oh of bubble sort is a phone-screen shortcut to see if the person understand algorithmic complexity. It would take much longer to screen each candidate if you launch a lengthy discussion of complexity. Save that for the in-person interview. Since bubble sort is the canonical example of sorting complexity, it's likely that someone would either recall the complexity directly, or remember the algorithm and derive the complexity in mere moments. Your answer is right, but I'm not sure you should devote that much time to the phone screen.
dss539
I respectfully, but completely, disagree. A much better question is "Describe what Big-O notation means.". To use the classic car analogy, it would be like interviewing a mechanic and asking "How does the transmission on a 1994 Jeep Wrangler work?" as opposed to "How does a standard transmission work?". All you need is a brief answer that indicates the person understands the overall concept.
zombat
A lot of this discussion is kind of funny to me when I think back on our HR person who was in charge, for some unknown and unknowable reason, for doing phone screenings for developers. He made sure, for example that they had programmed in "c pound" before.
Beska
@Beska - it's funny because it's true. Especially in larger companies, you get situations where people doing an interview have no idea what skills are required for the position, or what the skills even are. In these situations, you will invariably end up with someone who can "sound smart" (ie. applicable detail knowledge) bluffing their way through.
zombat
@zombat This isn't an interview, it's a phone screen. It's more along the lines of "how many spark plugs does a V8 have".
Adam Jaskiewicz
Also, I think I would voice my concerns about being interviewed by someone who doesn't know the answers to their own questions if I were asked about "C-pound" in an interview (or even a phone-screen, for that matter).
Adam Jaskiewicz
@zombat - n^2 is a quicker answer. As I said, you are completely right that the concept orders of magnitude more important than the instance knowledge, but if you are interviewing 200 candidates that will take much longer. In short, the Big Oh of phone screens in n. The screen will filter a lot out, perhaps only leaving log n. So I would apply the longer question to the log n applicants instead of all n of them. So, to reiterate. You are correct, but it's a time thing. If they only have 5 phone screens to do, then sure why not.
dss539
You guys are nitpicking. It says in the original question that not only was he asking them the Big O, but also to things like describing how bubble sort works. That's a much bigger time waster than describing Big O in general, which shouldn't take more than a few seconds. You run the risk of losing quality candidates with poor questions, and that will cost you a *lot* more in the long run.
zombat
If anything, you should filter out your phone candidates with fundamental background questions, so you don't waste everyone's time having them come in to interview. The interview is where you should get down to specifics that will apply to the job so you can analyze their skills in a more personal manner.
zombat
The first sentence says it all. Why in the world would ANYONE need to know, off the top of their head, the Big O of bubble sort?
Daniel Straight
A: 

WHere are these guys getting their masters degrees?

Is this like the spam emails I get all the time, send us some cash and we'll send you a degree?

I would think that anyone taking a basic, undergraduate class in numerical methods would have learned this.

JonnyBoats
They should have, and that's why I would suspect that these people are padding their resumes by lying about having a degree.
McWafflestix
A: 

One more semester to go and I will be graduating with a degree in Software Engineering: Computer Programming, and Big O was required in the Data Structures classes. Those classes were only required for programmers though, not for web programming or web development, as such I am not surprised that people coming out of school with a "CS" degree for web development have not learned about Big O notation.

X-Istence
I don't know that there IS a CS degree for "Web Development". maybe you could get such a thing at a community college; but I don't know of any university which grants a degree in Computer Science For Web Development. (Of course, I wouldn't go to a doctor with a M.D in Writing Prescriptions (not that I haven't gone to a few who acted like they had that degree).)
McWafflestix
@McWafflestix: http://uat.edu/majors/web_and_social_media_technologies.aspx. The school I go to ... Bachelor of Science is what it falls under, same as the Sofware Engineering Degree which is also considered CS.
X-Istence
That looks like they're calling it a BS in "Web and Social Media". Is it actually considered a concentration in "Computer Science"? Because I don't see any CS courses in that course list.
Adam Jaskiewicz
@Adam: As far as I am aware it was a computer science concentration, they may have changed it recently. It used to be known as Web Programming rather than Web and Social Media.
X-Istence
+4  A: 

I would be concerned if they didn't recognize big-O notation as a way of speaking about algorithm complexity.

I would not be worried if they couldn't remember big-O of a bubble sort off the top of their head. I would be worried if they couldn't derive it.

Here's the reason even web programmers need to big-O: they need to recognize when something is no longer linear. They also need to understand that processes can be non-linear. Basically, they need to be able to see how long something is taking on different kinds of input, or how long something is taking over time, and have the intuition "oh, I bet this process is O(n2)" or "O(n4)" or "O(2n)", and not the much less helpful thought "gee, this is slow."

As an example of where web programmers get tied up in algorithmic complexity, allow me to point to regular expressions. It is very, very easy to create a regex that isn't O(n) in its input size. When that happens and you hit general performance problems on large input, you need to have the conceptual tools to recognize what's going on.

Daniel Martin
I knew the concept behind big O a year or so before I encountered the notation. I used to write x^2 or log x or x log x describing algorithms before then.
Joshua
+6  A: 

I don't see how someone memorizing bubble sort, insertion sort, or any other sort and their corresponding time complexity implies that they know much, or even anything, about computer science nor would make them an even-close-to-competent programmer.

Personally, I think that the kind of person who would care about the underlying theory is going to be a better programmer.

This is important. So how do you test to find out if someone cares? Why not give them a problem, two fairly simple algorithms that accomplish the same thing in different time complexities, and then ask them to describe the differences and why one might be better than the other. And, if you can, make it a problem applicable to your domain area. If they can tell you why one of the two algorithms is better, and demonstrate the ability to figure it out, then they are likely stronger in this regard.

For your domain, I would want to know if they could recognize time complexity related problems more than I would care about Big-O notation. Would they simplify a for loop that made calls to a database to a single SQL query if the opportunity presented itself?

Kaleb Pederson
A: 

When you want someone to design your home, the person with the best credentials typically is the person with foundational (and hopefully experiential) architectural knowledge.

When you need surgery, the person with the best credentials typically is the person with foundational (and very hopefully experiential) medical knowledge.

Granted, people can learn things from books and people can learn things from sites like Wikipedia. But when one gets down to the brass tacks, so to speak, the engineer or technician who has the deepest knowledge of their field is likely the most capable and quite possibly the one to bring the best results.

Software Engineering is a profession, and like all technical professions benefits from foundational knowledge of the field. If interviewees didn't remember the term Big-O, I would be irked (have they ever heard of it? why not?). If they couldn't analyze an algorithm and at least give a very reasonable assessment of the worst run-time (average preferable), the interview would be done early. I would no more trust the applicant to build complex code than I would trust an average teenager to design and wire my home electrical system.

To reiterate: having a sense of algorithmic complexity is foundational. One may be able to learn how to assess complexity by reading up on it "when one needs it", but the hard fact is that if one is writing code, one needs to be aware of the ramifications of one's choices - the good software engineer should have this knowledge (and this tool) from square 1.

Demi
+2  A: 

JUst because somebody dosn't know/remember big-O or how a bubble sort works, dosn't mean they will not be a good developer. Most people don't know how a keyboard works, but is that as important as knowing how to use one? Seems like a petty reason to pass somebody up for consideration.

Tester101
I beg to differ. If someone does not have at least an intuitive understanding of complexity, then the code that they write will not scale. From my first job, I recall a couple of occasions where programmers who didn't understand complexity wrote mind-numbingly stupid algorithms that wasted vast amounts of (expensive) mainframe CPU time.
Stephen C
+1  A: 

If you phrased it as "big O", i can easily see not knowing what it is.

When i studied, it was called order, and written as O( n^2) but it was never ever referred to as "big Oh".

Maybe there is such an expression in some other industry. ;)
User
+1  A: 

I dedicate this post for all of You who say it doesn't really matter for web frontend coders.

In the interview for a python coder:

  • how would You get the last element from the list?
  • that's easy! my_list.reverse() ; print my_list[0]
Reef
I think that person had more serious issues than a handle on algorithm complexity.
TURBOxSPOOL
That's kind of a different issue than what the question was asking, but funny nonetheless :D
womp
+1  A: 

You should care because it's not that hard. And if they've (allegedly) done a computer science major and don't know it, there's something wrong (with them).

cletus
A: 

Yes, but just the basics:

  • O(n) to search for an item in an unsorted array
  • O(log n) to search for an item in a sorted collection (binary-search tree, SortedDictionary, etc)
  • Expected O(1) to access items in a hashtable
  • O(n log n) to sort collections
MrDatabase
A: 

They should know what Big O means, but IMO, a good understanding of design patterns is more valuable.

Gromer
A: 

Should they know what BigO is and how to determine it? Absolutely. Should BigO have to be remembered for bubblesort? I don't think so. It's not all that common that anyone will be writing their own sorts...most of the collections have pretty solid sorts and even if they have to they could google the bigO of most known sort schemes.

It's more important that they understand the concepts of algorithm analysis for their own algorithms...not remembering arbitrary facts about bubblesort. Seeing average case and worst case for your own computationally intensive code is more important.

A: 

I've been programming successful commercial apps for 20 years, have interviewed many candidates for companies I've worked for, and I've never asked about Big-O. I'm embarrassed to say that I actually had to use Wikipedia to remind myself how Big-O notation worked, although I did remember the general concept from my first year CS course. I asked myself how I could have forgotten something so fundamental, and then realized that, aside from lower-level systems-type programming, there are only really two orders I care about when reviewing my average LOB programmer's code: O(too slow) and O(fast enough).

Wayne