Ask HN: How much of your time is spent on classical algorithmic problems?
Almost none of the time my team and I spend writing code is spent focussed on solving "classical algorithmic problems" - search / sort / comparison etc. It is all writing clear logic.
Our efforts are all around writing unambiguous code which does what it says on the tin (and says on the tin what it does). Code which other programmers can easily work with and code which interacts defensively with the rest of the system and only affects that which its told to.
I'm interested in how representative that is. How many of you have programming jobs which are genuinely algorithmically driven?
What fraction of your time is spent on "classical algorithmic problems"?
62 comments
[ 3.4 ms ] story [ 251 ms ] threadI entered this field (taking a significant pay cut) thinking that maybe I could put some of my algorithmic knowledge to use. Turns out 90% of my job is rote logic - rewriting process flows and the like. Nothing too smart. Really boring tedious stuff.
The 'cleverest' task I did was implementing a Kalman filter to smooth over some encoder readings. That was the most fun I had in a while.
Given three arrays of integers, determine if it is possible to take a sum of three integers, one from each array, that equals a target value (say, 0).
It is not immediately obvious, but sorting the arrays will allow you to solve the problem much faster (whether or not this is the fastest solution possible is actually an open question). This problem has connections to several computational geometry problems, and I have heard that variations of it come up in certain real-world applications.
Also, there is more to algorithms than just sorting.
For example, last year I worked on a software package which was intended to match clothing automatically to form outfits. The client was a fashion consultant; the software had to duplicate what he did in his day-to-day work, algorithmically. You won't find that one in "The Art of Computer Programming"! (Or in any library, for that matter.)
The classical problems were problems back in the day. There is no point in re-implementing them nowadays. But it is very important to know how they are implemented, and the logic behind them.
Why?
Because we are tackling much, much harder problems. Fields like data analysis, NLP, machine learning are yet to reach their potential. If we cannot master the easy classical problems, how are we expected to tackle the bigger fields? By master, I mean understand and not re-implement/re-invent the wheel every single time.
In isolation, I've had a few brief stretches where I spent some time doing low level algorithmic stuff. I wrote some sorting/searching stuff by hand once, because I was working on external files, not doing it in memory. There was, at the time, either no library that did exactly what I was trying to do, or I didn't know about it.
More recently I've done some graph theory based stuff (Floyd-Warshall algorithm for "all pairs - shortest paths"), as I was experimenting with some social network analysis stuff that I wanted to do. But even that probably won't go anywhere. As I explore the capabilities of existing off-the-shelf graph database products, I'm finding most - if not all - of what I need.. At one point I thought I might need to roll my own, but it's a burgeoning field and there are more and more OSS options popping up all the time.
My own project: At least once a week.
The most exciting stuff has been implementing things where I have been unsure if what I was trying to would be possible at all in a browser. The feeling you then get when it actually works, and you know that you've pushed a limit that you have never seen anyone do in the browser before, can' be beaten.
If you push yourself to the limit, think outside the box etc. You are going to need knowledge of algorithms.
(Everyone knows about sorting algorithms, but many algorithms are not well-known. They're almost never needed, but when they're useful, they're really useful.)
People in charge of setting those business rules also rarely know what they actually want in details. This is what is meant by the joke that writing an accounting software is order of magnitude harder than building a kernel, even if the latter is much more challenging technically speaking.
Library functions normally are to generic and therefor we end up implementing lots of different variations of fast and memory efficient searching, sorting, graph optimizing, etc.
I spend less time these days implementing algorithms. However, you need a good understanding of algorithms to decide between using ActiveRecord or a service layer. You need a good understanding of algorithms to pick between a relational DB, a key-value store, or a document store.
Maybe you aren't picking difficult enough problems if you don't have to think about this kind of stuff.
Recently, I started creating a throwaway physics/game engine for fun and it is an awesome way to learn some really cool algorithms. Also, I did a small image manipulation app that exposed me to some cool stuff as well.
As a new grad it definitely pushed me more towards game development- would you mind sharing your reasons for leaving?
It's also tough for some engineers because there's usually a very clear product vs engineering divide -- you're implementing stuff other people come up with, and when they change their minds you throw it out and do it again a different way.
That said, making games is also a ton of fun and is a great way to be exposed to a lot of interesting engineering challenges. If you like games and you can put up with the issues above, you should definitely consider it.
If this is something you're looking for, my recommendation is to look at either large companies that have large infrastructure needs (Google, Facebook, Twitter, Amazon, LinkedIn, etc.) or small infrastructure-related startups, depending on your preferred working environment. If the hard parts of your job are offloaded to the database/language runtime/middleware, look for companies that work on databases, language runtimes or middleware. And in the interview, ask them for examples of hard problems that they have solved.
Also, I have absolutely nothing against the companies that don't do this kind of work. In fact, Firebase exists so others don't have to do this kind of work. This is just an observation that occasionally, the skillset tested in these interviews is not in line with the responsibilities a successful candidate will end up having, so make sure you ask.
So, what did we get? We wanted to sort (or work with trees, etc.). We knew how to do that manually. We could write the code, but our first cut code tended to be too slow. Heap sort, etc. are really clever. Stare at the code (typically are doing an informal proof of correctness by mathematical induction based on the definition of the natural numbers) and can confirm that it sorts, and with analysis as in Knuth can confirm the running time, e.g., worst case (n)log(n). So, net, there's not much question about what it does, that it actually sorts, and how fast it is. Great -- for sorting and searching.
Do I ever do such things? Actually, early in my project I wrote a bunch of heap sort routines, polymorphic, etc. I wanted to write some 'stable' versions but didn't get around to it this time. Also can write versions that sort by 'surrogate', that is, move only pointers and not the data. For some of the details of how Microsoft's Visual Basic .NET works with strings and instances of objects, there is some question about the value of sorting by surrogate! Then with the results, can have an O(n) routine that will take the 'permutation' of the pointers and move the data. Etc. I didn't write everything I could think of in sorting, but some of what I wrote is good and used in my code. And I got some polymorphic code that is only 2-3 times slower than a non-polymorphic version. So, yes, I did some work in algorithms, even some quite old ones.
Next I needed a 'priority queue' so borrowed the heap data structure from heap sort and, presto, got a nice priority queue routine. It's in my production code.
So, yes, I worked in algorithms. And for my project, that work is crucial in the sense that without it my software wouldn't work or, if I had used code I knew about from others, not work as well.
But now there is another issue in computing and software: There are old examples; since they are more explicit, let's start with those. For a positive integer n, suppose A is an n x n matrix of real numbers and we seek x, n x 1, to solve Ax = b where b is also real numbers and n x 1.
Now we need an 'algorithm'? Not really! An 'algorithm' as in sorting is not enough! Instead we need some mathematics prior to any sense of an 'algorithm'! Usually the mathematics we use is Gauss elimination, and a good chunk of a course in linear algebra makes clear just what that is doing and why it works.
Here's much of the difference: Looking at a description of code for, say, heap sort, it's easy to see that it sorts. Looking at a description of code for Gauss elimination, it's totally obscure why it solves Ax = b, that Ax = b has none, one, or infinitely many solutions, and if infinitely many how to characterize them. Instead of just the code, just the 'algorithm' for Gauss elimination, we need the math from, say, linear algebra. Similarly for a numerical solution to an initial value problem for an ordinary differential equation.
Then more generally, for some software, it may be that some math, new or old, is crucial for knowing what the software will do, much as the linear algebra was crucial for knowing what some Gauss elimination code will do. E.g., in Gauss elimination, turns out have some choice about the 'pivot' elements. Well, typically want to select the pivot that is largest in absolute value. Why? Some math! Next, do a lot of 'inner product' arithmetic. Then want to accumulate inner products in double precision. Next, when get a solution, want to ...
Point: A claim is that if find an SSBN, then can kill it with a nuke -- likely true. Another claim is that can't find an SSBN -- not really true but close to true since a promising effort to find the SSBNs would be 'provocative' and raise alarms. Also, if find and sink one, then that's the start of nuclear war, and the other SSBNs will be free to fire. So, what is tough is to find all the SSBNs at one time and sink them all at once. But if in the special scenario, then could find and sink the SSBNs one at a time. Then how long would they last?
The Navy wanted their answer quickly, in two weeks. That was about right, since my wife already had us scheduled for a vacation cabin in Shenandoah starting the day after the due date!
So, I derived some math, wrote some software, and both the Navy and my wife got what they wanted on time!
My understanding is that my work was later sold to another group interested in US national security. I could tell you what that group was, but then I'd have to ...!
There have been other projects!
But understanding algorithms brings you to a new level and opens a wide scope of other problems you can solve by applying this knowledge.
If you are not using knowledge about algorithms in your programming job it doesn't mean such knowledge is useless. Maybe that means your problems are not hard enough for this knowledge to be applied.
The algorithmic problems I deal with are things like:
- Why the hell is this API call running O(n*m) SQL queries? Can I tweak my logic and use of the ORM get it down to O(1)? The ORM doesn't let you forget about the underlying algorithms, it just makes it easy for you to shoot yourself in the foot if you don't understand them.
- Why is my single SQL query so slow? DB optimization is very much a "classic algorithmic problem", in that you need to understand the operations the DB performs and optimization is reducing its search space / # of operations.
- We're using too many jQuery pseudoselectors like ":hidden" and they're causing framerate drop on a particular page; can we use some dynamic programming / memoization techniques to dramatically reduce use of pseudoselectors?
- We need to figure out what font size will allow a piece of text to fit within a container on a PDF, but the bounds of the font (space consumed) don't scale perfectly linearly with the font's point-size. Finding the best fit is a search problem!
- And that's not even getting into infrastructure scaling issues! Do you know why Vertica might be a better fit for your data set and end user needs than Hadoop? If you understand the difference between an ETL approach and a MapReduce approach to data analysis, you're thinking about algorithms!
I spend a meaningful amount of time on "classical algorithmic problems" while doing frontend and backend web development, even if I've never had to re-implement mergesort.
They're basic math problems.
Query takes N milliseconds which is too long, mainly consisting of z & c when I run my profiler. It does x * y = z of these things and a * b = c of these things.
As z is the biggest number, can I reduce x or y?
Basic maths.
And even the last one you're better off actually trying out the technologies to trying to armchair theorize which tech is a better fit as without reading all their code you can't really see what they're really doing compared to what they say they do. Heroku being a pertinent case in point.
Search trees, dynamic programming, and reducing an algorithm's worst-case runtime are about as "classical" as you get; that's why they're in every beginning algorithms textbook.
Oh you could just know the basics and classical algorithms and able to do a smell test of algorithmic performance.
Queueing theory turns out to be a big part of the system I'm working on, as do graph traversals. I'm not proving anything new, but I am certainly transforming known solutions to be present implicitly in the way data flows through the device (a network gateway).
I've also done work on numerical solutions, implementing various formulae the researchers have come up with, and dealing with various optimization (in the mathematical sense) problems.
Lately there has been a lot of talk on "new classic" things, applying machine learning algorithms to data sets, and finding relevant classifiers and adjustments to the ML algorithms that provide better results. Hopefully I'll get into implementing and doing real work on that soon.
I do work in academia though, in a department focused on implementing research in ways that industry can actually use it.
I once wanted to stay away from web development because I knew a lot of it would be boring stuff like learning to work around browser bugs (which change with every generation of browsers, rendering your previous learning useless), rather than the mathematical/algorithmic mind puzzles which I really enjoy. I gave in because there's so much work available (and I found some clients who pay really well).
I think having experience working on both low-level embedded software and algorithmically intensive software (natural language processing, etc) gives me some advantage as a web developer. When the need to devise an algorithm or do something else hard-core comes up (which it does from time to time), I take it on with pleasure rather than shrinking back in fear. Or if I find a bug in my platform, I can drop down into the C source, figure it out, and submit a fix to the maintainers, rather than waiting for someone else to help.