February 02, 2025
The 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 insertion, and can be flattened into an equivalent sorted array,
so it has the relevant properties of an array during insertion sort. Unlike an
array, however, it has O(logn)O(\log n)O(logn) lookup complexity to find the insertion
point, and worst case O(logn)O(\log n)O(logn) complexity to rebalance the tree after
insertion, as opposed to O(n)O(n)O(n) complexity for a flat array.
January 31, 2025
The 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.
January 25, 2025
The 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 trie.
January 25, 2025
The challenge is to find the number of possible walls of width www and
height hhh 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.
January 23, 2025
This 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 both quite easy to handle if we use Dijkstra’s algorithm.