I used to be pretty good at logging onto TopCoder or HackerRank and brushing up on my problem solving skills, but I have to admit its been quite some time. So when I came across the minimum number of coins problem I decided to not only solve it, but solve it many times and see the performance differences amongst the solutions.

The problem:

Given a set of n coins, each with a different value (V1 , V2, ...Vn), and a given sum S, find the minimum number of coins that add up to S.

For example, given the set of coins whose values are (1, 5, 10 ,25), the minimum coins needed to make the sum of 23 is 5.

• 2 coins of value 10
• 3 coins of value 1

I really enjoy this problem, not only because I can solve it, but because it's something that anyone can understand, but not everyone realizes how hard it actually is to do (efficiently).

This will be a two part post: the first showing the brute force and greedy algorithm approaches, the second showing the backtracking and dynamic programming algorithms.

Full solutions can be found at: my github

The Setup

For better or worse, I decided the solution would be repsented in one of two ways:

1. Empty List - means no solution was possible
2. List of Pairs, where Pair.getLeft() is the number of coins and Pair.getRight() is the value of the coin.

Brute Force

The brute force approach involves finding all the possible solutions, then finding which of all the solutions uses the least amount of coins. This is obviously going to be largely innefficient but at least it does guarantee to find the optimal solution (if it ever finishes).

I decided to recursively find all solutions with the initial empty solution of 0 coins of each. Once a result is found I find the one with the least coins or else retun an empty list if no solution was found.

public List<Pair<Integer, Integer>> solve(int sum, int... coinValues) {
    Set<List<Pair<Integer, Integer>>> allSolutions = new HashSet<>();
    List<Pair<Integer, Integer>> coinStates = Arrays.stream(coinValues).mapToObj(v -> Pair.of(0, v))
            .collect(Collectors.toList());

    solutionHelper(sum, allSolutions, coinStates);
    return allSolutions.stream().collect(Collectors.reducing(this::optimalSolution)).orElse(new ArrayList<>());
}

public void solutionHelper(int sum, Set<List<Pair<Integer, Integer>>> allSolutions,
        List<Pair<Integer, Integer>> currentSolution) {
    int currentSum = calculateSum(currentSolution);
    if (currentSum == sum) {
        allSolutions.add(currentSolution.stream().filter(p -> p.getLeft() != 0).collect(Collectors.toList()));
        return;
    }

    if (currentSum > sum) {
        return;
    }
    for (int i = 0; i < currentSolution.size(); ++i) {
        List<Pair<Integer, Integer>> updatedSolution = new ArrayList<>(currentSolution);
        Pair<Integer, Integer> updateCoin = currentSolution.get(i);
        updatedSolution.set(i, Pair.of(updateCoin.getLeft() + 1, updateCoin.getRight()));
        solutionHelper(sum, allSolutions, updatedSolution);
    }

}

The recursive call basically checks if the current solutions sum is equal to the desired sum, if it is we're done so we add it the list of all solutions. If the sum is greater than the desired sum we stop rescursing, and lastly if the sum is still less than the desired sum, I recursively call solutionHelper, once for each of the coins.

Greedy

Unlike the brute force approach, the greedy algorithm will always finish quickly. The algorithm is dead simple: always choose the largest coin value that gets me closest to the desired sum. This algorithm is the only one that requires to do some work on the passed in coin values. Choose your favorite sorting algorithm and just sort the coinValues in descending order so that largest values are first. After that the code looks like:

public List<Pair<Integer, Integer>> solve(int sum, int... coinValues) {
    int remainder = sum;
    List<Pair<Integer, Integer>> change = new ArrayList<>();
    for (int value : descendingSort(coinValues)) {
        if (remainder == 0)
            return change;
        int numCoins = remainder / value;
        remainder %= value;
        if (numCoins > 0) {
            change.add(Pair.of(numCoins, value));
        }
    }

    return (remainder == 0) ? change : new ArrayList<>();
}

So off the bat the greedy algorithm is faster and the code is much easier to follow but...

The downside: it doesn't always work.

But why???

Basically if you have a bad set of coins values (3, 5, 11, 25) and the right sum (37), the greedy algorithm always overshoots the sum and since it only goes forward and never looks back, it can never find a solution.

But thankfully, it will always find a solution with a good set of coins but may not be the optimal solution. Also you need to have an unlimited of each amount of coin.

Conclusion

Both algorithms are simple to implement but both have their downsides. One takes too long for even small scenarios, and the other isn't guaranteed to find a solution. Luckily these aren't the only algorithmic tools we can use to solve this problem.

