A Library of Interview Question Algorithms

I recently spent some time revising for programming interview questions, and having done all of that work I wondered what I could do with it.

The result is a git repo of interview question algorithms that I’ve structured as a somewhat tongue-in-cheek utility; the kind of utility that i’d love to be able to use in a programming interview, but the kind would probably negate the point of the interview question in the first place.

The library solves programming questions that keep popping up, whether in books or online on sites such as HackerRank. This includes solutions to the following problems:






Sorting / Search


Project Euler

As an extra bit of practice, I also created a repo of solutions to Project Euler problems. These were mostly based on the HackerRank version of the problems, which typically require the most efficient solution to the problem rather than a single solution to a given input.

Alternative GoPro File Importer

I’ve been obsessed with my GoPro ever since I bought one last year, but was always a little frustrated with the process of importing and organizing files. The result is this little side project, an application that allows you to import GoPro files with a little more control than the default application allows.

Download GoPro Organizer

More specifically, the program allows you to:

– Sort media by type so that photos, videos, and timelapses are in separate directories.
– Choose whether files are stored by date taken or in a single directory.
– Rename files to the time they were taken (and choose the time format used).
– ‘Import’ files from any directory structure, allowing you to move your existing imported GoPro files into a different format.

GoPro In Action
A gratuitous example of a photo post import.

GoPro Studio separates timelapses into different directories but doesn’t do the same for photos, which makes it more difficult to create movies when you have to sort through a set of photos.

GoPro files follow a naming convention that allows the importer to differentiate between photos and timelapses (amongst other things), but it isn’t particularly helpful when you’re browsing a directory of photos. My application allows you to rename the files as they are imported, using the time they were taken as the new name of the file.

If you’ve already imported files from your GoPro’s SD card, the organizer allows ‘imports’ from any location and directory structure (provided the file names have not been changed), making it easy to re-sort files into a different format.

This solves a problem for me, and I hope it does for you! If you like it or have thoughts about other things it can do, please message me in the comments.

Download GoPro Organizer

Switching to HTTPS with Let’s Encrypt

One of my more trivial resolutions for this year was to switch to using HTTPS with Let’s Encrypt, a free certificate authority that recently entered open beta. It ended up being extremely easy, so i’d recommend it to anyone looking to make the switch.

How To Set Up

The set-up process was fairly trivial for me, running Ubuntu 14.04 with Apache 2.4. Their set-up script requires Python 2.7 or above, which caused issues for me on another system.

The first step is to follow the initial instructions on their website, to clone the repo and run the letsencrypt command to download required dependencies:

I couldn’t use the automated apache installer with my system, but the standalone mode was just as simple.

First, you have to stop your web server, to allow them to run an automatic domain validation tool (ACME, if you’re interested). Next, run this command (changing the domain):

This took less than a minute, and my web server was up and running again. From there I updated my apache configuration, shown below:

And that’s it!


Programming Resolutions for 2016

Inspired by Matt Might and others, I’ve decided to create some resolutions for 2016. I’m going to leave out the non-technical ones though, so while ‘Stay Healthy’ is out, it doesn’t mean i’m not trying!

  1. Write more. Starting now!
  2. Get better with the command line. This is the epitome of tools that I use all the time, but nowhere near as efficiently as I should.
  3. Learn Go. Of the all the new(-ish) trendy languages, this is the one that I feel i’m missing out on the most.
  4. Read more recent research. Since finishing my PhD I haven’t kept up-to-date with the latest and greatest from the research community.
  5. Make use of my spie charts. I have a couple of ideas for the spie chart implementation i wrote last year, but haven’t done anything with them.
  6. Secure this site. Since Let’s Encrypt entered open beta, i’ve been interested in trying it out (status: achieved).

And that’s it… for now. If everything goes to plan, you should see posts coming throughout the year; if it doesn’t, damn.

Writing a Huffman Encoder with Java 8 and Dagger 2

