Amazon Interview Question
Software Engineer / Developers/*
Just for fun, we can use Parsing concepts for this problem.
An attempted Recursive Descent Parser for something similar to following Grammar.
Tree : ( TreeList )
TreeList : Data TreeList | Tree TreeList | Empty
*/
// The tree object created as a result of Parsing.
public class Tree {
private object _data;
private List <Tree> _children;
public object Data {
get { return _data;}
set {_data = value;}
}
public Tree() {
_children = new List <Tree> ();
}
public void AddChild(Tree child) {
_children.Add(child);
}
}
// The Parser Class.
// With some error checking.
public static class TreeParser {
public static Tree Parse(String s) {
StringTokenizer tokenizer = new StringTokenizer(s);
Tree tree = new Tree();
Tree(tokenizer, tree);
Token t = tokenizer.GetNext();
if (t != Token.End) {
ParseError("Trailing Junk");
return null;
}
return tree;
}
private static void Tree(StringTokenizer tokenizer, Tree tree) {
Tree curTree = new Tree();
Token t = tokenizer.GetNext();
if (t != Token.LeftBracket) {
ParseError("Missing Left Bracket");
return;
}
TreeList(tokenizer, curTree);
Token t = tokenizer.GetNext();
if (t != Token.RightBracket) {
ParseError("Missing Right Bracket");
return;
}
tree.AddChild(curTree);
}
private static void TreeList(StringTokenizer tokenizer, Tree tree) {
Token t = tokenizer.PeekNext();
if (t == Token.Data) {
Data(tokenizer, tree);
TreeList(tokenizer, tree);
}
if (t == Token.LeftBracket) {
Tree(tokenizer, tree);
TreeList(tokenizer, tree);
}
return;
}
private static void Data(StringTokenizer tokenizer, Tree tree) {
Tree leafNode = new Tree();
Token t = tokenizer.GetNext();
leafNode.Data = t.GetData();
tree.AddChild(leafNode);
}
private static void ParseError(string msg) {
throw new ParseErrorException(msg);
}
}
internal enum Token {LeftBracket, RightBracket, Data, End};
// Use your own.
internal class StringTokenizer {
// Peeks at next token without consuming.
public Token PeekNext();
// Consumes Token.
public Token GetNext();
// Returns data Associated with last consumed Token.
public object GetData();
}
The idea is straight forward. Just recursively scan through the input string. When meeting a "(", start to deal with a node; when meeting ")", the current node is ready to deal with children.
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Node{
string data;
vector<Node*> children;
bool visited;
public:
Node(string d = ""):data(d){visited = false;}
void setData(string d){data = d;}
string getData()const {return data;}
void addChild(Node *n){
children.push_back(n);
}
void printTree() const;
};
//Depth first search
void Node::printTree() const{
cout << data << endl;
vector<Node*>::const_iterator it;
for(it=children.begin(); it < children.end(); it++){
if((*it)->visited) continue;
(*it)->visited = true;
(*it)->printTree();
}
}
Node *opTree(string input){
static int i = 0;
if(input.at(i) == '('){
string key = "";
Node * node = new Node();
bool keyDone = false;
i++;
for(; i < input.length();){
if(input.at(i) == '('){//next level recursion
keyDone = true;
node->setData(key);
node->addChild(opTree(input));
}else if(input.at(i) == ')'){
keyDone = true;
node->setData(key);
i++;
}else{
if(!keyDone)
key.push_back(input.at(i));
i++;
}
}
return node;
}else{
return NULL; //actually, this is an exception
}
}
int main(int argc, char **argv){
string str = string(argv[1]);
Node *root = opTree(str);
root->printTree();
delete root;
}
Hi all,
I got this idea. We create struct with data and parent field(can be a pointer to struct).When a "(" is encountered create a node,insert data(after "(" ),and set the parent.But when a ")" is encountered move a step back(that is to parent)using pointer. Root will have parent pointer NULL.
One way to solve this can be like this:
1) When ever you encounter '(', this is the currentNode and is the parent of forthcoming children nodes.
2) When you encounter ')', jump to one level up the hierarchy, i.e. currentNode->Parent and start forming the Tree
Yea I guess I have same algo as what u specified. Just correct me in case I go wrong.
I have tried implementing in an iterative way.
public void createNaryTree(String s)
{
Node n ;
for(int i=0; i< s.length() ; i++)
{
if(s[i] == '(' )
{
// Create a Node in Existing node
if( n == NULL)
{
// Create 1st Node
n = new Node();
}
else
{
// Add child to existing node
// This method will create a child node and will return it's reference
n = n.createChild(this);
}
}
else if(s[i] == ')' )
{
// when Closing bracket is encountered
// Get Parent will return the reference of Node's parent
n = n.getParent();
}
else
{
n.setValue(s[i]); // When alphabet is encountered
}
}
}
Thanks and Regards
struct Node
{
char value;
Node * child [n];
}
we have to call the funtion
constructTree(rootnode, stringinput, 0) to create the tree
boolean constructTree(Node *n, char *c, int i)
{
if(*(c+i) == '/0')
return false;
if(*(c+i) == '(')
{
char ch = *(c+i+1);
n =new Node;
n->value = ch;
/* here initialize all children of n as null */
int s=0;
while(constructTree(n->child[s++], c, i+2));
return true;
}
else if (*(c+i) = ')')
return false;
}
Here's the solution for Java.. I *think* it works:
static class Node {
char c;
Node parent;
Set<Node> children = new HashSet<Node>();
}
public static Node buildTree(String tree) {
Node current = new Node();
char[] treec = tree.toCharArray();
for(int i=0; i<treec.length; i++) {
if(treec[i] == '(') {
Node n = new Node();
n.parent = current;
current.children.add(n);
current = n;
} else if(Character.isLetter(treec[i])) {
current.c = treec[i];
} else if(treec[i] == ')') {
current = current.parent;
}
}
return current;
}
this is the working and tested code in CPP [for binary tree], you can easily modify this to suite it for n-ary tree:
void makeBTree(string givenString)throw() {
stack<Node *> nodeStack;
Node *temp;
int ix=0;
while(givenString[ix] !='\0') {
if (isalnum(givenString[ix])) {
temp = new Node;
temp->data = givenString[ix] - '0';
temp->left = NULL;
temp->right = NULL;
nodeStack.push(temp);
}
if (givenString[ix]==')' && nodeStack.size()>1) {
temp = nodeStack.pop();
Node *last = nodeStack.pop();
if (last->left == NULL) {
last->left = temp;
} else if (last->right == NULL) {
last->right = temp;
}
nodeStack.push(last);
}
ix++;
}
// string over, pop the top element as the root of the BTree
this->root = nodeStack.pop();
}
enjoy guys !
void parsing(BT b, String S)
{
if(S.charAt(0) == '(')
{
S = S.substring(1);
parsing(b, S);
}
if(S.charAt(0) == ')')
{ S = S.substring(1);
return;
}
else
{
BT c = new BT(S.charAt(0));
b =c;
S = S.substring(1);
if(S.charAt(0) == ')')
{ S = S.substring(1);
return;
}
else if(S.charAt(0) == '(')
{
S = S.substring(1);
BT d = new BT('0');
parsing(d, S);
b.child.add(d);
}
}
}
The problem looks quite simple:
- Anonymous January 14, 2009I will use stack for this problem.
1] First check if opening paranthesis, if yes then create a node with the element that just follows this and push it onto stack. This now becomes top of stack.
2] While stack is not empty:
parse the string,
if the character is open paranthesis, then just increment to next location which contains the character. make a node and make it child of current top of stack. then push this new node on the top of stack.
3] if the character is close paranthesis. just pop top of stack and do nothing.