Microsoft Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 6 vote

I think this might work.

#include<iostream>
using namespace std;
class node;

class node
{
    public:
    int data;
    node *left;
    node *middle;
    node *right;

    node(int val)
    {
        data = val;
        left = middle = right = NULL;
    }
};


node * create_list(node *tnode, node *tnode2)
{
    if(!tnode) return NULL;
    tnode2 = tnode;
    tnode2->left = create_list(tnode->left, tnode2);
    while(tnode2->left)
    tnode2 = tnode2->left;
    tnode2->left = create_list(tnode->middle, tnode2);
    while(tnode2->left)
    tnode2 = tnode2->left;
    tnode2->left = create_list(tnode->right, tnode2);
    return tnode;
}

int main()
{
    node *root = NULL;

    root = new node(10);
    root->left = new node(6);
    root->middle = new node(9);
    root->right = new node(13);
    root->left->left = new node(7);
    root->left->middle = new node(8);
    root->left->right = new node(5);

    root = create_list(root, root);

    while(root)
    {
        cout<<root->data<<'\n';
        root = root->left;
    }

    return 0;
}

- Tushar January 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

calling any thing recursively is using extra space on stack, although you didn't explicitly allocate them

- chk June 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 11 vote

Solution by Stanford professor -

cslibrary.stanford.edu/109/TreeListRecursion.html

- Vinit January 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is for a binary tree

- raktunc January 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome!

- Anonymous January 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

Java code:

public static TernaryTreeNode toList(TernaryTreeNode head) {
		if (head == null)
			return null;
		
		head.left = toList(head.left);
		head.middle = toList(head.middle);
		head.right = toList(head.right);
		
		TernaryTreeNode newHead;
		
		if (head.left != null) {
			head.left = join(head.left, head.middle);
			newHead = head.left;
		} else {
			newHead = head.middle;
		}
		
		if (head.middle != null) {
			head.middle = join(head.middle, head.right);
		} else if(head.left != null) {
			head.left = join(head.left, head.right);
		} else {
			newHead = head.right;
		}
		
		if(head.right != null) {
			head.right = join(head.right, head);
		} else if (head.middle != null) {
			head.middle = join(head.middle, head);
		} else if (head.left != null) {
			head.left = join(head.left, head);
		} else {
			newHead = head;
		}
		
		head.left = null;
		
		return newHead;
		
	}

	private static TernaryTreeNode join(TernaryTreeNode node1, TernaryTreeNode node2) {
		if (node1 == null) return null;
		
		if(node1.left != null) {
			node1.left = join(node1.left, node2);
		} else {
			node1.left = node2;
		}
		
		return node1;
}

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

Any order in which the linked list has to be formed ??

- Sen January 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are only allowed to use left pointer

- sonesh January 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Ternary {

	int data;
	Ternary left = new Ternary();
	Ternary right = new Ternary();
	Ternary child = new Ternary();
	
	public Ternary convert(Ternary root, Ternary tail){
		Ternary currNode;
		
		currNode = root;
		while(currNode.right!=null){
			if(currNode.child!=null){
				currNode.child.left = tail;
				while(currNode.child.right!=null){
					currNode = currNode.right;
				}
				tail = currNode.right;
			}
			currNode = currNode.right;
		}
		return currNode;
          }

}

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

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *left,*middle,*right;
};

struct node *newNode(int data)
{
struct node *temp=(struct node *)malloc(sizeof(struct node));
temp->data=data;
temp->left=temp->middle=temp->right=NULL;
return temp;
}

void ternaryTreetoLL(struct node *root,struct node **prev)
{
if(root==NULL)
return;
ternaryTreetoLL(root->left,prev);
root->left=*prev;
(*prev)=root;
ternaryTreetoLL(root->middle,prev);
ternaryTreetoLL(root->right,prev);
}

void printList(struct node *head)
{
if(head==NULL)
return;
while(head!=NULL)
{
printf("%d ",head->data);
head=head->left;
}
}

