Java Code Challenge: Nodes!

Welcome to Java Code Challenge! We’re taking challenges for reddit’s dailyprogrammer and going on a deep dive into the answer. A working solution is not enough; we’re looking for the cleanest Java code with tests. 3rd party libraries are welcome but if you can do it without it will be easier for others to comprehend.

If you can fit your solution in the comments then go for it, but preferably put your answer in GitHub and link in the comments. Next week we’ll be sharing the best solutions and sharing the best code practices we see!

Scroll to the bottom if you want the solution.

Challenge

In graph theory, the degree of a node is the number of edges coming into it or going out of it – how connected it is. For this challenge, you’ll be calculating the degree of every node.

Input Description

First, you’ll be given an integer, N, on one line showing you how many nodes to account for. Next, you’ll be given an undirected graph as a series of number pairs, a and b, showing that those two nodes are connected – an edge. Example:

3 
1 2
1 3

Output Description

Your program should emit the degree for each node. Example:

Node 1 has a degree of 2
 
Node 2 has a degree of 1
 
Node 3 has a degree of 1

Challenge Input

This data set is a social network of tribes of the Gahuku-Gama alliance structure of the Eastern Central Highlands of New Guinea, from Kenneth Read (1954). The dataset contains a list of all of the links, where a link represents signed friendships between tribes. It was downloaded from the network repository.

16
1 2
1 3
2 3
1 4
3 4
1 5
2 5
1 6
2 6
3 6
3 7
5 7
6 7
3 8
4 8
6 8
7 8
2 9
5 9
6 9
2 10
9 10
6 11
7 11
8 11
9 11
10 11
1 12
6 12
7 12
8 12
11 12
6 13
7 13
9 13
10 13
11 13
5 14
8 14
12 14
13 14
1 15
2 15
5 15
9 15
10 15
11 15
12 15
13 15
1 16
2 16
5 16
6 16
11 1
12 16
13 16
14 16
15 16

Challenge Output

Node 1 has a degree of 8
Node 2 has a degree of 8
Node 3 has a degree of 6
Node 4 has a degree of 3
Node 5 has a degree of 7
Node 6 has a degree of 10
Node 7 has a degree of 7
Node 8 has a degree of 7
Node 9 has a degree of 7
Node 10 has a degree of 5
Node 11 has a degree of 9
Node 12 has a degree of 8
Node 13 has a degree of 8
Node 14 has a degree of 5
Node 15 has a degree of 9
 
Node 16 has a degree of 9

Solution time

This is a relatively simple challenge but one that demonstrates why programming is more of an art than a science. Every single response was different in design and style. There is no one “correct” answer, which is one of the wonderful things about programming.

One of the aims for this series for me is to highlight more than just correct solutions, but solutions which are good code- code which, if in a production code base, would not quickly become legacy code or difficult to maintain.

This is not an inditement on any of the solutions- it’s a simple code challenge and so it stands to reason most people will just be solving it for the challenge, not to write beautiful code.

The general solution

The reason this is particularly easy as a challenge is that the input tells us how many nodes to expect- we don’t need to figure this out for ourselves. We’re also assuming that all our data input is accurate which makes it super simple.

So, we simply need to add up how many times a node ID appears in the input and store that number for each node. Pretty simple bucketing, which is what most people chose to do. Take this example from Jusio, which uses an array to store the totals.

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Scanner;

public class Degrees {

    public static void main(String[] args) throws IOException {

        Scanner scanner = new Scanner(Files.newBufferedReader(Paths.get(args[0])));
        final int[] dependencies = new int[scanner.nextInt()];
        while (scanner.hasNext()) {
            dependencies[scanner.nextInt() - 1]++;
            dependencies[scanner.nextInt() - 1]++;
        }
        for (int i = 0; i < dependencies.length; i++) {
            System.out.printf("Node %s has degree of %s\n", i + 1, dependencies[i]);
        }
    }
}

As we know how many nodes there are up front an array is a perfectly viable solution.

In Java 8 we can “one line” this thanks to Streams. Jusio also offered up a Java solution.

Files.lines(Paths.get(args[0]))
  .skip(1)
  .flatMap(it -> Stream.of(it.split(" ")))
  .collect(Collectors.groupingBy(Integer::new, Collectors.counting()))
  .forEach((node, count) -> out.printf("Node %s has degree of %s\n", node, count));

A nice condensed solution. However, it’s important to be careful with Java 8’s functional features. Since their release I’ve seen a tendancy by developers to go overboard to try and crush all their code into a one liner. When writing code readability should be our number one concern. Clean, readable code is easier to maintain.  I personally find the Java 7 version easier to comprehend, although for an example this simple it’s not that big a problem.

A pause for thought

The thing that has come across pretty consistenly is that most of the solutions have not been written using TDD or tests. That’s fine- I understand not everyone loves TDD as much as I do. But that has lead to one-shot code that has no seperation of concerns. The entire solution is shoved into a main method. As mentioned before this produces an adequate solution but not sustainable code.

I recieved an email after posting this challenge:

“to be clear, is the input standard in or a file?”

The answer for me is clear- it doesn’t matter. The way I approached this challenge was to start with the functionality- the bucketing- and providing the data in using a test, and testing the data out by giving access to the underlying sorted data.

@Test
   public void twoNodesConnectedResultsInTwoOutputLines(){
       NodeChecker nodeChecker = new NodeChecker(2, "1 2");
       String[] output = nodeChecker.output;

       assertThat(output.length, is(2));

       assertThat(output[0], is("Node 1 has a degree of 1"));
       assertThat(output[1], is("Node 2 has a degree of 1"));

   }

My NodeChecker class takes the input already split into the first line and the rest of the file.  This way I can test that the functionality is correct without worrying about the format it’s coming in as.

I could have even gone a step further and had the NodeChecker expose it’s collection counting the node degrees as opposed to it directly resulting in the textual output.  At the moment my solution is highly coupled to the output format.

However, it’s a simple interview challenge, and wouldn’t be hard to refactor  to something better :).

Next Step

If you’ve enjoyed this, I’ve just release a brand new video course.  I’ve taken a programming interview challenge that I give to my candidates and done a deep dive into the solution.  You’ll learn how to use Test Driven Development to solve a complicated programming challenge, along with a whole slew of advice, tips and tricks for impressing your interviewer.

Check out the new TDD course!

 

 

 

 

 

One Comment

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>