iLabs Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




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

#include <malloc.h>

#define QUEUE_SIZE 100

struct tree
{
	int data;
	struct tree *left, *right;
};

struct queue 
{
	struct tree *nodes[QUEUE_SIZE];
	int front,rear;
};

void printLevelOrder(struct tree *root)
{
	struct queue *Q = (struct queue *) malloc(sizeof(struct queue));
	struct tree *P;
	queueInit(Q);
	queueAdd(Q, root);
	queueAdd(Q, NULL);
	
	while(!queueEmpty(Q))
	{
		P = queueDel(Q);
		if(P == NULL)
		{
			if(queueEmpty(Q))
				return;
			printf("\n");
			queueAdd(Q, NULL);
		}
		else
		{
			printf("%d,",P->data);
			if(P->left != NULL)
				queueAdd(Q, P->left);
			if(P->right != NULL)
				queueAdd(Q, P->right);
		}
	}
}

/* Queue functions */
void queueInit(struct queue *Q)
{
	Q->front = Q->rear = -1;
}

void queueAdd(struct queue *Q, struct tree *node)
{
	if((Q->front+1)%QUEUE_SIZE == Q->rear)
	{
		printf("\n Queue is full");
	}
	else
	{
		Q->front = (Q->front + 1)% QUEUE_SIZE;
		Q->nodes[Q->front] = node;
		if(Q->rear == -1 )
		{
			Q->rear = 0;
		}
	}
}

struct tree * queueDel(struct queue *Q)
{
	if( Q->rear == -1)
	{
		printf("\n queue is empty ");
		return NULL;
	}
	else
	{
		struct tree *temp = Q->nodes[Q->rear];
		Q->rear = (Q->rear + 1) % QUEUE_SIZE;
		/* Queue is empty */
		if(Q->rear > Q->front)
		{
			Q->front = Q->rear = -1;
		}
		return temp;
	}
}

int queueEmpty(struct queue *Q)
{
	return Q->rear == -1 ? 1 : 0 ;
}

- siva.sai.2020 April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it seems, I wringly used front & rear indexes

- siva.sai.2020 March 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

my solution was


void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for(i=1; i<=h; i++)
printGivenLevel(root, i);
}


void printGivenLevel(struct node* root, int level)
{
if(root == NULL)
return;
if(level == 1)
printf("%d ", root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}


what will be complexity in case of balance binary tree .

in worst case it will be O(n)

- anuj.aj07 April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In any case you will need to visit every node once O(n) is the best that can be achieved.

In the above case the worst case complexity would be O(n^2)

To do it in O(n) use queues for level order traversal.

- Expressions April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for each level i am traversing the all the nodes till d-1 level.

so if height of the tree is h

level 0 --root node will be traverse h+1 time
level-1--- h time

level h ----- 1 time

so it will be like

(h+1) + 2 h + 2^1 (h-1) + 2^2 (h-2) +...........2^h

how to solve this now

- anuj.aj07 April 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the simplest way is to do it iteratively rather than recursively. In pseudo-code:

Set <Node> nodesToVisit = new HashSet();
nodesToVisit.add(root);
int levelAt = 0;
while(nodesToVisit.size() != 0)
{
	Set <Node> nextNodesToVisit = new HashSet();
	for(Node node : nodesToVisit)
	{
		System.out.print(node.getValue() + ", ");
		if(node.hasLeft())
			nextNodesToVisit.add(node.getLeft());
		if(node.hasRight())
			nextNodesToVisit.add(node.getRight());
	}
	System.out.println();
	nodesToVisit = nextNodesToVisit;
}

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

here you go:

public void TraverseNode(Node node)
        {
            Queue<Node> queue = new Queue<Node>();
            if (node == null)
                return;
            int nodesInCurrentLevel = 1; int nodesInNextLevel = 0;
            queue.Enqueue(node);
            while (queue.Count > 0)
            {
                Node nodeToTraverse = queue.Dequeue();
                if (nodeToTraverse.Left != null)
                { 
                    queue.Enqueue(nodeToTraverse.Left); nodesInNextLevel++; 
                }
                if (nodeToTraverse.Right != null)
                { 
                    queue.Enqueue(nodeToTraverse.Right); nodesInNextLevel++; 
                }
                Console.Write(nodeToTraverse.Data);
                nodesInCurrentLevel--;
                if(nodesInCurrentLevel == 0)
                {
                    Console.WriteLine();
                    nodesInCurrentLevel = nodesInNextLevel;
                    nodesInNextLevel = 0;
                }
            }
        }

And since you have to print each node, you have to traverse each node and you always do that so the complexity will be O(n).

- vj April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i am not looking for other solutions plese tell complexity for solutions i given........

- anuj.aj07 April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am assuming you gave the solution by finding the height and then
calling the print function for each level.
The complexity is O(n logn) assuming there are n levels.
because at every iteration you are going to a particular level which is (log n)
and you are doing this for n levels

- amber April 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void printLevel(Node root)
	{
		if(root==null)
			return;
		Queue q=new Queue();
		q.enqueue(root);
		q.par_num++;
		while(q.size()>0)
		{
			Node temp=q.dequeue();
			if(temp.left!=null)
				q.enqueue(temp.left);
			if(temp.right!=null)
				q.enqueue(temp.left);
			if(q.par_num==0)
				q.printQueue();
			q.par_num=q.child_num;
			q.child_num=0;
		}
	}


class Queue
{
	LinkedList<Node> list;
	int child_num, par_num;
	Queue()
	{
		list=new LinkedList<Node>();
		child_num=0;
		par_num=0;
	}
	
	public void enqueue(Node item)
	{
		child_num++;
		list.addLast(item);
	}
	
	public Node dequeue()
	{
		par_num--;
		if(list.size()==0)
			return null;
		else
			return list.removeFirst();
	}
	
	public int size()
	{
		return list.size();
	}
	
	public void printQueue()
	{
		System.out.println();
		for(int i=0;i<list.size();i++)
		{
			Node temp=list.get(i);
			System.out.print(temp.value);
		}
	}
	
}

class Node
{
	Node left;
	Node right;
	int value;
	
	Node(Node left, Node right, int value)
	{
		this.left=left;
		this.right=right;
		this.value=value;
	}
	
}

- north_remembers April 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have used two integers, child_num and par_num to keep a track of parents and children.
when parents ==0, which means only children are present in the queue, we print.

- north_remembers April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inorder traversal and strore each line in a separate list. On the end, print the lists. Time complexity O(n), space compexity O(n).

Trivial approach starting for each level from beginngin has O(n log n) for balanced tree, as it is log n levels and printing a level needs o(n) speps.

- tpcz April 03, 2013 | 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