int main()
{
struct node *root=newNode(10),*prev=NULL;
root->left=newNode(6);
root->middle=newNode(9);
root->right=newNode(13);
root->left->left=newNode(7);
root->left->middle=newNode(8);
root->left->right=newNode(5);
ternaryTreetoLL(root,&prev);
printList(prev);
getchar();
return 0;
}

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

Run a BFS and on popping each node from the queue, add it to the linked list. BFS can run either in recursive or explicit queue.

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

without using extra space

- sonesh February 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static TernaryTreeNode toList(TernaryTreeNode head) {
		if (head == null)
			return null;
		
		head.left = toList(head.left);
		head.middle = toList(head.middle);
		head.right = toList(head.right);
		
		TernaryTreeNode newHead;
		
		if (head.left != null) {
			head.left = join(head.left, head.middle);
			newHead = head.left;
		} else {
			newHead = head.middle;
		}
		
		if (head.middle != null) {
			head.middle = join(head.middle, head.right);
		} else if(head.left != null) {
			head.left = join(head.left, head.right);
		} else {
			newHead = head.right;
		}
		
		if(head.right != null) {
			head.right = join(head.right, head);
		} else if (head.middle != null) {
			head.middle = join(head.middle, head);
		} else if (head.left != null) {
			head.left = join(head.left, head);
		} else {
			newHead = head;
		}
		
		head.left = null;
		
		return newHead;
		
	}

	private static TernaryTreeNode join(TernaryTreeNode node1, TernaryTreeNode node2) {
		if (node1 == null) return null;
		
		if(node1.left != null) {
			node1.left = join(node1.left, node2);
		} else {
			node1.left = node2;
		}
		
		return node1;
}

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

/* 
	Might be easier to consider 'left' as the 'next' in the tree and just
	move middle and right to left most node while traversing left one at a time.
	Algo: 
	 Traverse left and find the left most leaf
	 current node = root
	 Till there are no nodes left on the leftside
	   do this for both middle and right
			Add middle to the left most leaf
			Add right to the left most leaf
	   move current one node left
*/

// Adds a given node to the left most 
NODE *AddToLeftEnd(NODE *root, NODE *node)
{
	while (root->left)
	{
		root = root->left;
	}
	root->left = node;

	return root;
}

// root becomes 'head' with list linked via 'left' when function returns
void TernaryToList(NODE *root)
{
	NODE *end = root, *curr = root;

	while (curr)
	{
		if (curr->middle) {
			end = AddToLeftEnd(end, curr->middle);
		}
		if (curr->right) {
			end = AddToLeftEnd(end, curr->right);
		}

		// Move to next node on left
		curr = curr->left;
	}
}

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

Complete running code in java ::




