Linkedin Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

1. create a dummy node D
2. En queue root and D. and go into a loop until Q is not empty.
2. De queue. if De queued node is not D print node and En queue its two children (if they exist). else En queue D and print newline. repeat this step until Q is not empty.
This is called dummy node trick for En queuing and De queuing.
All comparisons to D are pointer comparisons(c/C++) or Object reference comparisons(C# java).

- Dr.Sai December 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you mean "until Q is empty"?

- pulseball January 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

what is the difference b/w this and BFS?

- Somisetty December 08, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You can just use two vectors to solve this

void printTree (treeNode *root) {
  vector<treeNode *> curr_level;
  vector<treeNode *> next_level;
  curr_level.push_back (root);
  while (curr_level.size () != 0) {
  for (int i = 0; i < curr_level.size (); i++) {
     cout << curr_level[i]->value;
     vector<treeNode *> children = curr_level[i]->children;
     for (int j = 0; j < children.size (); j++) {
       next_level.push_back (children[j]);
     }
   }
   cout << endl;
   curr_level = next_level;
   }
}

- Sandra Dai January 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

private class TreeNode{
		TreeNode left;
		TreeNode right;
		int data;
	}
	
	TreeNode root;
	
	private class NodeLevel{
		TreeNode node;
	        int level;
	    
	    NodeLevel( TreeNode n, int l ){
	        node = n;
	        level = l;
	    }
	}
	
	public void printTheTree(){
	    LinkedList<NodeLevel> list = new LinkedList<NodeLevel>();
	    int currLevel = 0;
	    if( root != null )
	        list.add( new NodeLevel( root, currLevel ) );
	    
	    while( !list.isEmpty() ){
	        NodeLevel nodeLevel = list.remove();
	        TreeNode node = nodeLevel.node;
	        if( nodeLevel.level > currLevel ){
	            System.out.println();
	            currLevel = nodeLevel.level;
	        }
	        System.out.print( node.data );

	        if( node.left != null )
	            list.add( new NodeLevel( node.left, currLevel + 1 ) );
	        if( node.right != null )
	            list.add( new NodeLevel( node.right, currLevel + 1 ) );     
	    }
	}

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

Recursively traverse the tree. When you recurse, pass a variable indicating the current level + 1. So you'd start with level 0, and when you recurse, you'd pass 1 for the level, when those calls recurse you'd pass 2, etc. Then use that number as an index into an array of sets of nodes and add the node to the set that you get (which corresponds to the index, the node's level). Finally, look at each set one at a time (each set corresponds to a level and has all the nodes from that level) and print everything in the set.

- eugene.yarovoi December 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

got asked this Q.

- yup December 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simply use a queue . start at the root push it and its children onto it . pop one element . push children of next element and pop it . continue doing like this and tada u hv ur answer

- mania1234 January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I use a simple queue along with a count.

public static void printLevelByLevelQueue(Node root) {

		Queue<Node> queue = new LinkedList<Node>();

		queue.add(root);

		while (queue.size() > 0) {
			int count = queue.size();
			while (count > 0) {
				count--;
				Node temp = queue.remove();
				System.out.print(temp.val + "  --  ");
				if (temp.left != null)
					queue.add(temp.left);
				if (temp.right != null)
					queue.add(temp.right);
			}
			System.out.println();
		}

	}

- rm March 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void printTree(TreeNode *root)
{
    vector<TreeNode *> curr_level;
    vector<TreeNode *> next_level;
    curr_level.push_back(root);
    while(curr_level.size() != 0)
    {   
        for (int i = 0; i < curr_level.size(); i++ )
        {   
            printf("%d ", curr_level[i]->val);
            if (curr_level[i]->left != NULL)
                next_level.push_back(curr_level[i]->left);
            if (curr_level[i]->right != NULL)
                next_level.push_back(curr_level[i]->right);
        }   
        printf("\n");

        curr_level = next_level;
        next_level.clear();
    }   
}

- Wchuan91 October 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

calculateheight(TreeNode root){
if(root==null){
return 0;
}else{
return 1+Math.Max(calculateheight(root.left),calculateheight(root.right));
}
}

public static void main(){
int height=caculateheight(root);
for(int level=1;level<=height;level++){
printLevel(root,level);
}
}

printlevel(TreeNode root,int level){
if(root==null){
return;
}
if(level==1){
SOP(root.data)
}
printlevel(root.left,level-1);
printlevel(root.right,level-1);
}

- Anonymous November 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

just modify the iterative way for finding the height of Binary Tree

- Anonymous July 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

<pre lang="" line="1" title="CodeMonkey78016" class="run-this">#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <queue>
#include <math.h>


using namespace std;
struct Node
{
int data ;
Node *left;
Node *right;


};

queue<Node*> Q;
queue<int> first;
void inorder(Node* root)
{
if(root->left == NULL)
{
cout<<root->data;
}
else
{
inorder(root->left);

cout<< root -> data;

inorder(root->right);
}

}

void BFS()
{
int i(0);

while(!Q.empty())
{

if(Q.size() ==pow(2,i))
{
cout<<endl;
++i;
}

cout<<Q.front()->data;
Q.push(Q.front()->left);
Q.push(Q.front()->right);
Q.pop();
getch();
}
}

int main(int argc, char *argv[])
{
Node *root, *one, *two, *three, *four, *five, *six, ;
root = new Node();
one = new Node();
two = new Node();
three = new Node();
four = new Node();
five = new Node();
six= new Node();

root->data = 0;
one->data = 1;
two->data = 2;
three->data = 3;
four->data =4;
five->data = 5;
six ->data = 6;

root->left = one;
root->right = two;

one->left = three;
one->right = four;


three->left = NULL;
three->right = NULL;

two->left = five;
two->right = six;

four ->left = NULL;
four ->right = NULL;

five ->left = NULL;
five ->right = NULL;


six ->left = NULL;
six ->right = NULL;


Q.push(root);
BFS();




getch();
return(0);

}
</pre><pre title="CodeMonkey78016" input="yes">
</pre>

- Anonymous December 06, 2011 | 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