Akamai Interview Question for SDE-2s


Country: India
Interview Type: Phone Interview




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

6
4 8
3 5 7 9
ps={3547986}
nodetye={LLILLII}
Algo for creating binary tree

if(nodetype.length == 1){ // array has only one element hence it is head
return ps[0];
}
//iterate thrugh array and if nodetype is 'L' push it into stack , else pop last two elements from the stack and make it as right and left child of the current element push current element on to stack , in the end only root will be in the stack
for(int i=0; i < nodeType.lenght;i++){
	if(nodeType[i]=='L'){
	stack.push(ps[i]);
	}else{
	node right = stack.pop();
	node left=stock.pop();
	node element=ps[i];
	element.right=right;
	element.left=left;
	stack.push(element);
	}
}

return stack.pop();
}

- rohit mathur November 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

6
4 8
3 5 7 9
{3547986}
{LLILLII} // I dont find any use for this information , probably can be used for data verification
{0 - n-1}
top=n-1

constructBTree(post[n])
{
top=n-1;
root=post[top];
if(size(post) == 1)
return root;
if(z)
leftTop=top-1;
while(root < post[leftTop] && leftTop != 0)
leftTop--;
if(leftTop != 0)
root->left = constructBTree(post[0....leftTop-1]);
else
root->left = null;

if(leftTop < top-1)
root->right = constructBTree(post[leftTop....top-1]);
else
root->right = null;
}

- ultimatecoder July 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If I am correct, we will be given a post order tree like below:
LLILLII or LLILLILLIII.

For this they have given a condition that a node can have 0 or 2 children compulsory.

Algo for constructing a BinaryTreeNode in Java Language :

BinaryTreeFromPostOrder(char[] A, int i){

	if(A == null){
		return null;
	}

	BinaryTreeNode new Node = new BinaryTreeNode();
	newNode.setData(A[i]);
	newNode.setLeft(null);
	newNode.setRight(null);

	if(A[i] == 'L'){
		return newNode;
	}

	i = i - 1;
	newNode.setRight(BuildTreeFromPostOrder(A,i));
	
	i = i - 1;
	newNode.setLeft(BuildTreeFromPostOrder(A,i));
	
	return newNode;

}

Call this method with BinaryTreeFromPostOrder(A, A.length-1);


Let me know if I did any thing wrong or if I understood the question wrongly.

Thanks,
Ranjith

- u.ranjith August 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

If you are give the postfix in an array in the form like
a[]={i,i,n,i,n,n} and another array that denotes the node like
b[]={2,3,4,5,6,7} then you can make the binary tree using recursion as:

tree *makeBinaryTree(char a[],int b[],int *index,int n)
{
	int indx=*index;
        if(indx==n)
            return NULL;
	tree *n=makeNewNode(a[indx]);
	*index++;
	if(b[indx]=='i')
	{
		n->left=makeBinaryTree(n,a,b,index);
		n->right=makeBinaryTree(n,a,b,index);
	}
	return n;
}

- vgeek July 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

hi vgeek it seems that makeBinaryTree() is missing one more parameter, i.e., the 1st parameter, seems tree* type.

- S@iR@m July 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No its right but i have added one termination condition that was not there earlier.

- vgeek July 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is wrong.

lets take an example L L i (L=leaf and i=intermediate node)

first it creates new node for arr[0] (L), next again arr[1] here it is not 'i', so it returns

- algos July 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think that the array when making a tree is such that first you will be given the non leaf nodes followed by the leaf nodes as then it would not be possible to make an accurate relation between the parent node and the child node.

- vgeek July 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

if given array is post-order then start processing from end of the array and first insert right child and then left child

if given array is pre-order then start processing from start of the array and first insert left child and then right child

initially sz = length of array - 1 (for given post-order array)

void insert(node **root, char arr[], int &sz)
{
	*root = new node;
	(*root)->data = arr[sz];
	(*root)->left = (*root)->right = NULL;

	if(arr[sz] == 'i')
	{
		insert(&(*root)->right, arr, --sz);
		insert(&(*root)->left, arr, --sz);
	}
}

- algos July 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

First of all let me clarify the question: my understanding is that the tree generated by *postorder* traversal is given by the "i"-"l" array (or what exactly does the post-fix mean here?). If this understanding is correct, the following is my solution.

First of all it is easy to see that the last element of the array is the root. Then the difficulty in the recursive call is to separate the left subtree from the right subtree. To do so note that any tree has (number of "i") == (number of "l") - 1, therefore we can scan from the 2nd from the last element backwards and count the number of "i" and "l", until we have the condition (number of "i") == (number of "l") - 1 satisfied, and this will be the right subtree, and the rest is the left subtree.

- Chih.Chiu.19 July 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

All right if it is a post-order solution then your approach seems to be correct. I also thought about the post-fix thing but then i made a mistake by just considering it to be a normal array of non leaf nodes followed by leaf nodes

- vgeek July 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@vgeek
Thanks for the reply, but two questions for you:

1) Could the word "post-fix" possibly mean something else here? I really don't know... I looked it up and it seems to me it is only used when representing an algebraic expression, so I assume it is the "post-order" that should be used here.

2) If I am correct, why do I get two "-1"? LOL

- Chih.Chiu.19 July 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

No it means only post-order here postfix means nothing here...same with me -2 although i was mistaken by the word postfix ...LOL

- vgeek July 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Steps: (Let p and q be start and end position in postorder array)
1. Since the last element is root. we need to create a node postorder[r];
2. q=(p+r)/2;
3. Left subtree (postorder[1...q-1])
4 Right subtree(postorder[q+1 ... r])
The mistake I did was while constructing the tree , I had forgotten create the node at base case. Now I have rectified it . Attaching my code.

void construct_tree_postorder(int *postorder,int p,int r,struct node** tree)
{
    int x=postorder[r];
    if(r<p)
        return;
    if(r==p) // base case only root
    {
        (*tree)=create_a_node(postorder[r]);
         return;
    }
    else
    {
        int q = (p+r-1)/2;
        (*tree)=create_a_node(postorder[r]);
        construct_tree_postorder(postorder,q+1,r-1,&((*tree)->right));
        construct_tree_postorder(postorder,p,q,&((*tree)->left));
        return;
    }
}

- pras July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

LOLz .. interpreted the question wrongly .. please down vote it

- pras July 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sure, I can do it for ya, I love down-voting!

- Anonymous July 24, 2013 | Flag


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