At it's simplest you have things like checking for existence using linear scans of arrays. Anyone with experience sees that as a bad thing to do because they understand that it's inefficient for any sort of sizeable array. But those who don't understand algorithms or data structures won't even know there's an issue. And that's the simplest case really.
When you have a list and you need to efficiently add and remove items from both ends - then you want some sort of double-ended queue. I know where to find the one in my std lib and I know when I need to use it - which it turns out is almost never - I thought I did the other day, then I found a simpler way, which was actually a bit disappointing :)
Then, as you say, you have things like A* or R-trees. The more of these you have an handle on - even just to know they exist, the better position you'll be in when you need them.
But I don't even think that's the most important part of knowing data structures and algorithms (and really, I'm sure none of that's news to you if you're implementing A* searching). For me it's more about understanding efficient patterns for data access. So much of the work I do is about efficiently pushing data around in different forms. Often having a core chunk of data and then a couple of different indexing structures to allow me to interrogate it depending on the info I need.
Second, you should know when to use A* or something else, the trade-offs etc.
Third, you should know how to implement A* , when needed, with reference material (you'd be surprised how many programmers can't read/understand the reference material even when its given to them, or don't know enough programming to put it in code).
Of course you could get by with never using A* or tries or whatever advanced algorithm, not even in some ready-made API form. E.g. if you just do some CRUD or some simple web programming. But for the kind of programmers we're talking here, those three are paramount.
The thing you mention, implementing it from scratch with no reference material might be impressive, but it's more of a circus act.
In my experience, knowing which prebuilt algorithms and data structures to reach for matters more than being able to implement them myself. Not saying there isn't value in learning or that it doesn't help flex the problem solving muscles, but in most software domains, I think that practically speaking there are more important skills to focus on after you've mastered the basics of time and space complexity.
Because for people working in those kinds of problems we're talking about (we started from Valve and games IIRC, but it could also be Google, Facebook engineers etc) you don't just download some off the shelf API.
You'll need to create something of your own to:
- have the whole IP
- mold it specifically to the domain logic you need
- take control of it's memory and performance characteristics based on your constraints
- implement it in the language your company uses, for which no ready made A* (or some other algorithm) is available
- you'll need to make it talk to different infrastructure, libs etc
- you might be the one writing the library API yourself
As I said, this is not about what a CRUD programmer will need. But as you can see everyday in HN, people write these and other algorithms all the time in their jobs doing more serious engineering.
No, I mean knowing what algorithms/data-structures are available, what their characteristics are, and how to tweak them. This way you can say stuff like: with those data access patterns, we'll need a B+-tree with links for concurrency, modified to not delete depleted nodes until such-and-such. Or, something like: doing that efficiently requires an optimization that's NP-hard because the problem reduces to graph partitioning, but we can use an approximate solution that should work well-enough in this case.
Its useful to have a steel beam and know how to apply it to construction. Knowing how its made and the metallurgy and how that impacts the application levels you up. Then there's a whole sea of lower level construction vocational laborers who don't know steel beams exist and they'll just bodge something together with stuff from the junk yard and when it collapses, well, there's no guarantees in life and it was cheap and the academics never know anything anyway so stop complaining, and last but not least the social butterflies who heard the Jones's next door, who are billionaires, built their wall out of recycled plastic so we'll use that to hold up the roof instead of proletarian wood or even this steel beam stuff.
I recently spent a few hours reading about and implementing A* for the NPCs in a video game I'm working on.
Are you talking about being able to write A* and other algorithms from scratch with no reference material?