How Clear is this Interview Question?

Question

We are interviewing for a Senior Java Development Role and all three people that we have asked to complete this question gave us the same incorrect answer. The question was done before the interview so they had a lot of time. Their solutions seemed to sort the input by parentId and then childId instead of creating a tree and from the input and then traversing the tree to find the correct order. Is the question not clear enough?

Question:

The following is a simple skills and presentation test for the Java Developer role which must be completed before the telephone interview.

REQUIRED:

1. JUnit Test

2. Implementation of NodeSorter interface

QUESTION:

We have a Java object that looks something like this:

public class Node {

    public int id;
    public Integer parentId;

    public Node(int id, Integer parentId) {
        this.id = id;
        this.parentId = parentId;
    }
}

For example the following list of Node(s) might be displayed graphically as:

Node (id: 1, parentId: null), Node (id: 2, parentId: 1), Node(id: 3, parentId: 1), Node(id: 4, parentId: 2), Node(id: 5, parentId: 3)

              Node (id: 1)
             /            \
            /              \
           /                \
          /                  \
      Node (id: 2)         Node (id : 3)
         /                    \
        /                      \
       /                        \
      /                          \
  Node (id: 4)                 Node (id : 5)

Assumptions:

1. There will be always at least one Node

2. There will be one and only one Node with a null parentId

3. Every Node will have a valid parentId except for the Node which has a null parentId

Requirements:

1. Write a class that implements the following interface that will receive a List of Node(s) and order them from top to bottom (Nodes that are higher in the tree must be before the nodes lower in the tree. Eg. Node 1 on the top of the tree must be before node 4 which is on the bottom of the tree). Nodes on the same level will be in order of their id so the Node with id=2 will appear before the node with id=3 in the diagram above.

Interface:

    public interface NodeSorter {
        public List<Node> sort(List<Node> unSortedNodes);
    }

Test Data:

Test Case 1:

---

Diagram of Input:

              Node (id: 1)
             /            \
            /              \
           /                \
          /                  \
      Node (id: 2)   Node (id : 3)
         /                    \
        /                      \
       /                        \
      /                          \
  Node (id: 4)           Node (id : 5)

Input: Node (id: 2, parentId: 1), Node(id: 4, parentId: 2), Node (id: 1, parentId: null), Node(id: 3, parentId: 1), Node(id: 5, parentId: 3)

Output: Node (id: 1, parentId: null), Node (id: 2, parentId: 1), Node(id: 3, parentId: 1), Node(id: 4, parentId: 2), Node(id: 5, parentId: 3)

Test Case 2:

---

Diagram of Input:

              Node (id: 1)    
             /            \
            /              \
           /                \
          /                  \
      Node (id: 5)   Node (id : 2)
         /                    \
        /                      \
       /                        \    
      /                          \
  Node (id: 4)           Node (id : 3)

Input: Node (id: 5, parentId: 1), Node(id: 4, parentId: 5), Node (id: 1, parentId: null), Node(id: 3, parentId: 2), Node(id: 2, parentId: 1)

Output: Node (id: 1, parentId: null), Node (id: 2, parentId: 1), Node(id: 5, parentId: 1), Node(id: 3, parentId: 2), Node(id: 4, parentId: 5)

Answer 1

It appears to me that you're basically asking them to sort a list based on two factors - the parent ID and then the list ID. If that's the case, you could just simplify the question and not worry about the whole "tree structure" idea and just ask them to write a sort for a list based on two factors.

Answer 2

You can ask them to output the nodes in pre-order level-order, that ways the question would be crystal clear.

Answer 3

Honestly, the question seems pretty clear to me.

Have you tried asking them why they chose to sort by list ID and then node ID? Did they think that solved the problem? If so, what is their reaction when confronted with input for which it doesn't work?

Even if they didn't answer the question correctly, by asking them these questions you can both learn more about them and understand what in your question isn't clear enough.

Answer 4

I would say that this is pretty darn unclear. You want an unsorted list for input, and a sorted list as output.

Each item in the output list is a tree-node, but there is no balance enforced on the tree. Couldn't the user just read in the values for all the nodes, sort them, and then loop over the sorted values creating new nodes, each of which point at the previous node, and essentially be done...they've created a grossly unbalanced tree (no branches), but who cares?

That seems correct to me, but if I was interviewing I would not be very happy with this answer, because I would be wondering why the tree was there at all.

Nothing in this question indicates to me that I should do anything like what you're suggesting: "creating a tree and from the input and then traversing the tree to find the correct order."

Answer 5

The question was pretty clear. Everyone wrongly assumed that the tree was binary search, that may be why they did the sorting according to parentID, then listID. Which is wrong.

Answer 6

The question is clear in the input/output.

What data structure or algorithm should be used in the implementation is not specified hence, any can be used ( which is good ).

If the resulting code gives the expected output then, it is correct, even if they don't use a Tree ( because it was not in the specification ) if the output is wrong, the solution is wrong, even if they use a Tree.

Answer 7

I think the question itself is quite clear, but the choice of data in your test cases is leading people to attempt an incorrect solution (sorting by parentid). Perhaps this was deliberate?

If you want to make it more likely that respondents will get the correct answer, then you could include a test case that demonstrates that parent ids can be larger than child ids.

I'm not sure that would improve this as an interview question, however: it seems the question as written has the benefit of testing someone's ability to come up with a solution that's correct for all cases, not just for the samples they are provided.

Answer 8

Did you give examples of input and output to the interviewees like you did in the posting here? If you just give the rules without an example, I think someone could be forgiven for misunderstanding.

Personally, I think it's a good question. It's simple enough that you're not asking the applicant to spend days working on it, it has a clear, well-defined correct output, and a correct solution demonstrates a knowledge of how to manipulate data structures, which is pretty basic for a good developer. And I see you said that you asked applicants to do it before the phone interview, which I take it means do it at home, so they're not sitting in a room with an interview staring at them while they struggle and thus under artificial pressure.

The only real flaw I see is that it is not clear to me what the input is. You say the input is a list of nodes, apparently Node objects, but how does the programmer have any assurance that this list of nodes actually forms a tree? Is he supposed to simply assume that it is all valid input? Or is he supposed to validate it? I think you would be better to say that the function must accept the root node of a tree and then discover what nodes exist by traversal, rather than making the double problem of supplying the list and forcing the programmer to make sense of it.

It's a whole lot better than most of the interview questions I've gotten in my life, which tend to be questions like "How many years experience do you have with ...", "What is your greatest fault as an employee?", and "Do you have experience with Foobar version 3.9.7.6? Oh, you've only used version 3.9.7.5, sorry, we use 3.9.7.6 here."

My only quibble is, What does this question have to do with JUnit testing? You start out saying it's about JUnit testing but I don't see how it relates to that at all.

Answer 9

The question is CLEAR. You are asking for then BFS of the tree.

It's an interesting question for reviewing 1) abstraction capabilities; 2) order and style in programming 3) care for algorithm order (the big-O).

My answer for all that "how many times do you do that in your job" comments is:

• this question intends to evaluate:
  • the capacity of abstraction
  • the theory background
  • use of data structures and algorithms

If you can do that, then you are not a simple database-systems-oriented-basic-programmer.

Answer 10

How about updating the test cases to add tests that would fail given the incorrect solutions that are being provided?

It seems like that would be an obvious way to make the question a bit clearer. And then if they still don't understand the question or find it unclear given the question/test cases provided they can request additional information before completing their solution.