With technology moving faster than ever, I believe we need to cultivate more acceptability for simply using existing stuff

while rudimentarily understanding how it works, obviously ...

Or maybe you lust for a career in the gaming industry, which yes have their own engines ready to use, but you might have to do optimisations of your own. Or work with SOC and embedded systems. Maybe you would like to work with Linux core tools one day.

I think there is a broader world than that of the common jobs in the silicon valley.

Almost none of that is stuff I use on a daily basis and I've frankly forgotten most of it. And I work with successful programmers that skipped college entirely and never learned any of that. I don't find myself building compilers that often and while I enjoy the functional programming renaissance in languages in the last ten or so years, I had to relearn a lot of that stuff as I hadn't touched any of it in 20 years. A lot of the expert systems and Bayesian belief network stuff in the nineties got obsoleted by machine learning later.

While I've forgotten most of that stuff, I remember enough to get back into it when I need to. Which has happened a couple of times. Mostly, I just hit Wikipedia, read up on a bunch of things and then figure out what tools and libraries are appropriate.

And there are a bunch of things that I was taught that didn't click until I learned it properly by doing it in practice. Like dealing with concurrency. Which, as it turns out is less about formal methods (and temporal logic, which was a pet topic of my teacher) and more about engineering practical solutions to very real problems which my teacher had never experienced because he was an academic. I knew all the lingo but hadn't really experienced any of the pain. Nothing like debugging a misbehaving system where you can see all this play out in real life.

I never cease to be amazed by the amount of stuff I have to learn on new projects and have dealt with some amazingly niche stuff over the years. That's stuff from computer science, medical stuff, material science, legal stuff, and more. If you do software for companies working in some niche field, you end up absorbing a lot of knowledge about what they do, how they do it, and why.

I hope no one laughs -- it's not a joke.

I was told early on at uni that you're going to forget almost everything here or things change and you won't need this info

but hopefuly you'll develop an engineering mindset

Traditionally the masters degree is where you start specializing and becoming an industry expert.

The undergrad degree is intended to teach you how to learn and then how to learn within your specific specialization without becoming an expert in the specialization.

I also noticed this and questioned what I have to offer more. But once and a while there is this complex problem, and then you can see that some developers run into their limits, while others (mostly university degrees) can go further.

I'd hope it was the opposite: common jobs outside the valley ought to be all the plumbing of comesouttas into goesintos, and the valley ought to be concentrating on the fewer problems where deeper skills yield much higher values?

(I left the valley in the 1980s, so this may be just rose-coloured nostalgia)

Did you implement your own Set type and primitive functions?

Thankfully a lot of that stuff is in nodejs now, and there's a commitment to maintain parity with Web APIs which also helps, but there's still a lot of half-done work and path-dependencies on outside libs.

My usual example of something missing from the standard library is

    func max(a, b int) int {
      if a > b {
        return a
      } else {
        return b
      }
    }

Like the new slices package, meant to do common operations on slices, that is brand new on 1.21.

I wouldn't be surprised to see more and more new additions leveraging generics in next releases.

Neither of them use dummy values as you suggest. They have similar implementations (both are AVL trees) but sets really do contain only one value while maps contain two. I would be surprised if many other languages did as you suggest.

EDIT : and Rust: https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.ht... (this is used by the default implementation of HashSet).

The set implementation points out some of the differences, at https://github.com/python/cpython/blob/main/Objects/setobjec... :

   Unlike the dictionary implementation, the lookkey function can return
   NULL if the rich comparison returns an error.

   Use cases for sets differ considerably from dictionaries where looked-up
   keys are more likely to be present.  In contrast, sets are primarily
   about membership testing where the presence of an element is not known in
   advance.  Accordingly, the set implementation needs to optimize for both
   the found and not-found case.

A good engineer must understand the hardware, the data, and the algorithm.

If you live in a world where a line of code assigns a variable or dereferences a pointer or emits adds and imuls, you can probably get what's happening just looking at the code.

If each line of code manipulates complex structures, sends queries to the database, interfaces with the network etc, you'd better know what you're doing and you'd better know it well.

It also depends on your field of work.

