Amazon Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 3 vote

The problem looks quite simple:

I 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.

- Anonymous January 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about a tree like ((((((a))))))

- Anonymous September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

/*

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();
}

- T March 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Bill December 23, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- kk March 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Kiran April 06, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Kiran April 06, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Kunal October 27, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- whatsinthename April 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- Anonymous April 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Fun.

- Anon May 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 !

- whatsinthename October 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good job!

- geek January 09, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}


}
}

- ABHI.AKS.SINGH June 21, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More