Rantings and musings
T he challenge is essentially to figure out how inefficient it would be to insertion sort an array without actually doing an insertion sort. We can’t get around actually sorting the array, so what we need is a sort method that has equivalent behavior to an insertion sort, but is much more efficient. The simplest answer is a binary search tree. A binary search tree remains sorted after every…
T he challenge is to split a matrix into concentric rings, and rotate each ring a certain number of places to the left. To do that, all we really need to do is figure out how to look at each ring as if it were a flat array. That can be broken down into two challenges: the mathematics, and the code. The mathematics We’re given a matrix M \mathbf{M} M of width w w w and height h h h . We want to…
T he challenge is figure out whether any string in a set is a prefix of any other string, and if so, to print the first string in the set which either is the prefix of a previous string, or of which a previous string is a prefix. And, as with many other HackerRank challenges, the real challenge is to do it efficiently. Fortunately, in this case, the solution is simple: a data structure called a…
T he challenge is to find the number of possible walls of width w w w and height h h h made up of 4 different width Lego blocks, with no complete vertical breaks anywhere within. It turns out that there are actually two challenges here: one mathmatical and one technological. Let’s start with the mathematical one. The mathmatical challenge The mathmatical challenge is fairly straightforward: how do…
T his challenge boils down to a route finding problem: starting from any city with a library, what’s the least number of roads we need to travel we need to travel to get to any other city that can be reached by road. It has the minor complications that we need to group cities into clusters that are all reachable from each other, and decide where in that cluster to build libraries, but those are…
T he Array Manipulation challenge , as presented, is fairly simple: for a set of ranges and values, add each value to each element of an array that falls within its given range. The difficulty comes from the scale: if there are 1 0 6 10^6 1 0 6 ranges that each span 1 0 6 10^6 1 0 6 elements, the simplest solution requires 1,000,000,000,000 (that’s one quadrillion) additions and loop iterations.…
The key to performance is elegance, not battalions of special cases. Jon Bentley and Doug McIlroy We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Donald Knuth This is an unfinished blog post started some two-and-a-half years ago that is unlikely to ever be finished properly. So I’m publishing it as-is in case anyone finds it…
W e’ve struggled for a long time to programmatically measure the objective performance impact of add-ons on Firefox. While a perfect solution is still far off, we’ve recently started down an interesting new avenue: automatically measuring the impact of add-ons on the computer power consumption during test runs. This turns out to be a surprisingly useful proxy for performance overhead, since power…