---
tags: hierarchy service
---
# Hierarchy Service
contributed by < [henrychen0622](https://github.com/henrychen0622) >
## Introduction
>In our application we organize data in a hierarchy and we have a
service that we use to manage it. In this exercise you'll write a
simplified version of that service. It uses a similar API, but in
the interest of time, avoids tricky problems around availability,
scalability, concurrency, and persistance.
## Environment
```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 36 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 6
On-line CPU(s) list: 0-5
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-9400 CPU @ 2.90GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 2904.0000
CPU min MHz: 0.0000
BogoMIPS: 5808.00
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb r
dtscp lm pni pclmulqdq dtes64 est tm2 ssse3 fma cx16 xtpr pdcm pcid sse4_1 sse4_2 movbe popcnt xsave osxsave avx f16c rdrand hypervisor lahf
_lm abm 3dnowprefetch fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt ibrs ibpb stibp ssbd
Virtualization features:
Hypervisor vendor: Windows Subsystem for Linux
Virtualization type: container
```
## Problem description
>Your service will maintain a hierarchy of nodes in memory. The API
supports adding and deleting nodes, moving them to a new position in
the tree, and searching. Each node is identified by a name and an
ID (both strings). The name of a node must be unique among its
siblings (i.e., the children of the node's parent); the ID must be
unique among all nodes in the tree.
>The interface uses JSON-encoded messages. Your program will receive
requests on standard input and write responses to standard output.
>Note: if standard output is buffered by default in your language,
make sure to either disable buffering or do a flush after you write
each response. If standard output is being buffered, the test
client may not see your response, which will cause it to wait
forever.
>To simplify parsing, each request will be contained
on a single line. Your responses don't have to be on a single line.
Your program will not receive a new request until the response has
been received from the previous request. Your program will never
receive invalid JSON as a test case. Your program should exit
gracefully when it detects end of file on standard input.
>Note: If you want to do printf-style debugging, make sure to write
to standard error instead of standard output.
>We've given example input and output for each request (see below).
Your responses don't have to look exactly like the example
responses, but they have to be equivalent JSON objects.
>We've also provided a test client to help validate your implementation.
Please test your implementation with the test client. Your
implementation will be expected to pass all of the tests provided
by the test client, along with some additional tests. See below for
information on running the test client.
>We don't expect you to write your own test suite unless you feel
it helps you work.
>Beyond the API, we leave all implementation details to you. Use the
language of your choice and architect the service however you see fit.
You can use whatever references you want, but please restrict yourself
to your language's core libraries (unless you need to use an external
library to support JSON encoding/decoding).
## API Methods
>For all methods except Query, the response is a simple JSON object
indicating success or failure:
>Success response:
```json
{"ok":true}
```
>Failure response:
```json
{"ok":false}
```
## API operations
### Add Node
>Description:
- Add a new node to the tree.
>Params:
- name {string}: Node name
- id {string}: Node ID
- parent_id {string}: ID of the parent node; if ommitted or empty string,
add this node as the root node (assuming there isn't
already a root node)
>Validation:
- Two sibling nodes cannot have the same name.
- No two nodes in the tree can have the same ID.
- There can only be one root node (i.e., a node without a parent).
- Name and ID must be specified and not empty strings.
- If specified, parent node must exist.
> Example: Add the root node
Request:
```json
{"add_node":{"id":"1","name":"Root"}}
```
Response:
```json
{"ok":true}
```
> Example: Add a child node
Request:
```json
{"add_node":{"id":"4","name":"Child42","parent_id":"1"}}
```
Response:
```json
{"ok":true}
```
> Example: Add a child node to nonexistent parent.
Request:
```json
{"add_node":{"id":"4","name":"Child78","parent_id":"200"}}
```
Response:
```json
{"ok":false}
```
```cpp
void hierarchy::add_node(string name, string id, string parent_id) {
/* Name and ID must be specified and not empty strings. */
if (id == "" || name == "") {
std::cout << fail << std::endl;
return;
}
/* There can only be one root node */
if (parent_id == "") {
if (root != nullptr) {
std::cout << fail << std::endl;
return;
} else {
root = new Node(id, name);
std::cout << pass << std::endl;
return;
}
}
/* Inorder Traversal */
stack<Node *> s;
Node *cur = root;
Node *parent = nullptr;
while (cur || !s.empty()) {
if (cur) {
s.push(cur);
cur = cur->child;
} else {
Node *node = s.top();
s.pop();
/* unique id, siblings cannot have the same name */
if ((node->id == id) ||
(node->parent_id == parent_id && node->name == name))
{
std::cout << fail << std::endl;
return;
}
if (node->id == parent_id)
parent = node;
cur = node->next;
}
}
/* parent node must exist */
if (nullptr == parent) {
std::cout << fail << std::endl;
return;
}
/* check if it is the first child */
if (nullptr == parent->child) {
parent->child = new Node(id, name, parent_id);
std::cout << pass << std::endl;
return;
} else {
cur = parent->child;
if (cur->name > name) {
parent->child = new Node(id, name, parent_id);
parent->child->next = cur;
std::cout << pass << std::endl;
return;
}
while (cur->next && cur->next->name <= name) {
cur = cur->next;
}
Node *next = cur->next;
cur->next = new Node(id, name, parent_id);
cur->next->next = next;
std::cout << pass << std::endl;
return;
}
cout << "it should never be printed !" << endl;
return;
}
```
### Delete Node
> Description:
- Delete a node from the tree.
> Params:
- id {string}: ID of node to delete
> Validation:
- ID must be specified and not an empty string.
- Node must exist.
- Node must not have children.
> Example: Add root node and then delete it.
Request:
```json
{"add_node":{"id":"1","name":"Root"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"delete_node":{"id":"1"}}
```
Response:
```json
{"ok":true}
```
> Example: Delete nonexistent node
Request:
```json
{"delete_node":{"id":"1"}}
```
Response:
```json
{"ok":false}
```
```cpp
void hierarchy::delete_node(string id) {
/* ID must be specified and not empty strings. */
if (id == "") {
std::cout << fail << std::endl;
return;
}
/* Inorder Traversal */
stack<Node *> s;
Node *cur = root;
Node *parent = nullptr;
while (cur || !s.empty()) {
if (cur) {
s.push(cur);
cur = cur->child;
} else {
Node *node = s.top();
s.pop();
if (node->next && node->next->id == id) {
/* Node must not have children. */
if (nullptr != node->next->child) {
std::cout << fail << std::endl;
return;
}
Node *next = node->next;
node->next = node->next->next;
delete next;
std::cout << pass << std::endl;
return;
}
if (node->id == id) {
/* Node must not have children. */
if (nullptr != node->child) {
std::cout << fail << std::endl;
return;
}
parent = s.top();
parent->child = node->next;
node->next = nullptr;
delete node;
std::cout << pass << std::endl;
return;
}
cur = node->next;
}
}
/* Node must exist. */
std::cout << fail << std::endl;
}
```
### Move Node
> Description:
- Move a node to a new parent in the tree
> Params:
- id {string}: ID of node to move
- new_parent_id {string}: ID of the new parent node
> Validation:
- ID and new parent ID must be specified and not empty strings.
- Both nodes must exist.
- The name of the node to be moved must not be the same as those of any of
the new parent's other children.
- Move must not create a cycle in the tree.
> Example: Add root and two children, then move one child under the other one.
Request:
```json
{"add_node":{"id":"1","name":"Root"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"add_node":{"parent_id":"1","id":"2","name":"A"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"add_node":{"parent_id":"1","id":"3","name":"B"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"move_node":{"id":"2","new_parent_id":"3"}}
```
Response:
```json
{"ok":true}
```
> Example: Add root, child, child of child, then try to move first child under second (which would create a cycle).
Request:
```json
{"add_node":{"id":"1","name":"Root"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"add_node":{"parent_id":"1","id":"2","name":"A"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"add_node":{"parent_id":"2","id":"3","name":"B"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"move_node":{"id":"2","new_parent_id":"3"}}
```
Response:
```json
{"ok":false}
```
```cpp
void hierarchy::move_node(string id, string new_parent_id) {
/* ID and new parent ID must be specified and not empty strings. */
if (id == "" || new_parent_id == "" || id == root->id ||
id == new_parent_id) {
std::cout << fail << std::endl;
return;
}
stack<Node *> s;
stack<Node *> ss;
s.push(root);
Node *parent_tmp = root;
Node *parent = nullptr;
Node *prev = nullptr;
Node *child = nullptr;
Node *new_parent = nullptr;
int depth = 0;
find_root_id_node(root, &new_parent, new_parent_id, depth);
if (nullptr == new_parent) {
std::cout << fail << std::endl;
return;
}
/* Preorder Traversal */
while (s.size() > 0) {
Node *node = s.top();
s.pop();
/* Move must not create a cycle in the tree. */
if (!child && node->next && node->next->id == id) {
prev = node;
child = node->next;
if (child->child) {
ss.push(child->child);
while (ss.size() > 0) {
Node *node_tmp = ss.top();
ss.pop();
if (node_tmp->id == new_parent_id) {
std::cout << fail << std::endl;
return;
}
if (node_tmp->child) ss.push(node_tmp->child);
if (node_tmp->next) ss.push(node_tmp->next);
}
}
break;
}
/* Move must not create a cycle in the tree. */
if (!child && node->id == id) {
parent = parent_tmp;
child = node;
if (child->child) {
ss.push(child->child);
while (ss.size() > 0) {
Node *node_tmp = ss.top();
ss.pop();
if (node_tmp->id == new_parent_id) {
std::cout << fail << std::endl;
return;
}
if (node_tmp->child) ss.push(node_tmp->child);
if (node_tmp->next) ss.push(node_tmp->next);
}
}
break;
}
if ((node->child) && (!child) || (child && prev)) {
parent_tmp = node;
s.push(node->child);
}
if (node->next) {
if (node->next == child) {
if (node->next->next)
s.push(node->next->next);
} else {
s.push(node->next);
}
}
}
/* Both nodes must exist. */
if (child == nullptr) {
std::cout << fail << std::endl;
return;
}
/* check if it is the first child */
if (nullptr == new_parent->child) {
if (prev) {
prev->next = prev->next->next;
child->next = nullptr;
} else if (parent) {
parent->child = child->next;
child->next = nullptr;
} else {
cout << "somthing wrong, should not be here" << endl;
return;
}
new_parent->child = child;
std::cout << pass << std::endl;
return;
} else {
Node *cur = new_parent->child;
/* check same name */
while (cur) {
if (cur->name == child->name) {
std::cout << fail << std::endl;
return;
}
cur = cur->next;
}
/* move from parent */
if (prev) {
prev->next = prev->next->next;
child->next = nullptr;
} else if (parent) {
parent->child = child->next;
child->next = nullptr;
} else {
cout << "somthing wrong, should not be here" << endl;
return;
}
/* move to new parent*/
cur = new_parent->child;
if (cur->name > child->name) {
new_parent->child = child;
child->next = cur;
child->parent_id = new_parent->id;
std::cout << pass << std::endl;
return;
}
while (cur->next && cur->next->name <= child->name) {
cur = cur->next;
}
Node *next = cur->next;
cur->next = child;
child->next = next;
child->parent_id = new_parent->id;
std::cout << pass << std::endl;
return;
}
}
```
### Query
> Description:
- Return a list of nodes matching certain criteria.
> Params:
- min_depth {integer}: Minimum distance from root of query. Default: none.
- max_depth {integer}: Maximum distance from root of query. Default: none.
- names {list of strings}: If specified, only return nodes whose names are in
the list.
- ids {list of ids}: If specified, only return nodes whose IDs are in
the list.
- root_ids {list of ids}: Search subtrees rooted at specified nodes.
If not specified, search from the root. If any ID
in the list doesn't exist in the tree, ignore it.
> Validation:
>
All parameterss are optional. If no parameters are specified, return all
nodes. If no nodes match, return an empty list of nodes. There are
no failure cases.
Nodes must be returned in the order in which they would be found
in a pre-order depth first traversal with sibling nodes being
processed in order by name. Your query function should consider all
nodes in that order and include any nodes in the response that match
the specified parameters. Each node returned must match all specified
query parameters, as described above.
If a list of root IDs is specified, perform separate queries as
described above for the subtrees rooted at each specified root node.
The returned list of nodes should be the concatenation of the results
of each individual subtree query in the order given by the list
of root IDs. Ignore any specified root IDs that don't exist in the
tree.
For minimum and maximum depth, depth refers to the number of levels
a given node is below the root of the query (i.e., the number of
edges that must be traversed to get from the root of the query to
the given node). For example, the root of a query is at depth 0,
its children are at depth 1, their children are at depth 2, etc.
If minimum depth is specified, only nodes whose depths are greater
than or equal to the minimum depth should be considered. Similarly,
if maximum depth is specified, only nodes whose depths are less
than or equal to the maximum depth should be considered. If both
minimum and maximum depths are specified, only nodes whose depths
fall within that range should be considered.
> Example: Add nodes and query with max_depth 1.
Request:
```json
{"add_node":{"id":"1","name":"Root"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"add_node":{"parent_id":"1","id":"2","name":"A"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"add_node":{"parent_id":"2","id":"3","name":"B"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"query":{"max_depth":1}}
```
Response (pretty-printed for ease of reading):
```json
{
"nodes": [
{
"id": "1",
"name": "Root",
"parent_id": ""
},
{
"name": "A",
"id": "2",
"parent_id": "1"
}
]
}
```
> Example: Add nodes and query for nodes named "B".
Request:
```json
{"add_node":{"id":"1","name":"Root"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"add_node":{"parent_id":"1","id":"2","name":"A"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"add_node":{"parent_id":"2","id":"3","name":"B"}}
```
Response:
```json
{"ok":true}
```
Request:
```json
{"query":{"names":["B"]}}
```
Response (pretty-printed for ease of reading):
```json
{
"nodes": [
{
"id": "3",
"parent_id": "2",
"name": "B"
}
]
}
```
```cpp
void hierarchy::query(int min_depth, int max_depth, vector<string>& names,
vector<string>& ids, vector<string>& root_ids)
{
json j_arr;
json j;
json j_tmp;
if (!root || (max_depth < min_depth)) {
j["nodes"] = j_arr;
std::cout << j.dump(4) << std::endl;
return;
}
m_max_depth = max_depth;
m_min_depth = min_depth;
for (int i = 0; i < names.size(); i++)
m_names_set.insert(names[i]);
for (int i = 0; i < ids.size(); i++)
m_ids_set.insert(ids[i]);
for (int i = 0; i < root_ids.size(); i++) {
m_root_ids_set.insert(root_ids[i]);
}
std::set<string>::iterator itr;
if (!m_root_ids_set.empty()) {
// code here
for (itr = m_root_ids_set.begin(); itr != m_root_ids_set.end(); itr++) {
int depth = 0;
Node *node_be_found = nullptr;
find_root_id_node(root, &node_be_found, *itr, depth);
if (node_be_found != nullptr) {
preOrder(node_be_found->child, depth + 1);
}
}
}
else {
preOrder(root, 0);
}
j["nodes"] = m_j_arr;
std::cout << j.dump(4) << std::endl;
out:
m_max_depth = INT_MAX;
m_min_depth = 0;
m_names_set.clear();
m_ids_set.clear();
m_root_ids_set.clear();
m_j_arr.clear();
}
```
### API parser(json)
> Use the third party lib to implement json parser <[nlohmann](https://github.com/nlohmann/json)>
```cpp
void jsonDecodeProcess(hierarchy &h, json j) {
h.m_mutex.lock();
json::iterator it = j.begin();
string input_fun = it.key();
string id;
string name;
string parent_id;
string new_parent_id;
int min_depth = 0;
int max_depth = INT_MAX;
vector<string> names;
vector<string> ids;
vector<string> root_ids;
if (input_fun == "add_node") {
if (nullptr != j[input_fun]["id"])
id = j[input_fun]["id"];
if (nullptr != j[input_fun]["name"])
name = j[input_fun]["name"];
if (nullptr == j[input_fun]["parent_id"]) {
return h.add_node(name, id, "");
} else {
parent_id = j[input_fun]["parent_id"];
h.add_node(name, id, parent_id);
}
} else if (input_fun == "delete_node") {
if (nullptr != j[input_fun]["id"])
id = j[input_fun]["id"];
h.delete_node(id);
} else if (input_fun == "move_node") {
if (nullptr != j[input_fun]["id"])
id = j[input_fun]["id"];
if (nullptr != j[input_fun]["new_parent_id"])
new_parent_id = j[input_fun]["new_parent_id"];
h.move_node(id, new_parent_id);
} else if (input_fun == "query") {
if (j[input_fun]["min_depth"] != nullptr)
min_depth = j[input_fun]["min_depth"];
if (j[input_fun]["max_depth"] != nullptr)
max_depth = j[input_fun]["max_depth"];
if (j[input_fun]["names"] != nullptr)
j[input_fun].at("names").get_to(names);
if (j[input_fun]["ids"] != nullptr)
j[input_fun].at("ids").get_to(ids);
if (j[input_fun]["root_ids"] != nullptr)
j[input_fun].at("root_ids").get_to(root_ids);
h.query(min_depth, max_depth, names, ids, root_ids);
} else {
std::cout << h.fail << std::endl;
}
h.m_mutex.unlock();
}
```
## Compile and excute
```shell
make clean
make
../test_client_darwin ./debug/bin/hierarchy
```
## References
[Combination of Id-ParentId and HierarchyId Approaches to Hierarchical Data](https://www.codeproject.com/Articles/1192607/Combination-of-Id-ParentId-and-HierarchyId)
[Creating a hierarchy from parent child relationship](https://stackoverflow.com/questions/67740271/creating-a-hierarchy-from-parent-child-relationship)
Sign in with Wallet
Connect another wallet