There’s also two additional programming techniques you should be aware of:
* Dynamic Programming
</snip>
How often do folks here use dynamic programming techniques in their professional lives? My own niche is systems programming. Dynamic programming is an important technique, sure, but given how rarely I see it used in practice compared to, say, statistical estimation it feels very overrepresented in interviews. But, maybe that's my own niche being unusual.
An interesting point. I think most of today's systems tend to be "stateless" store state in a Database, which would make DP pretty cumbersome if not impossible to manage.
The only places were such types of processing will be required is when doing specific kind of processing, which for most scenarios you'd be better using an algorithm previously implemented on an existing library.
Most things in interviews are wildly overrepresented compared to their usage though. I haven’t done any shortest path, binary search, topological sort, or many other things in most of my time in industry. I would have a hard time remembering even one instance for many algorithms.
I don’t have a niche. I’m full stack. I do everything related to web apps and been at six companies doing that all in different fields. (Seed startups to large public companies)
Maybe if I was in computer vision then I’d use some of these algos more often. But those usually require a special masters or PhD to get an interview anyway. So, not really applicable to the overall industry tbh.
Thanks! For what it's worth, I'd say that full stack work is a specific niche in the field. It's a much different area of concern than the things I work on day to day.
It's hella common for SV though. The overwhelming majority of jobs here and startups are based around it. So, unless you're doing something close to hardware - you're likely working on a web app.
This doesn't mean you're just making pretty widgets for a browser.
Yeah, it's not commonly necessary for real world engineering, but it's certainly good to know, at least as a mental exercise. There's a nice free algorithms textbook used at UC Berkeley that covers the concept pretty well: http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-...
I usually reach for caching first because it’s more intuitive (for me and my reviewers) and because we often have well-known size bounds and relaxed enough performance requirements that make an “analytical” solution unnecessary.
Caching creates a mature product, no matter what your product roadmap says. If a rewrite is the tool of last result, caching is the second to last. Like pruning shears, once you use them, your world of options collapses considerably. All of those opportunities are gone and nature won't let you put them back.
Critically, caches are global shared state. That's why cache invalidation is the hardest thing. Global state also means people stop trying to have a data flow/architecture. None of these call trees need to advertise that they use a particular value because I can just grab it from a global if I need it. You don't know where things are actually used anymore because they all come from cache lookups, and because the lookup is so cheap (under typical system load, but catastrophic under high load), people don't even try to hold onto previously acquired data. They just fetch it again. Which is another boundary condition for cache invalidation (what if half a transaction has the old value and half the new value?)
They make flame graphs essentially useless. Sometimes immediately, or once the above starts happening. You quickly have no clear idea what the cost of anything is, because you never pay it, or if you try to pay it you end up amplifying the cost until there is no signal. Once people are promiscuously fetching from the cache, they don't even attempt to avoid duplicate lookups, so activities will end up fetching the same data 6 times. If you turn off the cache entirely for perf analysis then the cost skyrockets and the flame chart is still wrong.
You are back to dead reckoning and manually adding telemetry to potential hotspots to sort it out. This is very slow, and can be demoralizing. Quickly this becomes the fastest our app will be for a very long time.
All great points! For the type of work I'm thinking of (mostly offline data processing) I use caches in a much more limited way than you suggest. A short-lived local LRU cache on an expensive pure function over immutable data can significantly reduce our resource costs without adding significant complexity to the code. In some cases, DP would be more efficient but would require a mode of thinking and abstraction that's very different from most of our code.