“Knowing” of them would tell one where to look and how to think.

Writing software is much easier when you know that things like B-Trees exist or how breadth-first search works. How do you know where to find things like this in your library if you don't even know they exist?

And, when you need to optimize or handle special cases on critical paths, you may end up needing to implement these algorithms yourself.

Case in point: I once lead development of a major competitor to Dropbox. We couldn't use "off the shelf" queues and lists to manage upload and downloads, because there were too many special cases. I also had to implement my own immutable collections (until a library was released and we switched to it.)

But otherwise, 99% of the product used off-the-shelf list and queues under the hood.

Of course one should not reinvent the wheels. But understanding tricks and idioms used in these algorithms are useful elsewhere and in general helps you grow as a programmer.

As an aside, for non-programming mental models I found the Personal MBA by Josh Kaufman to be fantastic. Its title and marketing cheapen it a bit but the content is on point, extracting the best reusable patterns from graduate business education.

There are some good self-taught devs and a select few bootcamp-educated devs in the same sense that there are a few unwarped 2x4s available at your local Home Depot - the fact that the exceptions exist does not disprove that the majority are not worth your time.

But after reading the table of contents here, I'm thoroughly convinced that this book is not about that. About halfway through, I gave up trying to count the algorithms it was covering because it seems like it randomly decides it wants to be an AI textbook instead. Its focus on AI is weird; if you've got time for Naïve Bayes classifiers, where's convex hull? Where's simplex [1]? Fast Fourier Transform? Union-find? Constraint satisfaction? Hell, where's quicksort?

Another harbinger of quality: there's a section on "Choosing between MD5 and SHA". If you have an entire section on that in a book published in 2023, something is wrong. Then again, an algorithms book needing to have a section on that topic is itself... o_O-worthy.

[1] Okay, there's a section on linear programming. A section. Which, based on the section headings, seems entirely focused on "here's how to use a linear programming solver" and not anything on the actual algorithm itself. My algorithms textbook has an entire chapter on simplex, with instructions on how to code the algorithm itself.

I haven't read it myself, but Algorithm Design Manual (https://www.amazon.com/Algorithm-Design-Manual-Computer-Scie...) also tends to rank high on recommendation lists, and from looking at its table of contents, it does complement CLRS nicely--there looks to be a better selection of things like constraint satisfication or computational geometry.

That said, this particular book is an expensive way to line your birdcage, and it should be an O(1) decision to reject it. Shame that ORA put their name on this trash.

It's trivia, and more often than not it's completely useless trivia.

Big-O complexity refers to asymptotic complexity which is only theoretically met with very large datasets which are already in the realm of a RDBMS. Until that point, performance is far more sensitive to cache locality and other implementation details. This means that all those trivia numbers don't even match with real world data you get from your own performance tests.

So what's the point of wasting time memorizing trivia that doesn't even match real-world observations?

For all the other data structure operations it up. But there’s a lot more to data structures than big-O and implementing it yourself is one way to expose yourself to those details (eg cache locality or other things). Crossing abstraction layers requires an understanding of what’s above and below an abstraction. It’s not trivial to have that knowledge and know how to apply it effectively.

It also is not relegated to RDBMS. It can come up when dealing with as few as 1M elements. For example, look up the Rockstar long loading time bug that applied an n^2 algorithm accidentally to something like a few thousand or hundred thousand elements.

But you seem to be pretty into the ignorance is a virtue mantra so not sure there’s any point in engaging further.

(The other is adding network requests, eg database calls, in loops)

Big-o notation can also describe space complexity which is a property of the data structure itself and not the algorithmic operations. What I said was a catch all.

As for trivia, it 100% is when literally ever good data structure documentation says the big-o of that operation (+ a lot more details that can sometimes be more relevant). It’s trivia worth knowing for arrays and hash tables but not worth remembering for the various trees because there’s so many of them and they’re used so infrequently (+ implementation decisions can matter which is why reading docs is more important).

I don’t know what problem domains you are working with but algorithmic complexity is not the most common slow code reason I’ve seen new devs run across because the sane generic defaults tend to be relied on for that exact reason (+ code review by someone with experience will catch obvious problems)