Last year I wrote a Huffman Encoder to try out Dagger 2, and to experiment with Java 8, as we’d just started using it at work.

As a dependency injection tool, the advantage of Dagger is that it generates dependencies at compile time, meaning it doesn’t require reflection and errors should be easier to spot up-front.

In practice, I had a hard time getting it to work until I found this great post on using annotation processors in eclipse. This makes sure eclipse does all of the annotation processing that Dagger requires at compile time, though I found I had to manually build the project to get this to work (rather than relying on save-and-build).

There aren’t many component parts to the program, so Dagger doesn’t have to do much. The project is possibly most useful as a basic skeleton showing Dagger 2 working with maven and JUnit tests.

How to Balance an AVL Tree (Cheatsheet)

Struggling to remember how to balance an AVL tree? I created this cheatsheet as a study aid when I was a tutor at the University of St Andrews as a quick reference guide.


The root node is the first node above the inserted node that is unbalanced.

The child node is either the left or right child of the root node. The child node involved in rotation is the node on the path towards the recently inserted value.

Which Operations to Perform

LEFT-LEFT Heavy Tree

  • The left sub-tree of the left child grew.
  • To balance: Right rotation around the root.
A left-left heavy tree
A left-left heavy tree


  • The right sub-tree of the left child grew.
  • To balance: Left rotation around child, then right rotation around root.
Left-Right Heavy
A left-right heavy tree.


  • The right sub-tree of the right child grew.
  • To balance: Left rotation around root.
A right-right heavy tree
A right-right heavy tree


  • The left sub-tree of the right child grew.
  • To balance: right rotation around child, then  left rotation around root.
A right-left heavy tree.
A right-left heavy tree.

Rotation Algorithm

In the case of single right and left rotations the pivot is the root node.

In the case of left-right and right-left rotations the pivot is the child node for the first rotation, and the original root node for the second rotation.

Rotating Right

1. Save value of pivot.left (temp = pivot.left)

2. Set pivot.left to value of pivot.left.right

3. Set temp.right to pivot

4. Set pivot to temp

Rotating Left

1. Save value of pivot.right (temp = pivot. right)

2. Set root. right to value of pivot.right.left

3. Set temp.left to pivot

4. Set pivot to temp

Fixing Common PowerMock Problems

PowerMock is a great tool for static / final mocking, but exhibits odd behavior in some cases. This post covers three of the most common PowerMock problems I’ve encountered.

A test class annotated for PowerMock.

Intro to PowerMock

PowerMock is useful in cases that a tool like Mockito can’t handle — namely mocking final classes and static methods.

There are many reasons why you shouldn’t aspire to mocking static methods, but sometimes it can’t be avoided.

To mock with PowerMock, you have to use the @PrepareForTest annotation, which sets up the class being mocked (it dynamically loads another class to wrap it). You can also use the @PowerMockIgnore annotation to specify classes that should be ignored when the mock occurs.

This post includes some examples of PowerMock in action, which you can find here.

Common PowerMock Problems

Mocking Core Java Classes

By default, a lot of Java system classes are ignored by PowerMock, meaning you can’t mock them the way you would any other class.

To show what happens when you do this type of mock, consider this example using the java.net.NetworkInterface class.

I have one other class in the test (creatively called OtherClass), whose call takes a NetworkInterface object, calls it’s isUp() method, and returns the result:

My first test shows that the mock is created successfully by calling isUp() method from within the test method (code):

This test passes, but if you try and use this same mock in a different class, it won’t work (code):

The NetworkInterface class, as a standard Java class, is ignored by PowerMock, so the call to isUp() doesn’t result in the expected mocked call.

To fix this, you need to @PrepareForTest the class calling NetworkInterface#isUp(), OtherClassrather than the class being mocked (code):

The test now passes, and the mock is successfully executed.