Whats better?

The next part of this post will describe the back tracking and dynamic programming solutions which can do much better.

It was that time again to try and learn a new language and like always I tried to figure out which of all the hippest languages was the one to get some of my precious time. Having jumped on the bandwagon too early on other languages, I've learned my lesson to learn the current most popular one. So what was my threshold this time?

• How long has it been around?
• Does it have an active community?
• Are people using it in production?
• Maturity of its toolchain
• How hard is it for me to deploy?

There were some contenders but I decided to go a non-JVM route so ended up with Golang...back to my college roots of C-like compiled binaries. Although I had some flashbacks of long nights at Qualcomm wading through Makefile after Makefile trying to figure out where the wrong compile flag came from but I decided to try it out anyways.

Learning the syntax was probably the easiest part of this journey. Despite differences from other languages, I found myself enjoying its conciseness and some of its fundamental choices like ability to return multiple objects and the disappearance of unnecessary characters. Once I got past the tutorials I tried building my own project - Animagi - an object mapper of sorts.

Most important to me was the kind of testing support available. It's nice that core language comes with a pretty good testing package but luckily I came accross Gomega and Ginkgo. With these two I was able to create some nice looking BDD tests with easy to use expectations. Brought me back to my rspec days with Ruby.

Now that I know I can test my code I started looking at the dependency management - having heard for the past few years that was one of the sticky points - I was happy to see that 'go dep' had made pretty nice progress. I've been spoiled with Maven, Gradle and to a lesser degree NPM/shrinkwrap. Although it still needs a lot of work its usable.

Lastly deployments.

Although Animagi is a library, I wrote the smallest webserver possible that does absolutley nothing and compiled it.

Docker to the rescue.

I really didn't want to worry about differences between the build server, and the test server, and the production server simply because one box got some package updates and others didn't so why not just throw the binary in a docker image through it in a container somewhere.

It's still early to put my verdict in writing but so far it's been fun and promising. Once I finish Animagi I'll start writing a full web service with routes for APIs and exported metrics that can be monitored. I feel like it'll be somewhere in between Spring Boot and an express node app.

Note: The gopher image is licensed under Creative Commons Attributions 3.0. Credit: Renee French

Software engineering is full of highly opinionated people. I mean just look at how many blogs you can follow...each of which are just another opinion to take into consideration. But I feel like many opinion-wars devolve into an individual engineer's choice of IDE/editor/terminal...a.k.a "Tools of the Trade".

