# Archive for the ‘Code Corner’ Category

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 {

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!

# ￼Code Corner: Create a queue from two stacks

In code corner, we take a real interview programming challenge and solve it in code. Whilst these questions may be likely be asked as a whiteboarding exercise, as a developer you will learn much more by actually coding the solution and getting your hands on the APIs, collections and algorithms in discussion

You can download this exercise from the CJIQ Github at https://github.com/corejavainterviewquestions/queuefromtwostacks. Each stage is a commit; rollback to the initial check out and code along on a branch. You can then compare your answer to mine. Results are developed using TDD.

Creating a queue from two stacks is one of those questions that seems to have lingered around for years and still gets asked. It’s a good one to know just in case it gets asked, but more importantly it’s a nice opportunity to look more into stacks, queues and calculating Big O.

The task is simple. Replicate the functionality of a queue using two stacks.

A Queue is a First-in-first-out (FIFO) data structure. If you push item A, B and C in that order, then pop three times, you will get A, B and C. Conversely, a stack is a Last-in-first-out (LIFO) structure; In the same example you would get C, B then A.

You can read more about these data structures in this previous post on interviews and data structures.

Queue has 2 methods we’re interested in: add and remove. Stack has push and pop.

``` @Test
public void addingOneItemAndRemovingFromQueueWillReturnThatItem() throws Exception {
Queue queue = new Queue();
￼￼
￼    assertThat(queue.remove(), is(“Item 1”));
}```

To write this test, I’ve created an add method- I’ve chosen to use Strings. We could generecise it very easily but let’s keep it simple. We add a remove method, which we expect to return the object we’ve added.
To implement is very simple; the functionality would be identical for a Stack, so we’re effectively just delegating.

``` Stack stackOne = new Stack();
stackOne.push(item);
}
public String remove() {
return stackOne.pop();
}```

First test pass! Feel the serotonin.

commit

Ok, time for a more realistic test, adding multiple items.

``` @Test
public void
Queue queue = new Queue();
assertThat(queue.remove(), is(“Item 1”));
}```

￼This gives a nice test fail; We’re getting item 3 back incorrectly. Now we need to actually think of an implementation.
Imagine our stack like a bucket.

We need to get to the bottom of the bucket to remove the item that was first in. The only way to do this is to pop all of the items in the way.
This test is really simple, so we don’t actually care about the other items. Let’s just pop everything out the way. It’s crude, but in TDD we aim to do the minimum work to make the test pass.

``` public String remove() {
String result = null;
while(!stackOne.isEmpty())
result = stackOne.pop();
return result;
}```

Pretty basic. Let’s write a harder test.

commit

I’ve renamed the last test and expanded it to include an extra pop.

``` @Test
public void
Queue queue = new Queue();
assertThat(queue.remove(), is(“Item 1”));
￼ assertThat(queue.remove(), is(“Item 2”));
}```

Now we need to handle the storage when popping items from stack one. The obvious location is to put onto the second stack we’re allowed. By putting each popped item on the stack we reverse the collection so it’s in the right order for a queue. The top item can then be returned.

We must then return all items back to the first stack so that we can add more items to the stack.

``` public String remove() {
while(!stackOne.isEmpty()) {
stackTwo.push(stackOne.pop());
}
String result = stackTwo.pop();
while(!stackTwo.isEmpty()) {
stackOne.push(stackTwo.pop());
}
return result;
}```

This makes the test pass, and is a an accurate albeit crude solution to the problem.

commit

There is some duplication in the code above. The TDD Mantra is Red, Green, Refactor. So let’s clean the code up a little.

``` public String remove() {
swapStacks(stackOne, stackTwo);
String result = stackTwo.pop();
￼ swapStacks(stackTwo, stackOne);
return result;
}
private void swapStacks(Stack stackOne, Stack stackTwo) {
while(!stackOne.isEmpty())
stackTwo.push(stackOne.pop());
}```

Not only is this cleaner code, but it’s much easier to understand what’s going on.

commit

What about missing tests? It’s important to think of edge cases in these scenarios. What about the empty case? Particularly in an interview it’s important you decide what is the correct behaviour. Should the queue return null or throw an Exception? Either could be argued quite reasonably. I have chosen to throw an exception, as passing null around can result in fragile and error prone code.

``` @Test(expected = NoSuchElementException.class)
public void throwsErrorIfRemoveCalledOnEmptyQueue(){
Queue queue = new Queue();
queue.remove();
}```

This test fails; we get an `EmptyStackException`. This should be an easy fix.

``` public String remove() {
if(stackOne.isEmpty())
throw new NoSuchElementException(“The Queue Is Empty”);
￼ swapStacks(stackOne, stackTwo);
String result = stackTwo.pop();
swapStacks(stackTwo, stackOne);
return result;
}```

Easy!

commit

Just for safety, lets throw in a more complex test, of multiple adds and removes.

``` @Test
public void multipleAddsAndRemovesInCorrectOrder() throws Exception {
Queue queue = new Queue();
assertThat(queue.remove(), is(“Item 1”));
assertThat(queue.remove(), is(“Item 2”));
assertThat(queue.remove(), is(“Item 3”));
assertThat(queue.remove(), is(“Item 4”));
}```

As expected, this test passes. We now have a complete Queue solution.
However, this is a very slow solution. Let’s analyse the Big O. First, we have to go through every item on the stack and pop it; that’s n. Then we have to push every
￼item, which is n again. We then pop all the items, another full iteration of n. We then add all bar one item back, n–1. That’s O(4n). Pretty poor! Can we come up with a better solution?
Let’s consider the first time we perform a remove operation. We push every item and pop it onto the secondary stack. At this point the secondary stack is in correct queue order. If we do not move back to first stack then we can just pop from the secondary queue until it is empty. If a remove request happens and stack 2 is empty, we simply swap the stacks then.

``` public String remove() {
if(stackOne.isEmpty() && stackTwo.isEmpty())
throw new NoSuchElementException(“The Queue Is Empty”);
if(stackTwo.isEmpty())
while(!stackOne.isEmpty())
stackTwo.push(stackOne.pop());
return stackTwo.pop();
}```

Every pop is from stack two. We check if there are elements (we now must check both stacks). If there are, we check whether we need to do a stack swap (i.e. stack two is empty). We can then pop from the top of stack 2.
As we now have a test suite we can run to check the solution, we know we haven’t broken anything.
But what is the complexity of this algorithm? When stack two becomes empty we have to do a full pop from stack one and push onto stack two; which is O(2n), simplified to O(n). However, this should not happen often (dependent on the usage of the stack). Most calls to remove will just execute stackTwo.pop(), which is a constant time operation.
We can therefore say that, whilst the worst case is O(n) it will give constant amortised time, e.g., if you run a million operations through the queue most of ￼them will be constant time.

### Given a sentence or formula containing square brackets, curly braces and brackets, write an algorithm to determine if it is balanced.

This question has been around for a long time but often candidates can struggle with it due to having limited data structures experience.  There’s a number of possible ways of coming up with a solution, but here’s the best I’m aware of.

At its purest form this is a matching exercise. We obviously need to loop through the characters in the sentence.  For efficiency we want to only iterate through it once, which rules out the option of taking each character and then trying to find it’s partner from the opposite end (which will result in multiple iterations).  But how do we keep track of what we have seen, and in what order?

In day to day work, people generally spend most of their time with Lists and Maps.  There’s a ton of other collections in the Java universe but people don’t get experience with them which is why this can be so tricky.   The data structure we’re looking for here is a Stack.  Stacks are LIFO, Last In First Out.  That means whichever element I most recently added will be removed first.  This is perfect for this exercise, as it means as I go through I can pop opening brackets onto the Stack, and if I find a closing brace I then can compare it to whatever is on top of the stack. If it matches then we’re happy, else we know we’re unbalanced.

```//pseudocode
loop through characters of string
If(this character is an opening brace)
push onto stack
if(this character is a closing brace)
pop from stack. If it isn't the matching brace, return false```

If you had figured out this far then well done.  You know how to use Stacks and how to apply it to this problem which is the main test as part of this question.  There are a couple of hazards to avoid when implementing though.

Firstly, although Java does have a Stack collection you shouldn’t use it. Even Oracle’s own documentation says to avoid it in favour of Dequeue.  A Dequeue is a double ended queue and has functionality to support LIFO and FIFO (First in First Out) functionality.

Secondly, it’s really easy to write ugly code for this.  Most the implementations you’ll find on line have a ton of if statements; there’s a particularly horrible implantation from Princeton you can see the source for here.  Big if statements are a terrible practice; they’re very difficult to read and understand.  Your code combined with your tests should be your documentation; if you feel the need to write comments then 95% of the time you need to break your code down and make it simpler. Hopefully you can apply your knowledge to come up with something a bit more obvious!

```import org.junit.Test;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

public class StackFormulaBalanceTest {

private StackFormulaBalance stackFormulaBalance;

@Test
public void emptyStringIsBalanced() throws Exception {
stackFormulaBalance = new StackFormulaBalance();
assertThat(stackFormulaBalance.balance(""), is(true));
}

@Test
public void lotsOfNestedBracketsButBalancedReturnsTrue() throws Exception {
stackFormulaBalance = new StackFormulaBalance();
assertThat(stackFormulaBalance.balance("([Hell{} T(h(e[r]e))]boom)"), is(true));
}
@Test
public void correctNumberOfClosingBracketsButInWrongOrderReturnsFalse() throws Exception {
stackFormulaBalance = new StackFormulaBalance();
assertThat(stackFormulaBalance.balance("(a[b{c)d]e}"), is(false));
}
@Test
public void onlyHasClosedBracesReturnsFalse() throws Exception {
stackFormulaBalance = new StackFormulaBalance();
assertThat(stackFormulaBalance.balance("}])"), is(false));
}
@Test
public void correctBalancingButWithMoreOpeningBracketsReturnsFalse() throws Exception {
stackFormulaBalance = new StackFormulaBalance();
assertThat(stackFormulaBalance.balance("({}"), is(false));
}
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class StackFormulaBalance {
Map<Character, Character> brackets = new HashMap<Character, Character>() {{
put('{', '}');
put('(', ')');
put('[', ']');
}};

public boolean balance(String toBalance) {
Deque<Character> bracketsStack = new ArrayDeque<Character>();
for (int i = 0; i < toBalance.length(); i++) {
char currentChar = toBalance.charAt(i);
if (characterIsOpenBracket(currentChar)) {
bracketsStack.push(currentChar);
} else if (characterIsAClosingBracket(currentChar) &&
closingBracketMatchesLastOpeningBracket(bracketsStack, currentChar)) {
return false;
}
}
return bracketsStack.isEmpty;
}

private boolean closingBracketMatchesLastOpeningBracket(Deque<Character> bracketsStack, char currentChar) {
return bracketsStack.size() == 0 || !brackets.get(bracketsStack.pop()).equals(currentChar);
}

private boolean characterIsAClosingBracket(char currentChar) {
return brackets.values().contains(currentChar);
}

private boolean characterIsOpenBracket(char currentChar) {
return brackets.containsKey(currentChar);
}
}
```

The private methods could be inlined if you’re that way inclined, but by pulling them out and naming them well we can make our algorithm clear. It reads very similarly to the pseudocode.

What do you think? Do you have a better implementation or other suggestions? Let me know!

Given a sentence such as “The fox jumps over the lazy dog”, implement in Java how you would reverse this to output “dog lazy the over jumps the fox”.

This is a relatively simple piece of code that has a few gotchas. Watch the code along video below or head straight past for the explanation.

```public class StringReverserTest {
@Test
public void wordsOfTheStringWillBeInReverseOrder() throws Exception {
StringReverser stringReverser = new StringReverser();
String result = stringReverser.reverse("fox jumps over the lazy dog");
assertThat(result, is("dog lazy the over jumps fox"));
}
}
public class StringReverser {

public String reverse(String stringToReverse) {
String[] split = stringToReverse.split(" ");
StringBuilder stringBuilder = new StringBuilder();
for (int i = split.length ; i > 0; i--) {
stringBuilder.append(split[i - 1] + " ");
}
return stringBuilder.substring(0, stringBuilder.length() - 1);
}
}```

First of all we need to split the string into its constituent words, which we can do using the .split() function on String.  It’s surprising how many people don’t realise functions like this exist which mean they are instantly flumoxed.

We then iterate in reverse through the array.  We take the length of the array (e.g. the number of words) and count down.  This can be tricky due to zero indexing so be careful.

We then append each word to a StringBuilder and add a space.  Why StringBuilder? If in theory we were to pass a huge sentence of thousands of words into this method then it would create a ton of objects, which would also make it slower.  Take this code sample I’ve just run on my machine:

```//Version 1
long l = System.currentTimeMillis();
StringBuilder sb = new StringBuilder();
for(int i=0; i<10000; i++){
sb.append("Core Java Interview Questions");
}
System.out.println(System.currentTimeMillis() - l);
//Version 2
l = System.currentTimeMillis();
String hi = "";
for(int i=0; i<10000; i++){
hi = hi + "Core Java Interview Questions";
}
System.out.println(System.currentTimeMillis() - l);```

The StringBuilder version takes 7ms. Incredibly the second version takes 4112ms.  That’s almost 600 times slower!

We then have the final gotcha; when returning the String we need to cut off the last space (every time we add a word we add a space to the end).  Substring can be tricky for getting the indexing

Write a program to detect if a String is a Palindrome
Watch the code-along video below or head straight past for the explanation.

```public class PallindromDetectorTest {
@Test
public void detectsThatRacecarIsRacecarBackwards() throws Exception {
PallindromDetector pallindromDetector = new PallindromDetector();
boolean result = pallindromDetector.check("racecar");
assertThat(result, is(true));
}

@Test
public void emptyStringIsAPallindrome() throws Exception {
PallindromDetector pallindromDetector = new PallindromDetector();
boolean result = pallindromDetector.check("");
assertThat(result, is(true));
}

@Test
public void oneLetterIsAPallindrome() throws Exception {
PallindromDetector pallindromDetector = new PallindromDetector();
boolean result = pallindromDetector.check("a");
assertThat(result, is(true));
}

@Test
public void returnsFalseForAWordThatIsNotAPallindrome() throws Exception {
PallindromDetector pallindromDetector = new PallindromDetector();
boolean result = pallindromDetector.check("Core Java Interview Questions");
assertThat(result, is(false));
}
}

public class PallindromDetector {
public boolean check(String toCheck) {
for (int i = 0; i < toCheck.length(); i++) {
int length = toCheck.length();
if(!(toCheck.charAt(i) == (toCheck.charAt(length -1-i)))){
return false;
}
if(i + 1 >= length/2)break;
}
return true;
}
}
```

In this example there are a few requirements considerations. What happens if the String is empty? What happens if there is only one letter?  You should ensure you ask this question. I’ve assumed that both are in fact palindromes.

There are multiple approaches to this, but I have gone with this simple solution that involves no extra data structures and only half a run through of the data.  We use a loop to iterate through the data; at 0, we check the first character to see if it matches the last character.  If it does not, we instantly return false.  We then increment i by 1, and check the next letter along, then the next furthest back.  This continues until we get halfway, or one less than halfway if it’s an uneven number of letters.

During pairing interviews we often chuck this little JUnit interview question into the mix:

```import org.junit.Test;

public class ATest {
private int testInstance = 0;

@Test
public void aTest() throws Exception {
testInstance++;
System.out.println(testInstance);
}

@Test
public void anotherTest() throws Exception {
testInstance++;
System.out.println(testInstance);

}

@Test
public void aSecondTest() throws Exception {
testInstance++;
System.out.println(testInstance);

}
}```

We have three tests and in each test we increment an integer by 1.  What is the expected output?

If you guessed 3 then you’re wrong! The reason we bring this up during a pair programming interview is because candidates will often use a teardown method to null or reset some data objects so that they’re back to their original state for the next test. You don’t need to do this! Each run of the test JUnit will create a brand new instance of the test. As a result the output of the above is “1” each time. To further proove the point, here is the output again but this time also printing out the object.

As you can see, each time there is a brand new instance created.

Which of these code fragments compile, and which do not?

``` //Example 1
int another[], y[];
// Example 2
int[] array, x[];
//Example 3
Object interesting = new Object[]{};```

If you think either Example 1 or 2 compile, what code would you write to initialise them?

All of the statements will compile. Example 1 is simply just creation of two array. to initialise these would just involve basic array syntax.

` int another[] = {}, y[] = {1,2,3};`

Example 2 is more nuanced. this is creating an int array called array, and and 2d int array called x.  To initialise would look like this:

`int[] array = {}, x[] = {{1,2,3},{4,5,6}};`

Example 3 would absolutely compile too.  An Object Array is still an Object.

For more Java Array madness, check out this great post at vanilla java.

Can you inherit from an interface twice? This would be pointless unless you throw in generics.  Imagine for example that I have an interface, Basket, which contains a type of fruit (T extends Fruit).  The interface has one method, select(T fruit), so I can take a type of Fruit from the basket. I want to have an implementation of Basket where I implement a Basket of Oranges and a Basket of Apples, from which I could take two types of fruit.

Does this compile?

```public interface Fruit {
}
public class Apple implements Fruit{
}
public class Orange implements Fruit{
}
void select(T myFruit);
}
@Override
public void select(Apple thingToJuggle) {
System.out.println("Tasty Apple!");
}
@Override
public void select(Orange thingToJuggle) {
System.out.println("Tasty Orange!");
}
}```

And the verdict is….

No! There’s not a chance this will compile. Ten points to you if you got the correct answer. To inherit from an interface twice is illegal in Java. It’s tempting to think that Generics will allow you to get away with it (and I confess I fell for this myself years ago when I was asked it in an interview). But generics are implemented terribly in Java, and one of the consequences is that they are erased away before runtime- better known as type erasure. So at compile time it may be implementing Basket<Orange>, Basket<Apple>, but at runtime this just becomes implements Basket, Basket, which is illegal syntax.

How did you do?  Do you think your colleagues would’ve got the right answer? Challenge them now by sending them this post via Tweet or Facebook.

Photo credit Marcus Spiske