Euler Zero - backlog

It's taking longer to document my approach to some of these early problems than to actually solve them so I'm developing quite a backlog. If I ever win the lottery (which I don't actually play^*, because...math), forget the "I'd be on a beach, or travel" BS that other people always say - I would immediately hire a tech writer.

*Full disclosure: if the potential payout gets large enough, I might occasionally buy a ticket

Simple LRU cache implementation

This originally came up as an interview question (my sabbatical is over, so...). The requirement was to implement a fixed-size LRU cache; the public interface was given as:

class LRUCache {
public:
    LRUCache(int size);
    void put(int aKey, int aValue); // cache aValue, associated with aKey
    int  get(int aKey);             // returns value associated with aKey
    // ... fill in anything else necessary
};

Obviously, for a cache implementation we want O(1) lookups, so I started with std::unordered_map as the associative container. Unfortunately, I got sidetracked with my initial choice of a backing-store container for the actual values. The "conversational chat" part of the interview went a bit long and we were on a schedule so I ran out of time. Although my solution probably would have worked, it still sucked (I would have caught that as soon as I had to fix all of my iterators, but literal pencil-and-paper is a major time sink). At the end, it was pointed out to me that a std::list would have been a more natural (and optimal) choice for the required backing storage. This is embarrassingly obvious, so naturally I had to cook up a solution when I got back home.

It only took a few minutes to throw something together, but then I had a few basic issues about the general problem. For example: the definition of get() - what if aKey is not in the cache? What should be returned? I had asked the interviewer and the answer was -1 (this is completely understandable - what else would he ask to be written in a few minutes?). I'm never a fan of magic numbers though, so at the time I just put

const int invalid_value = -1;

into the class declaration as changing the given interface didn't seem to be a choice (really: it was an interview question, not a real work problem). Nevertheless, this obviously needed to be fixed once I had liberty to change the interface definition back at the ranch.

Anyway, after cooking up a quick-and-dirty working solution I spent a little more time to tweak the public interface a bit and add some additional functionality. It's now a simple template-based generic object LRU cache implementation that uses std::unordered_map for the associative container, std::list (by default) for backing storage, iterators for results, etc. and has acceptable performance - pretty much everything you'd actually use is O(1). I didn't spend that much time on it so it could still use some work, but it's at https://github.com/frasnian/LRUCache (I did wait a week before posting it on github, so I hope they won't mind).

Again, the stable iterators for std::list are so obvious for the backing container choice that it is just embarrassing (I originally even considered a list, but for some reason I had a brain freeze and started thinking about O(n) performance for operations I wouldn't have ever used for this). I'm okay with ending my sabbatical, but the first few interviews are probably going to suck.

Euler Zero, re-revisited

It seems I was a bit optimistic about how easy it would be to create zero-runtime solutions to Project Euler problems due to the relaxations on constexpr functions introduced in C++14.

I recently picked up a problem a colleague pointed out to me last year and as it turned out to be from Project Euler, I decided to try to create a zero-runtime version after I came up with a correct solution. It is more challenging than I expected, so I may be doing the occasional Euler Zero solution after all.

Euler Zero code and wiki are now in a GitHub repository, at https://github.com/frasnian/euler-zero. Any solutions will be linked from here, but for the most part, code will be in the repository and commentary will be in the accompanying repo wiki.

Hiatus

After an extended hiatus (during which the US endured an election season from hell, Adam Goodes did in fact retire, and I took a personal sabbatical), I'm apparently starting up this blog again. Not too many people follow it anyway*, but that's really what most blogs are: random bits into a global /dev/null.

*yet :)