Permalink
May 13, 2021
Newer
100644
75 lines (60 sloc)
1.6 KB
1
/**
2
* Monarchy Interface Design
3
* Time Complexity: O(n)
4
* Space Complexity: O(n)
5
*/
6
7
class Person {
8
constructor(name) {
9
this.name = name;
10
this.isAlive = true;
11
this.children = [];
12
}
13
}
14
15
class Monarchy {
16
constructor(king) {
17
this.king = new Person(king);
18
this._persons = {
19
[this.king.name]: this.king,
20
};
21
}
22
23
birth(childName, parentName) {
24
const parent = this._persons[parentName];
25
const newChild = new Person(childName);
26
27
parent.children.push(newChild);
28
this._persons[childName] = newChild;
29
}
30
31
death(name) {
32
const person = this._persons[name];
33
34
if (person === undefined) {
35
return null;
36
}
37
38
person.isAlive = false;
39
}
40
41
_depthFirstSearch(currentPerson, order) {
42
if (currentPerson.isAlive) {
43
order.push(currentPerson.name);
44
}
45
46
for (let i = 0; i < currentPerson.children.length; i += 1) {
47
this._depthFirstSearch(currentPerson.children[i], order);
48
}
49
}
50
51
getOrderOfSuccession() {
52
const order = [];
53
this._depthFirstSearch(this.king, order);
54
return order;
55
}
56
}
57
58
const monarch = new Monarchy("Jake");
59
60
monarch.birth("Catherine", "Jake");
61
monarch.birth("Tom", "Jake");
62
monarch.birth("Celine", "Jake");
63
monarch.birth("Peter", "Celine");
64
monarch.birth("Jane", "Catherine");
65
monarch.birth("Farah", "Jane");
66
monarch.birth("Mark", "Catherine");
67
68
console.log(monarch.getOrderOfSuccession());
69
/* ["Jake", "Catherine", "Jane", "Farah", "Mark", "Tom", "Celine", "Peter"] */
70
71
monarch.death("Jake");
72
monarch.death("Jane");
73
/* ["Catherine", "Farah", "Mark", "Tom", "Celine", "Peter"] */
74
75
console.log(monarch.getOrderOfSuccession());