@PrepareForTest disables code coverage tools for the prepared class, which is hard to fix. The only way around this problem is to not mock Java system classes, which you could do by wrapping system class and all calls to it.

OutOfMemory PermGen Errors

PowerMock seems prone to the ‘java.lang.OutOfMemoryError: PermGen space' error, because it does so much dynamic class loading. There are some useful blog posts on this (1), but they tend to be a little too optimistic about this problem being completely fixed.

There are a number of ways to fix a PermGen error:

  1. Increase your PermGen size. Since it’s only an issue with tests, this may not be such a big deal (2)
  2. Pool mocks to limit the volume of classloading (3)
  3. Avoid using mocks entirely, instead using anonymous test classes (3)

Test Class Doesn’t Run: java.lang.VerifyError

I had this issue using PowerMock in unit test classes that had a superclass.

It happens because Oracle made Java’s bytecode checking stricter in Java 7, so it can be fixed with by stopping this checking using -noverify as a JVM argument.

If you’re not the kind of person to take that as an acceptable answer (good call), I fixed this issue by updating my version of the JDK (in my case from 7_72 to 7_79). It’s not clear that one version of the JDK definitively fixed this problem (people seem to report it as being fixed before 7_72, for example), but it’s worth updating the JDK and your version of PowerMock before resorting to -noverify.

Other Resources

Continuous Integration for GitHub Java Projects

This post discusses how to setup a Java GitHub project with code coverage and continuous integration that is run automatically on each commit.

Working on the WordBrain Solver I wrote about last month, I thought it’d be interesting to set the project up to do this, and set up a few extra reporting tasks. This project manages:

  • Build. Managed by maven.
  • Code coverage. Instrumented by Jacoco.
  • Reporting. FindBugs and PMD reports.
  • Continuous Integration. Updates automatically pushed to Travis CI.
  • Code coverage reports. Published on Coveralls.

The result is a set of tags displaying the state of the project on GitHub:

Result Badges


The majority of the setup for all of these tools is in the project’s pom.xml file.

This is broken into three key sections:

  • Dependencies, which includes each of the libraries used in the project. Libraries that are only used in testing are given the test scope, meaning they are unit included in the release of the project.
  • Build, which describes where the code is located and how to build the code. This includes the plugins used to run unit tests and instrument code coverage.
  • Reporting, which includes plugins that are used to generate analysis or reports of the code. This includes the generation of JavaDoc, and plugins such as PMD and FindBugs.

Instrumenting Code Coverage

Code coverage is included in the build section of the pom. The code coverage tool i’m using, Jacoco, is executed in two phases:

The pre-unit-test phase attaches the jacoco agent to the JVM used to run the unit tests. In this execution, surefireArgLine is used to add the agent to the surefire test runner as an extra JVM parameter here.

The post-unit-test phase is run after the unit tests have completed, analyzing the jacoco output to produce a nice HTML report.
The jacoco agent is attached to the unit tests (run with surefire), by adding to the surefire argline here.

To generate code coverage results (created by default in target/jacoco-ut), run the test command:

Reporting: FindBugs and PMD

Published Results

While the code coverage tools form part of the maven build process, the maven reporting process includes plugins such as FindBugs and PMD.

In this pom, I added reporting for: JDepend, FindBugs, PMD, JavaDoc, and Surefire.

Adding them is as simple as adding the maven dependency, and running them is as simple as:

Continuous Integration: Travis CI

Travis CI Page

Travis CI is free for open source projects, so it’s a great tool to use if you have a project like this one. All it requires is a yml file specifying what the server should run (and signing up to the website):

If this file is set up correctly, you shouldn’t need anything else in your project. Travis automatically builds every time you push to your main branch.

Coverage Reporting: Coveralls

Coveralls Site

Coveralls automatically accepts coverage reports from Travis CI and displays them in nice interface.

As with Travis, it’s free for open source projects, and as with Travis, it doesn’t require much configuration.