The age old Vim vs. Emacs has evolved into IntelliJ vs Eclipse vs Sublime vs Atom vs notepad for all I care. You can crate software in almost any IDE/text editor (except iOS...don't get me started)...but really the most important part is being comfortable.
If I give any advice it would be learn the your tool. Anyone can learn the basics of programming in a particular language but being efficient and productive only comes after you become hyper familiar with your choice of tool. How does one drop a break point, how do you open a specific file, how do you pull up a call hierarchy...hell...how do you comment a chunk of code (I hate comments btw). No matter what language or which IDE, you should become familiar with all of the above without touching the mouse.

If you've ever seen someone at the keyboard who knows their IDE intimately you'll quickly appreciate how much work they can get done with such little effort. It's crazy how many shortcuts exist. I've been using some sort of Eclipse variant for over 7 years now and I'm still learning. Only until recently did I learn about "command + 3" (yes I use a Mac...circle back to earlier iOS comment) ...it's the gateway to any shortcut...and speeds up any taks: extracting constants, extracting methods and even switching perspectives.

Languages will come and go but the tools of the trade will adapt and keep you efficient for years to come. Learn one really well and slowly become adequate on the others. Don't let something small like an IDE slow you down from being great at your job.

If you were wondering...I prefer STS (Spring Tool Suite) for Java, Visual Studio Code for JavaScript and Sublime for anything else.

Interviewer: What's wrong with this code?

import java.time.LocalDateTime;

public class Service {

    public boolean isMorning() {
        LocalDateTime currentDateTime = LocalDateTime.now();
        
        return currentDateTime.getHour() < 12;
    }
}

This was my interview experience with the first Test Driven Development team with which I worked. It seemed silly at the time but after 10+ years of developing various software I still use the concepts behind the question.

If you're still scratching your head and wondering whether the class doesn't exist, or if the return type is wrong or maybe just overlooking some basic syntax - I'll save you the trouble and tell you the code is 100% functional. The main problem is that the code is completely untestable. Unless you want to run a server and wait up to 12 hours for the return value to change, the code needs some refactoring.

Tock

To show one way of making time-based business logic testable I wrote a very small SpringBoot app that sends back a greeting based on the system's local time. The fully working codebase can be found at https://github.com/barreeyentos/tock.

The main idea behind the code is that many applications rely on time somewhere in its logic and this code is usually the most error prone. I won't go into testing Time Zones as that needs a full dedicated blog but for now I'll stick to just one time zone (the server's timezone).

Let's start with this simple service:

@Service
public class GreetingService {

	public static final String INVALID_HOUR = "You should really fix the clock.";
	public static final String GOOD_NIGHT = "Good night";
	public static final String GOOD_AFTERNOON = "Good afternoon";
	public static final String GOOD_MORNING = "Good morning!";
	public static final String NIGHT_OWL = "Good morning?";

	private static final DateTimeFormatter formatter = DateTimeFormatter.ISO_DATE_TIME;

	public GreetingService() {
	}

	public Greeting createAppropriateGreeting() {
		String greeting = null;
		LocalDateTime localDateTime = LocalDateTime.now();
		String formattedTime = localDateTime.format(formatter);

		int hour = localDateTime.getHour();

		if (0 <= hour && hour <= 5) {
			greeting = NIGHT_OWL;
		} else if (6 <= hour && hour <= 11) {
			greeting = GOOD_MORNING;
		} else if (12 <= hour && hour <= 17) {
			greeting = GOOD_AFTERNOON;
		} else if (18 <= hour && hour <= 23) {
			greeting = GOOD_NIGHT;
		} else {
			greeting = INVALID_HOUR;
		}

		return new Greeting(greeting, formattedTime);
	}
}

We've made a great service (or just a greet service) ... seems bug-free and even handles invalid hours. Now let's go ahead and write a test.

private GreetingService service;

@Before
public void before() {
    service = new GreetingService();
}

@Test
public void testMorning() {

    Greeting greeting = service.createAppropriateGreeting();
    assertThat(greeting.getGreeting()).isEqualTo(GreetingService.GOOD_MORNING);
}

Hmmm... fail.

This test only passes at certain times of the day...so unless you only test in the morning these tests are pointless.

So far the GreetingService extremely straight-forward but still untestable so let's start refactoring. In order to make it better we need to be able to control how the localDateTime variable is set. You may first try passing the time into the method, but you will soon find that at some point in the application you still end up with untestable code. So how about create our own time service.

The TimeService Interface

For this app, the interface will be short and simple:

@FunctionalInterface
public interface TimeService {
	LocalDateTime now();
}

And the just as simple implementation:

@Service("timeService")
public class TimeServiceImpl implements TimeService {
	public LocalDateTime now() {
		return LocalDateTime.now();
	}
}

Now you can imagine the implementation of the GreetingService to be injected with a TimeService and now the time can be set as below:

@Autowired
public GreetingService(TimeService timeService){
    this.timeService = timeService;
}
...
LocalDateTime localDateTime = timeService.now();

You might be thinking that this is a waste of time and is just an over-engineered example but let's take another stab at our tests.

@Mock
TimeService timeService
private GreetingService service;

@Before
public void before() {
    service = new GreetingService(timeService);
    when(timeService.now()).thenReturn(LocalDateTime.of(2017, Month.SEPTEMBER, 17, 9, 30));
}

@Test
public void testMorning() {

    Greeting greeting = service.createAppropriateGreeting();
    assertThat(greeting.getGreeting()).isEqualTo(GreetingService.GOOD_MORNING);
}

Success!

Now you can test every line of code at any time of the day. These simple changes make your app 100% testable at both the unit and integration level.

You can probably stop reading now, but if you're still reading the next step is going to not use Mockito and just make my own Time Mock....Tock.

Since I already have an interface its easy enough to make my own testing implementation:

public class Tock implements TimeService {
	private LocalDateTime mockTime;

	public Tock() {
	}

	public void setTime(LocalDateTime now) {
		this.mockTime = now;
	}

	@Override
	public LocalDateTime now() {
		if (Objects.isNull(mockTime)) {
			return LocalDateTime.now();
		}
		return mockTime;
	}
}

Now the tests look something like:

TimeService timeService
private GreetingService service;

@Before
public void before() {
    timeService = new Tock();
    service = new GreetingService(timeService);
    timeService.setTime(LocalDateTime.of(2017, Month.SEPTEMBER, 17, 9, 30));
}

@Test
public void testMorning() {

    Greeting greeting = service.createAppropriateGreeting();
    assertThat(greeting.getGreeting()).isEqualTo(GreetingService.GOOD_MORNING);
}

But Why?!?!

Yes, you're right...one has a lot less code and why write your own mock? Well this is obviously a contrived application but if you're testing a loop that checks the time in every iteration, you might find it useful for your clock to advance 1 minute for every call of now(), or maybe you want to simulate time drift and you need to always be 30 seconds behind real time. Your own Tock can help you test more intricate scenarios where Mockito or other popular libraries can't help you.

Hopefully this example can help you test your apps just a little bit better than before and it can remind you to think about tests before you start to write code.

The full code for Tock that has integration tests for the Controller and unit tests for the service is here for your enjoyment: https://github.com/barreeyentos/tock.

EC2, ELB, Route53, S3...they stand out on any Software Engineer's resume these days but why should you want to learn these services? As of 2016, AWS had a 45% share of the public cloud infrstructure market, so it might be worth your time.

There are plenty of easier paths to get your pet project up and running such as Heroku, Engine Yard or Google App Engine; but I like to use AWS as my playground for the same reason I make side projects - to learn new skills that will help my career and my day to day easier. Here I'll give you a high level overview of what and how to set things up and a small ansible script that will re-create the network on your account.

The Basics

Setting up your infrastructure will consist of a VPC, a couple of subnets, an IGW, NAT and their routing tables. Breaking it down quickly, your VPC is your private network with an assigned IP range. Your VPC is broken up into subnets each of which get assigned a subset of your VPCs IP range. You'll want to make an IGW and assign your VPC to it. This will give your VPC access to the internet. The NAT similarly will give internet access to private subnets^[1] and disallow incoming connections to them. Lastly, and most importantly, are your routing tables. You associate your subnets with a routing table and then you create some routes to allow traffic in and out.

A minimum setup to get a project live and reachable would be 1 VPC, 1 subnet, an IGW and 1 routing table. The IGW is associated to the VPC, and the routing table allows all traffic from the IGW to your 1 subnet.

Note: At this point you only have the network setup, next steps would be to deploy your project to an EC2 instance and tweak its security group to allow specific ports to be used.

Click All The Things

When I first tried to set this up myself I spent a lot of time clicking. So many services and so many configuration pages and options are on every page of AWS it's extremely easy to get lost. The one thing I won't do in this blog is have screenshots of AWS with a step-by-step tutorial...it will be out of date by the time you read it, and it's honestly worth your time to go click all the things. Once you've gotten fairly familiar with the basics of AWS it's better to move on and just automate the setup. Lately I've been enjoying using Ansible for automated infrastructure becuase it was super simple to get started with.

Ansible

Ansible is a simple automation language that can perfectly describe an IT application infrastructure
-Ansible

I'm usually skeptical about a company's elevator pitch, but I have found that ansible is quite simple. There are modules for mostly everything, and when there aren't I can quickly write a script that gets the job done instead.

To create the simple setup we'll be using the Ansible Cloud Modules. Specifically:

• ec2_vpc_net
• ec2_vpc_igw
• ec2_vpc_subnet
• ec2_vpc_route_table

A sample task in a playbook would like:

- name:  "Create VPC for in AWS"
  ec2_vpc_net:
    profile: "barreeyentos_profile"
    region: "us-west-2"
    state: present
    cidr_block: "10.0.0.0/16"
    name: "barreeyentos_vpc"
    tags: {"Environment": "barreyentos"}
  register: vpc_result

To get the ansible playbook to work you will have to setup a few credentials that allow the creation of AWS resources. The complete step-by-step with the ansible playbook can be found here which is a playbook used to setup a small POC of setting up this blog powered by Ghost.

What I learned

The reason I like playing with and learning AWS is because it makes my day to day easier. As a software engineer I work with large distributed systems and writing code is only half the battle. Making it performant and reliable is more important than making sure the code formatted correctly or named appropriately and to do this I've had to understand the infrastructure the code is being deployed to. Understanding its limits and how it scales is usually faster than trying to micro-optimize algorithms. When PagerDuty wakes me up in the middle of the night because the servers are on fire, I like to have the peace of mind that I won't accidentally delete half of the network by clicking the wrong button. I also enjoy my sleep, so quickly knowing what service to scale up or which machine to add more disk space to is worth the time investment.