The addendum about network calls in a loop makes it sound like his domain uses some kind of SDK with a bad API design. There are some notorious examples which are known to fool new and uninitiated developers who haven't read the fine print into writing code that looks perfectly reasonable on the surface, but does dumb things under the hood.

My experience with new devs is more towards obsessive concern with respect to time complexity, at least where isn't hidden behind a bad API design, fearing an algorithm with high complexity that when measured under its practical use would be just fine. It can be difficult for new (and even old) developers to grasp just how fast computers actually are.

Said database APIs are typically not unreasonable when the database is running in the same memory space as the application, where latency is unnoticeable, as historically was the case when a lot of these APIs were designed. But, as you know, the model breaks as soon as you find yourself in a high latency environment, like over a network.

So then you get some weird bulk operators bolted onto the system to work around the latency issue, but they don't fit the mental model of the rest of the API designed around the idea of single unit operations. Save catching it in the fine print, they go unnoticed. Indeed, the naive programmer who hasn't yet been burned will not be able to fathom that another developer could design such a bad API and will put faith in the idea that the underlying system will somehow automatically mitigate the problem you describe. And in small scale testing it works fine, so there is no reason to doubt that notion. That is, until it is too late...

The experienced developer has learned to stop trusting other developers and bring a heavy skepticism when using another's API. This is a blessing as it means they (usually) stop making those kinds of mistakes when they encounter a bad API, but it is curse as it means they see no reason to fix the problem. "Why don't the junior devs just know better?!" they say. And so, the cycle repeats.

I’ve worked and led teams in multiple problem domains. Devs not understanding how to optimize to avoid slow time complexity is definitely one of the first nuts you have to crack in a new engineer.

Again, not saying it’s irrelevant and it might be highly relevant in some problem domains. But in general big-O of the common data structures should be memorized with the rest being trivia that should be accessible in the documentation for the data structure (or by looking at the implementation and doing it yourself).

I take it that you didn't bother to read the thread you are replying to? There is no reason why you need to have the time complexity of any given function memorized should someone ask. You can – better yet, they can – read the documentation or, failing that, read the code to answer the question. If you happen to have it on hand, that's great and all, but it is only necessary if the asking party see themselves as a trivia master.

> Devs not understanding how to optimize to avoid slow time complexity is definitely one of the first nuts you have to crack in a new engineer.

You never really crack that nut, no matter how experienced, as many problems have no known faster time complexity solution to provide the 'how'. To begin to try to crack that nut you're going to down the road of researcher, not writing day-to-day software, and even then your research is not guaranteed to yield results.

Whether or not developers choose to observe time complexity is orthogonal.

But, okay, let's entertain your random tangent. Such a request is emblematic of junior managers/junior manager hopefuls misguidedly trying to wedge their knowledge into the function of the operation. In reality, you don't want to have to build a team that requires discussion about such matters. You need to define clear performance requirements upfront and let the benchmarks speak for themselves. Even if a function is O(N!), but measures successfully within the needs of the application, good enough.

It is especially important to encode these requirements in benchmarks as it documents for future developers the same requirements, and ensures they stay within them as code gets modified. The reality is that you won't be around forever. Keeping a team that relies on you to ask such questions is a failing on you.

But let's accept, for the sake of discussion, that you have failed your team. One still does not need to remember that kind of information. The function they wrote contains what they need to know, and they can consult the function to ascertain that information as needed – just as you could all by yourself in this scenario. If you like keeping such trivia in active memory, good on ya, but it is never necessary.

Whether this is truly fun I guess depends on where you are on the developer spectrum. I’d much rather develop low level libraries than app code so any chance I get is just a great opportunity to dig into the low level stuff.

At this point, I can take a look at the rest of the code and see if there's some specific reason a linked list was chosen, or if it was just that the developer didn't put much thought into it. If there is a reason (order matters, etc), I can consider what other structures might _also_ suit that need, but also give faster lookups. And, because I know of a variety of data structures, how they're implemented, and what their characteristics are; coming up with some initial choices (or starting points) happens fairly rapidly.

