Skip to content

Instantly share code, notes, and snippets.

@furf
Created July 13, 2019 15:59
Show Gist options
  • Save furf/7f2051c8ccff040dde2c2b521902c2d9 to your computer and use it in GitHub Desktop.
Save furf/7f2051c8ccff040dde2c2b521902c2d9 to your computer and use it in GitHub Desktop.
Coding challenge for constructing and traversing (depth-first) trees.
// Found at https://www.glassdoor.com/Interview/Reddit-Senior-Software-Engineer-Interview-Questions-EI_IE796358.0,6_KO7,31.htm
// # a list of strings.Each string is a management / report relationship.
// #
// # EXAMPLE INPUT:
// #
// #[
// # 'B,E,F',
// # 'A,B,C,D',
// # 'D,G,I',
// # 'G,H'
// #]
// So, write some code(pseudo or language of your choice, including SQL) for the following:
// A is the manager of B, C, D.B is the manager of E and F, and so forth.
// # EXAMPLE OUTPUT:
// #
// # A
// # ....B
// # ........E
// # ........F
// # ....C
// # ....D
// # ........G
// # ............H
// # ........I
/**
* Node
*/
class Node {
constructor(id) {
this.id = id;
this.parent = null;
this.children = [];
}
appendChild(node) {
if (node.parent) {
node.parent.removeChild(node);
}
this.children = this.children.concat(node);
node.parent = this;
}
removeChild(node) {
if (node.parent !== this) {
return;
}
this.children = this.children.filter(child => child !== node);
node.parent = null;
}
}
/**
* Document
*/
class Document {
constructor() {
this.nodes = {};
this.root = new Node();
}
findNode(id) {
return this.nodes[id] || null;
}
createNode(id) {
const node = new Node(id);
this.nodes[id] = node;
this.root.appendChild(node);
return node;
}
}
/**
* DocumentBuilder
*/
class DocumentBuilder {
constructor(document) {
this.document = document;
}
build(structures) {
const doc = this.document;
structures.forEach(structure => {
const [parentId, ...childrenIds] = structure.split(',');
// Find or create parent Node.
const parent = doc.findNode(parentId) || doc.createNode(parentId);
childrenIds.forEach(childId => {
// Find or create child Node.
const child = doc.findNode(childId) || doc.createNode(childId);
parent.appendChild(child);
});
});
}
}
/**
* DocumentTraverser
*/
class DocumentTraverser {
constructor(document) {
this.document = document;
}
traverse(callback) {
this.traverseNode(this.document.root, 0, callback);
}
traverseNode(node, level, callback) {
node.children.forEach(child => {
callback(child, level);
this.traverseNode(child, level + 1, callback);
});
}
}
/**
* DocumentRenderer
*/
class DocumentRenderer {
constructor(document) {
this.traverser = new DocumentTraverser(document);
}
render() {
this.traverser.traverse(this.renderNode);
}
renderNode(node, level) {
const indentation = '....'.repeat(level);
console.log(`${indentation}${node.id}`);
}
}
/**
* main
*/
const document = new Document();
const builder = new DocumentBuilder(document);
const renderer = new DocumentRenderer(document);
const data = [
'B,E,F',
'A,B,C,D',
'D,G,I',
'G,H',
];
builder.build(data);
renderer.render();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment