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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138 | import java.util.*;
public class ManagerRelation {
private static Set<BinaryNode> treeNodes = new HashSet<BinaryNode>();
private static BinaryNode root;
public static void main(String[] args) {
try {
ManagerRelation mr = new ManagerRelation();
Scanner in = new Scanner(System.in);
int _count;
_count = Integer.parseInt(in.nextLine());
mr.readInput(_count, in);
} catch (NumberFormatException ne) {
ne.printStackTrace();
} catch (Exception e) {
e.printStackTrace();
}
}
private BinaryNode commonManager(BinaryNode root, String s1, String s2) {
if (root == null) {
return null;
}
if (root.getValue().equalsIgnoreCase(s1) || root.getValue().equalsIgnoreCase(s2)) {
return root;
}
BinaryNode left = commonManager(root.getLeft(), s1, s2);
BinaryNode right = commonManager(root.getRight(), s1, s2);
if (left != null && right != null) {
return root;
}
if (left == null) {
return right;
} else {
return left;
}
}
private boolean isNodeExists(String value) {
Iterator<BinaryNode> treeNodesIterator = treeNodes.iterator();
while (treeNodesIterator.hasNext()) {
BinaryNode n1 = treeNodesIterator.next();
if (value.equalsIgnoreCase(n1.getValue())) {
return true;
}
}
return false;
}
private BinaryNode getNode(String value) {
BinaryNode node = null;
Iterator<BinaryNode> treeNodesIterator = treeNodes.iterator();
while (treeNodesIterator.hasNext()) {
node = treeNodesIterator.next();
if (value.equalsIgnoreCase(node.getValue())) {
return node;
}
}
return node;
}
public void readInput(int count, Scanner in) {
//read the employee1 first name for whom we need to find the ancestor
String employee1 = in.next();
//read the employee2 first name for whom we need to find the ancestor
String employee2 = in.next();
//Define a set contains unique employees names, this set count should not be more than count of
// unique employees
Set<String> uniqueEmployees = new HashSet<String>(count);
uniqueEmployees.add(employee1);
uniqueEmployees.add(employee2);
while (uniqueEmployees.size() <= count) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 2; i++) {
sb.append(in.next());
if (i == 0) {
sb.append(",");
}
}
String[] relationLine = sb.toString().split(",");
uniqueEmployees.add(relationLine[0]);
uniqueEmployees.add(relationLine[1]);
if (uniqueEmployees.size() <= count) {
constructRelationTree(relationLine[0], relationLine[1]);
}
}
BinaryNode node = commonManager(root, employee1, employee2);
System.out.print(" FOund " + node.getValue());
}
private void printRelationTree(BinaryNode root) {
if (root == null) {
return;
}
System.out.print(root.getValue());
printRelationTree(root.getLeft());
printRelationTree(root.getRight());
}
private BinaryNode constructRelationTree(String s, String s1) {
BinaryNode node;
if (isNodeExists(s)) {
node = getNode(s);
} else {
node = new BinaryNode(s);
treeNodes.add(node);
if (root == null) {
root = node;
}
}
if (node.getLeft() == null) {
BinaryNode n1 = new BinaryNode(s1);
node.setLeft(n1);
treeNodes.add(n1);
} else {
BinaryNode n2 = new BinaryNode(s1);
node.setRight(n2);
treeNodes.add(n2);
}
return node;
}
}
|
Here I am attaching the code.
No comments:
Post a Comment