{Kurung Kurawal}

Java Tree Test

konglie

Kali ini, saya ingin menyajikan solusi (versi saya) untuk sebuah pertanyaan logika. Jadi ceritanya, ada yang bertanya, bagaimana caranya menyusun logic/code untuk melakukan pengujian Tree (data). Ini sepertinya soal ketika interview kerja, atau sejenisnya.

Berikut pertanyaannya

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

/*
   1. Only write your code in the methods that have the comment 'write your code here' or in the section 'write optional helper functions here'
   2. Do not modify anything else
   3. If your code cannot compile or fails the test cases in 'main()', you will not receive a response from us
*/
 
import java.util.*;
import java.util.regex.*;
 
public class TreeTest {
    public static void main(String... args) {
 
        /*
           Consider the following tree:
 
                 1
              /  |  \
             2   4   6
           / |  / \  |  \  
          3  9 5  7  11 12
              / \      / | \
             13 16    14 23 17
               / \
              24 32
 
 
          Assuming the numbers are the ids of each node, the tree can be written down as follows:
 
          1(2,4,6) 2(3,9) 4(5,7) 6(11,12) 5(13,16) 12(14,23,17) 16(24,32)
 
          In the example above, for the group 1(2,4,6), node 2, 4 and 6 are the child nodes of
          node 1. Note that extra whitespaces should be accepted. Assume ids are positive integers only.
        */
 
        Tree first = new Tree("1(2,4, 6) 2(3, 9) 4(5,7)  6(11,12 ) 5(13,16)   12(14, 23, 17) 16( 24,32 )");
        assertTrue(first.getDepthOfNodeWithId(1) == 1);
        assertTrue(first.getDepthOfNodeWithId(4) == 2);
        assertTrue(first.getDepthOfNodeWithId(5) == 3);
        assertTrue(first.getDepthOfNodeWithId(12) == 3);
        assertTrue(first.getDepthOfNodeWithId(16) == 4);
        assertTrue(first.getDepthOfNodeWithId(23) == 4);
        assertTrue(first.getDepthOfNodeWithId(32) == 5);
 
        /*
              2
           / | | \ 
          5  4 3  1
          |     \
          7      9
         / \   /  \
        12 10 11  14
            |
            13
           / | \
         16  8  15
        */
 
        Tree second = new Tree(" 2(5, 4, 3,1)  5(7)   3(9) 7(12, 10)   9(11, 14)  10(13) 13(16,8,15)");
        assertTrue(second.getDepthOfNodeWithId(2) == 1);
        assertTrue(second.getDepthOfNodeWithId(5) == 2);
        assertTrue(second.getDepthOfNodeWithId(3) == 2);
        assertTrue(second.getDepthOfNodeWithId(12) == 4);
        assertTrue(second.getDepthOfNodeWithId(11) == 4);
        assertTrue(second.getDepthOfNodeWithId(13) == 5);
        assertTrue(second.getDepthOfNodeWithId(8) == 6);
    }
 
    private static void assertTrue(boolean v) {
        if(!v) {
            Thread.dumpStack();
            System.exit(0);
        }
    }
}
 
class Tree {
    private Node root;
 
    public Tree(String treeData) {
        // write your code here
    }
 
    public int getDepthOfNodeWithId(int id) {
        // write your code here
        // if a node is not found, return a negative value
    }
 
    // write optional helper functions here
}
 
class Node {
    private Node parent;
    private List<Node> children;
    private int id;
 
    public Node(int id) {
        this.id = id;
        this.children = new ArrayList<Node>();
    }
 
    public Node(int id, Node parent) {
        this(id);
        this.parent = parent;
    }
 
    public void appendChild(Node child) {
        children.add(child);
    }
 
    public int getId() {
        return id;
    }
 
    public List<Node> getChildren() {
        return Collections.unmodifiableList(children);
    }
}

Nah, ini solusi versi saya, bisa dilihat di code ini.
Demikian, semoga berguna untuk kita semua.