So yes, I could get all this done without knowing all that information. But it happens a LOT faster because I know it. I notice the issue faster. I have some starting points for options faster. Etc.

Not having that information would not prevent me from doing my job. But having that information makes me _better_ at my job. Faster, more efficient, safer, etc.

Now: the way I approach an example like this is similar to what you do, but the difference is that I'm merely aware there's a bunch of different containers out there which behave in different ways wrt lookup/add/remove/... and for the vast majority of them I have no clue about the implementation. I don't need such implementation knowledge to realize that another container might be the trick here. I also don't really need that knowledge to decide which container that eventually might be, nor to come to conlusions fast (since you're stressing that): that's a couple of minutes to lookup moreover the final decision stage will be through performance testing anyway, because measuring under actual usage is the only way I'll ever be convinced one is effectively better than the other. That's usually what is going to take time, not picking one out of x. In the extreme it might even be so that I'd first need to write a wrapper to then have a configurable container type just to be able to have people test it under different workload types, etc.

Obviously I've been through this a couple of times and by doing so did become aware of main traits of various containers/algorithms/... and yes that will be somewhat faster in the decision process. Likewise there have been certain domains in which I did dig down all the way to the very bottom and obviously having to sort out problems in that domain will be faster for me. But in the end: for me personally 'x algorithms programmers should know' is useless. Job-dependent perhaps, on the other hand I've seen enough people struggle to come up with actual and practically useful software aspects exactly because they kept on getting lost in implementation details.

I guess for me, it boils down to something like "Given a software developer A, adding more experience to them will generally make then a _better_ software developer; and most of that is the knowledge they gained in that experience". Knowledge makes one a better software developer. And knowing more algorithms and data structures is one form that knowledge can take.

- Take a quick look at the symptoms and code and see if it's obvious

- Take a look at the jstacks and see if there's anything that stands out (lots of code stuck in the same place)

- Take a more thorough look at the code to see if anything stands out

- See if I can reproduce the issue locally

- From here it various wildly

I rarely run a profiler just because it's difficult to put it into place in a production environment (which is generally the only place these issue come into play unless you set up the conditions artificially on a lower environment). That's not to say never; I just try to identify the issue other ways first.

To keep things more substantial, consider facing issues storing data at your company. Maybe the nature of your data flow causes constant slowness, because your B-Tree indices are being constantly rebalanced on writes. You knew this because you understand how B-Trees work and you also know LSM trees might be a better data structure for your needs.

And so what I mean is that understanding the big blocks you use in high level often requires understanding data structures and algorithms, even though you don’t need to implement them

Think about ECS in games - that requires a knowledge of data structure that transcends big-O trait comparison to exploit CPU architecture for drastically better efficiency.

You might ignore memory allocations but the under the hood allocations can be important in some cases to make sure they play friendly. Or understanding cache impact and why using a linked list may not be a great idea. Or when sorting+searching may make more sense than just searching.

The more you know the better able you are to make effective decisions and people who work strictly in abstractions tend to be limited in their ability to solve problems that cross abstractions.

And then there’s also some algorithms, like for example topological sorting, that are typically implemented as part of application-specific code, not by use of an existing stock implementation. When you know nothing about implementations, you might not notice that the code you’re writing happens to actually be an instance of a well-known algorithm or data structure.

It’s like the Microsoft Word problem. 10% of functionality is used by everyone (eg saving a file, opening a file, changing the font). Those are baseline “everyone should know this”. The remaining 90% is still valuable and used by distinct subsets of customers. If Microsoft started deprecating the long tail of features without careful cohort analysis they’d start losing swathes of customers.

So for the most common operations of the most common structures I’d expect memorization of complexities just because of repetition of use (or deriving/guessing it from first principles cause it’s easy for the most common ones). But there’s much more traits and it would be important to understand that (eg what are the primary drivers of CPU time when accessing a hash map? An array? A linked list?).

In many cases it will be impossible for you to write certain parts of code, or you will end up mashing random libraries together, ending up with a program that works 1000x too slow, instead of just writing a few lines of code that solves the issue.

This is especially true for graphs/BFS/DFS and binary trees/search algorithms.

Also, without training your understanding of basic algorithms, you may be unable to write a lots of code that goes beyond wrapping over basic libraries. Not to mention being able to write the libraries themselves.

I would personally say there is definitely no answer to "what should all programmers know" other than at least one programming language along with its associated tooling and enough about a platform software can run on to deploy it. Beyond that, across the full spectrum of software lifecycle careers, I'd say we've started converging on somewhat of a hodgepodge depending on role and where the standards are coming from. IT technician type careers have various certifications coming from platform providers like Cisco, Redhat, and Microsoft, and industry groups like CompTIA. Corporate security gets things like CISSP. If you go to a university, majors in computer science will give you what we expect academics in the subject to know before they can run labs or teach, and software engineering majors some idea what we might expect team leaders in large software organizations to know about how more general engineering principles and practices get applied specifically to software. These tend to have a lot of commonality in terms of at least being familiar with the basics of operating systems and networking, information security, discrete math, data structures and algorithms, programming language paradigms and constructs, possibly some bit of how compilers and maybe processors work.

Then you get what large and well-known employers expect implicitly from their interview and promotion processes. This seems to have also converged largely on at least including basic common programming language constructs, data structures and algorithms, and possibly some minutiae related to specific languages, toolchains, platforms, ecosystems, and possibly larger principles related to things like distributed systems, databases, how the Internet and web work, depending on the nature of the major product lines.

No single person needs to know all of that, but if you do, you're probably reasonably well-prepared to understand the hows and whys of any well-known or largely-used software system. It definitely doesn't mean your daily life as a developer will ever involve directly using that knowledge any more than a practicing psychiatrist remembers and can recite the exact details of the Krebs cycle. But having to learn it still might help guard a bit against susceptibility to bullshit quackery from drugmakers trying to tell them a miracle cure can do something that is metabolically impossible.

Because:

1: Sometimes you need to choose the algorithm, even if it's implemented for you. (Many languages provide many different kinds of collection types, varying on some small details that appear unimportant, until they are very important to your specific need or use case.)

2: Sometimes knowing details of the algorithm helps you avoid edge cases and other inefficient behavior.

3: Sometimes if you know the algorithm exists, you know what kind of library to search for, instead of reinventing the wheel.

However, a small anecdote. I recently obtained my pilots license, and one of the things you'll quickly learn in aviation is that there is a massive amount of information that you are required to learn that you will almost certainly never need, except possibly for that one moment in 1000 hours of flying when something happens in the air, and you simply can't pull over to the side of the road.

Developers who have an understanding of the how -and- why when they are required to solve a problem vs just plugging a library in will have a much better career developing solutions and leading teams that do exceptional work. Back to my anecdote about aviation, understanding the "how -and- why" could mean life or death.

I don't think this logic applies to software development in general and algorithms in particular.

When you need to roll out a b-tree from scratch, just crack open a book and read up. The worst thing it can happen is that somr acceptance test fails and you roll back a change. That is hardly a life-or-death scenario.

The word "soft" in "software" has meaning.

How would you know you need to use (or implement) a B-Tree in your solution VS some other data structure?

I also don’t understand the career claim. How does that work?

The pilots that don’t remember these things when they’re needed are dead.

Will they? Or do you just like the idea of a world where that is true?

Programming is (almost) never life or death and honestly is rarely even in the same ballpark.

Most people don’t need (or want) to do exceptional work.

This is unfortunate because the tools can often be a cheat code. It's painful to see people fixate on one possible cause without going to fundamentals and making a proper assessment. These people all pass the traditional programming interview filters for algorithms.

“Reinventing wheels is how we get better wheels.” - Source Unknown

It seems having great libraries is both a blessing and a curse to software engineers. On one hand, we get to build increasingly more powerful systems with these libraries without being bogged down by re-inventing the wheels -- some of which are nearly impossible to implement anyway, such as BLAS. On the other hand, it seems a waste of time to spend years studying the fundamental algorithms and data structures -- or in a narrow view our CS background is not necessarily a moat for us nor a foundation for us to build our expertise on. Of course, a lucky or talented few can build their careers on deepening their CS background, but many of us end up spending majority of time integrating various libraries and systes.