Implementing a stack and using it to print alternate elements in reverse

Question

Challenge:

Implement a stack interface.

Specifications:

The interface should have ‘push’ and ‘pop’ functions.
Your task is to ‘push’ a series of integers and then ‘pop’ and print every alternate integer.
Your program should accept a file as its first argument.
The file contains a series of space delimited integers, one per line.
Print out every alternate space delimited integer, one per line.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Scanner;

public class Stack<T> {
    LinkedList<T> list = new LinkedList<>();

    public static void main(String[] args) throws FileNotFoundException {
        Scanner input = new Scanner(new File(args[0]));

        while (input.hasNextLine()) {
            System.out.println(
                retrieveAlternates(input.nextLine().split("\\s+"))
            );
        }
    }

    private static String retrieveAlternates(String[] input) {
        Stack<Integer> stack = new Stack<>();
        StringBuilder result = new StringBuilder();

        for (String s : input) {
            stack.push(Integer.parseInt(s));
        }

        for (int i = 0; i < input.length; i++) {
            if ((i & 1) == 0) {
                result.append(' ').append(stack.pop());
            } else {
                stack.pop();
            }
        }

        return result.substring(1);
    }

    public void push(T t) {
        list.add(t);
    }
    public T pop() {
        return list.removeLast();
    }
}

Tests:

@Test
public void test1 {
    assertEquals("4 2", Stack.retrieveAlternates("1 2 3 4"));
}

@Test
public void test2 {
    assertEquals("4 -2", Stack.retrieveAlternates("10 -2 3 4"));
}

I've never really had an "Implement X" challenge, before. This passed, but did I effectively do what was expected? Could it be better?

Answer 1

For this specific piece of code, I think actually implementing a stack would be better:

public class Stack<E> {

    private Node top;

    public Stack() {
        this.top = null;
    }

    public void push(E element) {
        Node temp = top;
        top = new Node(element);
        top.setNodeBelow(temp);
    }

    public E pop() {
        if (top == null) {
            // Do what you want to do here. You can throw an exception, or you
            // can just return null.
            return null;
        }
        E result = top.getValue();
        top = top.getNodeBelow();
        return result;
    }

    class Node {

        private E value;
        private Node below;

        public Node(E value) {
            this.value = value;
            this.below = null;
        }

        public E getValue() {
            return value;
        }

        public void setValue(E value) {
            this.value = value;
        }

        public Node getNodeBelow() {
            return below;
        }

        public void setNodeBelow(Node below) {
            this.below = below;
        }

    }

}

(And yes, add your main() and retrieveAlternatives() methods as well)

This way, your code can be faster as implementing a Stack with a LinkedList can slow you down, because a LinkedList also has to deal with size and more complicated Nodes.

I like the fact that you did (i & 1) == 0. Most programmers would (or at least I would) use (i % 2) == 1.

Here:

System.out.println(
        retrieveAlternates(input.nextLine().split("\\s+"))
);

I know you want to keep within the 85 (I think) character limit per line, but I think:

System.out.println(
        retrieveAlternates(input.nextLine().split("\\s+")));

is just as readable; or you can even do:

System.out.println(retrieveAlternates(input.nextLine().split("\\s+")));

and still be within the limit.

Answer 2

Since you passed this may be a moot point, but if this was an interview question, when the spec says "implement an interface", I would expect to see an interface:

public interface Stack<T> {

    void push(T item);

    T pop();
}

And an implementation:

public class StackImpl<T> implements Stack<T> {

    LinkedList<T> list = new LinkedList<>();

    @Override
    public void push(T item) {
        list.add(item);
    }

    @Override
    public T pop() {
        return list.removeLast();
    }
}

It's better to separate the interface, the implementation, and the runnable. So the code of the main program, and the retrieveAlternates method doesn't belong in a Stack class.

Also note that you don't need a stack at all to solve the problem. You can just reference the elements of the input by the right indexes, and you don't need to convert them to integers either:

static String retrieveAlternates(String[] input) {
    StringBuilder result = new StringBuilder();

    for (int i = 0; i < input.length; i++) {
        if ((i & 1) == 0) {
            result.append(' ').append(input[input.length - i - 1]);
        }
    }

    return result.substring(1);
}

I know this is cheating, but actually, you're already cheating when you implement a Stack interface using a LinkedList... At an interview I would expect that you'd have to implement an array-backed stack or something, without using the wonderful high level elements of the JDK.

Unit testing

Oddly, your unit tests have syntax errors: () missing from test1(), and both tests call a method whose signature doesn't exist. It's as if you've never run these tests, just typed them up here because you know I would pick on not having any tests...

Also, test1 and test2 are not good names: it's best when tests have descriptive names, so that they are easier to understand, both when reading the code later, and when something fails and reading the error messages.

I would propose this naming style:

@Test
public void test_1_2_3_4_gives_4_2() {
    assertEquals("4 2", Solution.retrieveAlternates("1 2 3 4".split("\\s+")));
}

@Test
public void test_10_m2_3_4_gives_4_m2() {
    assertEquals("4 -2", Solution.retrieveAlternates("10 -2 3 4".split("\\s+")));
}

The splitting, necessitated by the method under test is tedious, using new String[]{ ... } in each test case would also be tedious, so I'd suggest to simplify using a helper method:

void assertAlternates(String expected, String input) {
    assertEquals(expected, Solution.retrieveAlternates(input.split("\\s+")));
}

@Test
public void test_1_2_3_4_gives_4_2() {
    assertAlternates("4 2", "1 2 3 4");
}

@Test
public void test_10_m2_3_4_gives_4_m2() {
    assertAlternates("4 -2", "10 -2 3 4");
}

And I suggest adding some more potential corner cases:

@Test
public void test_1_gives_1() {
    assertAlternates("1", "1");
}

@Test
public void test_1_2_gives_2() {
    assertAlternates("2", "1 2");
}

Note that I'm not following camelCase for test method naming. I'm not aware of a standard for this, and static code analysis tools like Sonar don't complain about this kind of naming, even though I'm using the most strict rule set.

Keep in mind that unlike regular code, it's acceptable (and even recommended) to use long names for test methods. And these names tend to get long, snake_case is far more readable (in my opinion) than camelCase.