Just say everything is O(2^N) and you’ll be technically correct most of the time. If the interviewer says that it’s wrong, they don’t know their fundamentals.

Honestly, the N+1 query problem with ORMs is more important for most web developers than the data structures used and their complexity.

Can you explain? I clearly forgot the fundamentals :p

(Taking a Algorithms course now, so I might get it wrong, if so, RIP to my finals in a few weeks)

I think O notation represents the upper bound, so a complexity of N can also be said as O(N^2) or O(N^3), but that isn't particularly useful.

In other words, if f(x)/g(x) < inf when x->inf, then f(x) = O(g(x)).

Then there's omega-notation (lower bound, f(x)/g(x) > 0) and theta-notation (both lower and upper bound, 0 < f(x)/g(x) < inf).

Yeah this is right. Big O can be thought of as meaning “eventually always smaller than a multiple of” so f(n) = O(g(n)) as n -> inf means that there is some N (the “eventually” part) and M (the “multiple of” part) such that, for every n > N, |f(n)| < M g(n).

I had a good chuckle at this, +1 !

I think it should depend on how much money you are intending to pay the candidate and how desperate your company is to hire.

By my experience, some companies need a competent body in the seat ASAP, and some are looking for world-class engineers.

That's true to some extent, but I am quite sure even the worldest-of-class engineers have tripped up on a question or two and went on to get a rejection. If such people truly are talented then they'll have no trouble getting hired elsewhere and the companies in question would be blissfully unaware what they missed out on.

Such companies deserve to fail if so, as the supply of such engineers is limited and allegedly they need such engineers to survive :)

Think Sears vs Amazon-- which company would know what gold was if they fell into a pile of it?

I am not sure the failure of any company has ever hinged on the hiring decisions of a few developers. If you take a look into the downfall of Sears you'll see long-term strategic missteps that aren't related to recruitment in their software engineering teams.

Also I don't think a company deserves to fail if they've got a bit too much faith in a slightly flawed recruitment process. The entire point of us sharing posts like this on here and discussing them is to learn and even help each other, isn't it?

But if they’re not competent, then you’ll be stuck debugging/rewriting 6 months of the the incompetent engineer’s work

Completely agree and have been burned this way as well. If you need engineers but cant even find competent ones (something ive seen before), then the only choice is to put them on prototype work/non-critical projects

Yeah I agree that there is no need to go overly academic in interviews. I wouldn't ask about the different O-Notations and what they mean.

But if I give a code sample that has three nested for loops over some array and doing string comparisons, the candidate should at least have a vague idea that this might be problematic and could better be solved using sets or maps.

Yeah I agree that it could be better to explore this sort of stuff by looking at actual code. To be honest though you could come at it from more of an academic angle if the candidate has a more theoretical background. It's just about how the question is presented, being flexible with the response and ready to adapt if things don't go as planned. Maybe I'm kind of derailing the topic here to grind my own axe around some people's attitude towards recruitment :D