7
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I felt like I "cheated" but couldn't put my hands on it, thanks! I was confused/unsure if it literally wanted me to use an interface. Awesome answer as usual. \$\endgroup\$ – Legato Mar 8 '15 at 18:41
  • \$\begingroup\$ I'm a fan of parameterized testing, such as the way TestNG handles it. Because of that, I'm a fan of having a single @org.testng.annotations.Test-annotated method as an entry point and then pass in the required test values, or wrap them in a wrapper object, so that the tests' output look cleaner by way of TestNG calling toString(). If I do use the wrapper way, I will approach using an enum-driven solution where I can use slightly more meaningful value names, or optionally over-ride toString(). IMO this does away with the slightly off snake_case test method names... YMMV. ;) \$\endgroup\$ – h.j.k. Mar 9 '15 at 8:51
  • \$\begingroup\$ Also, my preference for an enum-driven solution only works well for repetitive testing on methods (especially those that will give you a range of outputs for different inputs). It is even possible to do a very light workaround for an enum value to do validation/exception-handling logic. On the other hand, if you're going to test a database access library for separate Create, Read, Update and Delete operations, then I'll opt for the usual separate testing methods... \$\endgroup\$ – h.j.k. Mar 9 '15 at 8:58
  • \$\begingroup\$ With that said, I think it's not a big issue here for test methods, as there really isn't a much better way to do so (unless you really want to read testOneTwoGivesTwo, probably being more confusing). However, I may consider referring to -2 as neg2/negative2/minus2 instead of m2, just to make it a little bit clearer... \$\endgroup\$ – h.j.k. Mar 9 '15 at 9:02
  • 1
    \$\begingroup\$ Thanks @h.j.k., that's insightful! For me, simple JUnit4 tests, non-parameterized, are the "sweet spot" at the moment. They let me do 80% of what I need at very little effort. Going all the way to 100% would take significantly more mental effort, for diminishing returns, often increased complexity. But someday, maybe, I might start using parameterized tests, and TestNG, and then that will become the new sweet spot. It's easily possible, I guess \$\endgroup\$ – janos Mar 9 '15 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.