public class TernaryTree2DLL{
// Demonstrate tree->list with the list 1..5
public static void main(String[] args) {


//-------------------------------------------
BTOperation ob=new BTOperation();

TernaryTreeNode r5 = new TernaryTreeNode(5);
TernaryTreeNode r6 = new TernaryTreeNode(6);
TernaryTreeNode r7 = new TernaryTreeNode(7);
TernaryTreeNode r8 = new TernaryTreeNode(8);
TernaryTreeNode r9 = new TernaryTreeNode(9);
TernaryTreeNode r10 = new TernaryTreeNode(10);
TernaryTreeNode r11 = new TernaryTreeNode(11);
TernaryTreeNode r12 = new TernaryTreeNode(12);
TernaryTreeNode r13 = new TernaryTreeNode(13);

TernaryTreeNode r2 = new TernaryTreeNode(2,r5,r6,r7);
TernaryTreeNode r3 = new TernaryTreeNode(3,r8,r9,r10);
TernaryTreeNode r4 = new TernaryTreeNode(4,r11,r12,r13);
TernaryTreeNode root = new TernaryTreeNode(1, r2, r3, r4);


// ob.treeInsert(root,16);
// ob.treeInsert(root,18);
// ob.treeInsert(root,17);
// ob.treeInsert(root,20);
// ob.treeInsert(root,6);
// ob.treeInsert(root,7);
// ob.treeInsert(root,3);
// ob.treeInsert(root,13);
// ob.treeInsert(root,9);
// ob.treeInsert(root,2);
// ob.treeInsert(root,4);
//-------------------------------------------


System.out.println("tree:");
// ob.printTree(root); // 1 2 3 4 5
// System.out.println();


System.out.println("Inorder traversal of tree:");
ob.inOrderTree(root);


TernaryTreeNode head = ob.treeToList(root); // treeToDLL(root);
// TernaryTreeNode head = ob.toList(root);
System.out.println("DLL traversal: ");
ob.printList(head); // 1 2 3 4 5 yay!

}
}
class TernaryTreeNode
{
int data;
TernaryTreeNode left;
TernaryTreeNode middle;
TernaryTreeNode right;

public TernaryTreeNode(int v)
{
this.data=v;
}

public TernaryTreeNode(int v , TernaryTreeNode small, TernaryTreeNode middle , TernaryTreeNode large) {
this.data=v;
this.left = small;
this.middle = middle;
this.right=large;
}

}
class BTOperation {

public TernaryTreeNode treeToList(TernaryTreeNode root)
{
// base case: empty tree -> empty list
if (root==null)
return(null);

// Recursively do the subtrees (leap of faith!)
TernaryTreeNode aList = treeToList(root.left);
TernaryTreeNode bList = treeToList(root.middle);
TernaryTreeNode cList = treeToList(root.right);

// Make the single root node into a list length-1
// in preparation for the appending
root.left = root;
root.right = root;

// At this point we have three lists, and it's
// just a matter of appending them together
// in the right order (aList, root, bList)

aList=append(aList, bList);
aList=append(aList, cList);
aList = append(aList,root );


// root = append(root, bList);


return(aList);
}


public TernaryTreeNode append(TernaryTreeNode a, TernaryTreeNode b)
{
// if either is null, return the other
if (a==null) return(b);
if (b==null) return(a);

// find the last node in each using the .previous pointer
TernaryTreeNode aLast = a.left; // small;
TernaryTreeNode bLast = b.left; // small;

// join the two together to make it connected and circular
join(aLast, b);
join(bLast, a);

return(a);
}

public void join(TernaryTreeNode a, TernaryTreeNode b) {
a.right = b;
b.left = a;
}



/*
Given a non-empty tree, insert a new node in the proper
place. The tree must be non-empty because Java's lack
of reference variables makes that case and this
method messier than they should be.
*/
public void treeInsert(TernaryTreeNode root, int newData) {
if (newData<=root.data)
{
if (root.left!=null)
treeInsert(root.left, newData);
else
root.left = new TernaryTreeNode(newData);
}
else
{
if (root.right!=null)
treeInsert(root.right, newData);
else
root.right = new TernaryTreeNode(newData);
}
}


// Do an inorder traversal to print a tree
// Does not print the ending "\n"
public void printTree(TernaryTreeNode root) {
if (root==null) return;
printTree(root.left);
System.out.print(root.data+ " ");
printTree(root.right);
}


// postorder travseral of tree
public void inOrderTree(TernaryTreeNode root)
{
if(root==null) return;


inOrderTree(root.left);
inOrderTree(root.middle);
inOrderTree(root.right);
System.out.print(root.data+" ");

}



// Do a traversal of the list and print it out
public void printList(TernaryTreeNode head) {
// System.out.println(" head :: " + head.right.right.data);
TernaryTreeNode current = head;

while (true)
{
System.out.print(current.data + " ");

current = current.right;

if(current==head)
{
break;
}
}

System.out.println();
}


}

- codeAddict March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 4 vote
To create a singly linked list you need another structure {{{ struct listnode { treenode* node; listnode* next; }; and the with this structure you can make header = null, and the traverse the tree in any order you want, for example "inorder" and add every node you check to the list. - Franky January 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The problem mentions that "Without using extra space". :-)

- SauR January 05, 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