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.
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.
- 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.
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).
By my experience, some companies need a competent body in the seat ASAP, and some are looking for world-class engineers.
Think Sears vs Amazon-- which company would know what gold was if they fell into a pile of it?
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 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.
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.
But 99% of projects do not come even close to the scale where you need that.
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.
I agree that you don't need to know anything about von Neumann Architecture and the likes in order to be a Web Dev.
But I wouldn't want to hire someone who doesn't have basic knowledge about data structures and runtime complexity. It's just too easy to have something work fine in development, but choke in production due to accidentally quadratic behaviour.