How Clear is this Interview 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)
How Clear is this Interview 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)