Once you’re signed up, the only addition to the project is a maven build plugin:

Pushing updates from your local machine or another build server requires you to enter an authentication token here, but if you’re using Travis you don’t need any additional setup. The following line in the travis.yml file creates and sends the coverage report with no additional configuration:


Result Badges

The result of this configuration is a pair of badges showing the current state of the build and the code coverage.

More importantly, it sets the project up for future work with a great set of tools for monitoring the state of development.

Creating a WordBrain Solver

I became quietly obsessed with an iOS game called WordBrain over the holidays, and thought it’d be interesting to write some code to solve it’s puzzles (you can find the result here).

A basic single-word game.

The game itself is similar to a typical word search puzzle where, given a grid of letters, you have to find the words in the grid.

It differs in that words don’t have to be found in straight lines, so individual letters can be joined across diagonals, and as each word is found, it is removed from the grid and the remaining letters fall down. This means that for harder puzzles it isn’t possible to connect the letters in the last word unless you have found the preceding word(s).

Before starting, you know how long each word is and the order in which words must be found (as the 5 word puzzle below illustrates).

A more elaborate multiple-word game.


My solution started out as a simple word finder — finding all words of a certain length — but evolved into a more complete puzzle solver.

First, given a grid and a set of word lengths, the solver comprehensively scans the the grid for words matching against the first word’s length. It then recursively scans for the subsequent words, based on the updated grid (which is created by removing the preceding word(s)). This creates a set of potential solutions to the puzzle.

To speed up search, I created a trie dictionary to allow the solver to terminate when a non-english prefix is found.

Then, to narrow down the set of possible solutions, I used a corpus of English word frequencies to rank them by the most commonly used set of words. This tends to match the expected solution, because WordBrain uses fairly common words.

Finally, I created a Swing UI to make it easier to enter problems and view solutions.


The trie solution is significantly faster than the alternative, an in-memory set of words that didn’t allow early termination based on prefixes.

The solver itself could be slightly more space efficient, because it creates new a string through each recursive call rather than modifying a character array. However, as the search continues onto successive words, some of this copying is necessary (the updated grid, the words found in each solution, etc.).

The Swing UI isn’t particularly well written, but it does display everything required for a solution. First, potential solutions are shown next to the grid:

Potential Solutions
Potential Solutions

Next, for a particular solution, the highlighted word is shown in a decreasing shade to show the order in which letters must be selected:

Solution Illustration
Solution Illustration

Overall, this was a relatively interesting side-project, with a few things such as the trie and solution sorting which added a little depth to the implementation.

That said, I’d recommend completely ignoring this code and playing WordBrain unassisted. It’s a lot of fun!

Spie Charts Explained (+ Chart.JS Add-On)

I recently discovered spie charts, and thought it’d be interesting to try to create one in javascript… so here we are! This post introduces spie charts and discusses a spie chart extension I created for chart.js.

You can find the working code for the chart.js extension on GitHub.

What is a Spie Chart?

A spie chart is an overloaded version of a pie chart, where you can vary the height of each segment along with its width. This enhancement enables various things, such as the comparison of a dataset in two different states, or the addition of extra dimensions to a single dataset.

The next two sections use examples from the original paper on spie charts to illustrate these uses (though my data is totally made up).

Type A: Comparison of States

To compare a dataset in two states, the original dataset can be segmented in a regular pie chart, with the difference between this and the next state illustrated by the varying height of each segment.

Imagine government expenditure for two distinct years charted in separate pie charts. The change between the two charts is so marginal that it is difficult to determine what changed.

With a spie chart, expenditure in one year can be represented by the width (angle) of each segment in the chart, and the change in spending for the next year can represented by the height (radius) of each segment. This allows you to visualize both the relative weight of spending in each sector, and how that spending has changed over time:

In this example, some segments are broken down into multiple slices, where the outer slice illustrates how much spending has been reduced between the two reports.

Type B: Additional Dimensions

Alternatively, the height can be used to show a size relative to one value, while the width shows the same size relative to another.

In the following example (again based on one in the Feitelson paper), the spie chart conveys road casualties by age and sex. The height of each segment is used to indicate the number of casualties relative to the population size of that segment, while the width is used to indicate the proportion of casualties between age ranges (segments).

This example also shows how slices can be used to convey even more information, such as a breakdown of casualties in a segment between pedestrians, car riders, and (motor)cyclists.

The key characteristics of the spie chart in these examples are the ability to vary both the height and width of each segment, along with the ability to slice each segment into distinct sections.

Creating a Spie Chart

I am no expert with JavaScript, so creating the spie chart was an interesting process. If you want to skip that and jump straight to code, you can find it on GitHub, with examples here, and code here.

I decided to use chart.js as the basis for the chart, which proved to be a good decision, as it’s nicely written and extremely extendible.

Chart.JS Structure

Chart.js consists of a core file — named Chart.Core.js — and several others, with one for each type of chart supported. I decided to copy and extend the polar area chart, since it allows for pie-like segments that have different heights (though each segment has the same width).

Each of the chart type files has the same general structure, but i’ll discuss the Chart.PolarArea.js file here.

At the top of the file, a defaultConfig object provides defaults to be used for the chart’s display, including whether a scale is shown, whether animations are used, and the specifics of these features.

The majority of the code is contained within an extension of the Chart.Type object, which is the base class for all of the chart types. For a polar area chart, this contains an array of segments (the SegmentArc type), and set-up code for displaying a scale and tooltips.

The key functions in the PolarArea chart type are:

  • addData(), through which incoming data is passed from the calling function, and parsed into individual SegmentArc objects.
  • draw(), which is (somewhat obviously) called to draw the chart. When an animation is used for the chart, this function is called repeatedly, with the size of each segment gradually increasing as a result of a call to an easing function.

Each call to draw() adjusts the size of each segment by changing the start and end angle of the segment, and then the draw() function for each segment is called. This draw function is implemented in the Chart.Arc type in the core file and is common to pie charts and polar area charts.

Writing the Spie Chart

The basis of my spie chart is the existing polar area chart, modified to support variable width segments and slices. The Chart.Core.js file remains un-altered.

To begin, I updated the expected input format of the chart to allow for each of these changes.

The input format looked like this for a given segment:

But now looks like this:

I created a new Chart.Arc type, called SliceArc, and updated the addData() function to parse the incoming slices into this object (meaning the SegmentArc object contains many SliceArc objects).

The draw() function is significantly updated, with the main change being that each slice needs to be updated as the chart is drawn, rather than each segment (essentially, more looping).

The SegmentArc.draw() function is overridden, and now draws individual slices in a segment rather than the whole segment in one call. (I think this logic should be moved to the SliceArc call itself, which may make it possible to call the original Arc.draw() function without modifying it)

Tooltips were particuarly challenging to fix, because the existing inRange() and tooltipPosition() functions are very much designed around the location and position of the segment, and not slices. To avoid modifying the showTooltip() function (which is relatively large and in Chart.Core.js [called here]), I pass a slice object and make it look like a segment object (this is more than a little hacky).

Both share the same base class, so this in some ways reflects the extensible design of chart.js, but it involved adding some state to the slices that I don’t think would have otherwise been duplicated from the segment object.

Finally, I updated the tooltips template, which now iterates through slices as well as segments, and highlights slices on hover rather than segments (an implementation of which is shown in the spie-enhanced.html example).

Thoughts on Solution

Now that I have a better understanding of the structure of the codebase, I think I could do a better job modularizing certain functions and re-using existing core components. That said, i’m impressed how easy it was to create the new chart, and how little new code had to be written.

I thought about trying to allow the chart to behave like a multi-level pie chart, but there are already solutions for this, and adding an extra dimension would make things even messier.