Java puzzle – solution

Three weeks ago we published a puzzle in our blog, challenging you to see if you can solve it. In this post we are going to publish the solution, so SPOILER ALERT – in case you wish to challenge yourself beforehand, I recommend to stop reading this post for now and to go and see the original puzzle. Another spoiler alert for the readers – the repository with the puzzle now also contains a solution package.

When you successfully solved the puzzle, it revealed an URL, opening which you could enter your solution in order to have a chance of winning one of the copies of the “Java Puzzlers” book. The challenge ended up being more popular than we thought – during the three weeks, we received 170 solutions and 312 unique visitors to the URL. We have also concluded the raffle and will contact the winners via email to send out the books.

The puzzle was calculating a number prefix for the solution URL. The calculation was carried out by 100 Workers running in 4 threads. Each of the Workers was assigned a number from 1 to 100, for which this particular Worker went ahead and

• looked up the number on the corresponding line from the resource located in this URL URL
• calculated the Fibonacci number corresponding to the number retrieved from the particular line in this file.
• stored the calculated result into the List to be used by Accumulators in the next phase

So, for example the Worker(2) would have received the number 10 from the second line in the aforementioned URL and had calculated 55 as the 10th Fibonacci number in return. Calculating Fibonacci numbers is recursive operation, so the built-in solution was using a cache for the intermediate results, so after the Worker(2) had completed, one would have expected to have cached the first 10 Fibonacci numbers for other Workers to use in next iterations.

As a last step, the puzzle was summarizing the results calculated by Workers. This took the 100 calculated Fibonacci numbers stored in the List and calculated the sum of those using Accumulators running in 8 threads.

In order to find the solution, you needed to improve the code in two regards

1. Performance of the code – the original version of the puzzle would have taken more than a month to calculate on most machines.
2. Correctness of the code – the original version contained synchronization issues making the calculated result incorrect.

Next, I will describe my solution to the puzzle. I went through the solutions sent to us and in several cases you found other interesting ways to solve it, many of which were different in some regards. So if your solution is not exact match, do not worry, it is the outcome that counts.

Our logic for solving this puzzle was contradicting the “first make it work and then make it fast” axiom – to find out what the code does, one would expect it to complete in reasonable time. So the very first step towards speeding up the calculation was figuring out the problem with the built-in caching solution – the CacheKey class contained the infamous hashCode()/equals() problem. Due to the problem, the original caching solution does not work as expected – the calculated Fibonacci numbers keep being added as the CacheKey instances keep returning unique hashCode() results and having 100% cache misses.

This in return triggers constant network round-trips to the source URL, taking more and more time during each iteration. The solution would be easy – add the implementation for the hashCode() and equals() methods similar to the following example and you had successfully solved the first step:

    @Override
    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;
      CacheKey cacheKey = (CacheKey) o;
      return key.equals(cacheKey.key);
    }

    @Override
    public int hashCode() {
      return key.hashCode();
    }

Next problem with the caching solution was its size. Even when the cache is now working as expected after the addition of the proper hashCode() and equals() methods, the cache size was not sufficient. The puzzle is calculating 100 Fibonacci numbers but the original cache size is set to 50. So in order to fully utilize the caching, the cache size was required to be set to 100 (or larger for that matter) instead of the default constructor setting it to 50:

public class Worker implements Runnable {

  private static final Cache cache = new Cache(100);

After making these two changes, the code was running fast, completing under 5 seconds, depending on the machine. But the calculated result was not a correct URL. This was due to the concurrency issue built into the Accumulator – multiple Accumulator threads were writing to the same result variable without any synchronization in place. The solution for this is again as easy as changing just two lines in the code, making the result summarizing to run in the synchronized block:

public void run() {
	synchronized (lock) {
        result = result.add(number);
    }
}

In addition, you had to make sure the result will not get cached by setting the results variable as volatile:

private volatile BigInteger result = BigInteger.ZERO;

Last challenge, affecting some of the runs, was related to the ExecutorService shutdown() mechanism. When shutting down the ExecutorService, the Accumulators are not guaranteed to have finished. So to overcome this, you needed to add the following after executorService.shutdown():

executorService.shutdown();
try {
  executorService.awaitTermination(10, TimeUnit.SECONDS);
} catch (InterruptedException e) {
  e.printStackTrace();
}

So all in all, in order to be successful, you needed to figure out that:

1. The caching solution does not work, triggering constant network round-trips
2. The cache is too small
3. The two synchronization issues with the result summarization
4. The proper way to shut down the ExecutorService

Many of you simplified the last two steps and used a simple loop instead of the complex ExecutorService solution built into the original puzzle. Even though this was not expected, it serves as an excellent example where a good engineer should thrive for simplicity. Indeed, the summarizing of the results could have done in a simple loop without all the unnecessary magic surrounding the concurrency.

For the 312 people who made it, good job! You really have what it takes to solve tough programming problems. Even though it was a small puzzle, it is representative of what our team faces during the day – to – day operations, seeing our customers suffering from many nasty performance issues, triggered often by similar problems.