Usually I had funny but opposite experience when doing consulting for performance optimizations.

At some points either teams converged to people without basic knowledge of data structures or they rushed with something that works (when N in O(N) was small) then scaled up. They get used to lower performance slowly like boiled frog.

Then someone is tasked with optimization, but instead of attacking data structure at hand, usually those people tried to optimize pieces of the puzzle for smaller gain, then they ended up with small hacks to shave some execution time, with unmaintainable code which lead to serious bugs.

This is the kind of observation that should be central to CS, but isn't.

While academic algorithm astronauts write papers which include Greek math symbols and can be proven correct, most people do... something else.

Optimising the something else would be a huge benefit to the industry. But no one even looks at it. It's just a thing that happens, and there's no research into fixing it or making it better.

I feel like this is moving in the opposite direction! I think the issue is that most of the time the "something else" people write with poor algorithms is actually an application of the correct, efficient algorithms from formal papers written by academics, but they don't know it and thus don't use it.

I think the main thing we want to avoid here is situations like the following:

- interviewer asks candidate to determine the complexity of some algorithms

- candidate is nervous, has a minor brain-fart and flubs a couple of them

- interviewer evaluates candidate as lacking basic CS knowledge you learn in 1st year of any CS course

Ok in this case we're talking about big-O, but it could really be anything.

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

Not knowing how databases work is a pretty common issue I come across with colleagues. Even basic things like normal forms (which take about 5 minutes to understand), and what transactions are. I think it’s why non-RDBMS datastores are so popular, because they generally just ignore all the problems RDBMS are trying to solve, so the developer isn’t inconvenienced by thinking about them.

Non rdbms are popular because at scale everything that's nice about "classic" rdbms are what makes them ultra slow.

edit: the features I refer to are stuff like foreign keys, cascades, dynamic fields, complex joins, etc. Once your stuff is spread out you loose some of these by definition and if you're still sticking to a single DB with massive stores you're not getting much humpf out of it anymore.

I 100% agree there are way too many fools that think their DB is big and try non rdbms too early and waste too much time. But I still think their lack of recent popularity is due to their own limitations.

Not really, they remain fast enough, there’s just no easy way to scale them past a certain point. Or there wasn’t anyway, I believe with spanner and CockroachDB we’re getting pretty close.

But 99% of projects do not come even close to the scale where you need that.

There are very few RDBMS usecases where scale is a legitimate performance concern. Index scans scale to a very, very high cardinality.

There are use cases that aren’t best suited to an RDBMS at any scale, like managing a collection of denormalized documents, or a graph. But in my experience, considering these factors isn’t what’s motivating adoption of Mongo, or Dynamo. Your key lookups will always be fast (until you get a hot shard), but when you cram a highly relational set into a document db, eventually you’re forced to realize that there’s a lot of mutations and access patterns that you simply can’t implement, because you chose the wrong tool for the job.

Either that or you’ll decide that it’s a good idea to implement your own concurrency control mechanism on top of your document database. Which I’ve personally seen at least 3 people try and do.

Except they are also popular with people that are not working "at scale" where that would matter.

obligatory https://youtu.be/b2F-DItXtZs webscale database discussion