Google Interview Question Senior Software Development Engineers
Country: United States
Thanks for validating. Below is a JavaScript implementation of the same :
function documentTree(){
this._root = null;
};
documentTree.prototype = {
constructor : documentTree,
add : function(value,name){
var node = {
name : name,
value : value,
children : []
},
current;
if(this._root === null){
this._root = node;
}
else{
current = this._root;
while(true){
if(current.children && current.children.length===0){
current = current.children;
}
else{
current = node;
break;
}
}
}
},
insertAt : function(name, value, level){
var node = {
name : name,
value : value,
children : []
},current,i=1;
if(this._root===null){
this._root = node;
}
else{
current = this._root;
while(true){
if(i===level){
current.children.push(node);
break;
}
else if (level > i){
current = current.children;
i++;
}
else{
console.log("Node cannot be added");
break;
}
}
}
}
};
you can use the stack to create it. To represent it in stack, you can store the text as it is in the stack where each <tag_name> or </tag_name> will be become a stack element. Values inside a tag can be stored in a value tag as shown below.
</value>
text_value
<value>
<value> is the bottom of the stack. While creating the objects from the stack, parent pointer can be maintained (stored on a second stack) that signifies to which parent the current tag belongs. When the tag is completely popup from the first stack, the top pointer should be popped out from the second stack as well.
Though I have written the explanation in text but it should make sense.
Can we assume the following:
+ There are only a fixed number of tags
+ There is a max length to the number of tags in any line (including a TEXT tag)
If we assume that, can we just use a structure with an array of string pointers pointing to the respective tags?
// Tags array
char *tags[MAX_TAGS] = {"html", "body", "div", "span", "/html", "/body", "/div", "/span", "DONE"};
// input message
<html><body><div><span>TEXT1</span><br/></div></body></html>
// message encoding
char *msg[MAX_TAGS] = {
&tags[0], &tags[1], ......
};
This would optimize storage, but needs more cpu cycles to find the index into the tags[] array.
class TNode
{
public:
enum type;// text node , tag node<>, another tag node</tag> or special tag node <br />
string content;
string originalString;
};
// <html> <body> <div> <span> TEXT1 </span> <br/> </div> </body> </html>
//parse the string, and push every node in domtree
stack<TNode> domtree;
/* you could use another stack algorithm to verify the tree
stack<TNode> domtree2;
foreach(var node in domtree){
if(node.type == NodeType.tag){
domtree2.push(node);
}
else if(node.type == NodeType.atag){
TNode pair_node = domtree2.pop();
if( pair_node.content == node.content )
; // verify failed
}
}
*/
class TreeNode{
public:
TreeNode* parent;
enum type;
string content; //tagName or text
vector<TreeNode*> children;
};
typedof TreeNode *PTreeNode;
PTreeNode rootp = new TreeNode();
PTreeNode cursor = rootp;
while( !domtree.empty() )
{
TNode cur = domtree.pop();
if( cur.type == NodeType.atag ){
// create node, append it to cursor node's children, move the cursor to that node
PTreeNode newNode = new TreeNode();
cursor->children.push(newNode);
cursor = cursor->children[ cursor->children.size()-1 ];
}
else if( cur.type == NodeType.tag ){
cursor->children.reverse();
cursor = cursor->parent;
assert( cur.content == cursor->content );//don't need it if after verified
}
else{
//create text node append text;
PTreeNode newNode = new TreeNode();
cursor->children.push(newNode);
}
}
PTreeNode tree_root = rootp->children[0];
Generally speaking, you use a tree to represent hierarchical data. This is because there could be many tags inside the same tag, something that there's no direct way of representing using a linear data structure like a stack or a queue.
- Anonymous January 05, 2015