Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

case class NaryNode(v: Int, var children: Vector[NaryNode])

  def Traverse(root: NaryNode) = {
    def recurse(prev: NaryNode, current: NaryNode): Unit = {
      if (current == null) return
      if (prev == null) current.children = current.children :+ null

      if (current.children.filter(_ == prev).length != 0 ||
        current.children.length == 1) { 
        // if the prev node is one of the child of current, then
        // it means all children have been visited. Now visit current node.
        
        // if current node has no children, then visit current node
        
        // ==1 because we add one pointer to the children Vector 
        // for pointing to the current node's sibling.
        println(current.v)
        
        // visit the current node's sibling
        recurse(current, current.children(current.children.length - 1))
      } else {
        // connect the children into a singular link list.
        for (i <- 0 to current.children.length - 2) {
          current.children(i).children = current.children(i).children :+ current.children(i + 1)
        }
        
        // connect the last child back to the current node.
        current.children(current.children.length - 1).children =
          current.children(current.children.length - 1).children :+ current
        
        // now visit the current node's first child.
        recurse(current, current.children(0))
      }
    }

    recurse(null, root)
  }

- jiangok2006 September 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NArrTreeTraversalModified {

    private static class NArrTreeNodeModified {
        int val;
        ArrayList<NArrTreeNode> children;
        boolean canVisit;

        public NArrTreeNode(int value) {
            val = value;
            children = new ArrayList<>();
        }
    }

    public ArrayList<Integer> postOrderTraversal(NArrTreeNodeModified root) {
        ArrayList<Integer> result = new ArrayList<>();
        Stack<NArrTreeNodeModified> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            NArrTreeNodeModified node = stack.peek();
            if (node.children.size() == 0 || node.canVisit) result.add(stack.pop().val);
            else {
                node.children.forEach(n -> stack.push(n));
                node.canVisit = true;
            }
        }
        return result;
    }

}

- rsrs3 September 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct node
{
	int data;
	int noc;
	node **child; 
};
node *getDummyNode()
{
	node *N=new node;
	N->data=-1;
	return N;
}
void printPostOrder(node *T)
{
	stack<node *> s1,s2;
	s1.push(T);
	while(!s1.empty())
	{
		node *N=s1.top();
		if(N->data==-1)
		{
			s1.pop();
			cout<<s2.top()->data<<" ";
			s2.pop();
		}
		else
		{
			s2.push(N);
			s1.pop();
			s1.push(getDummyNode());
			int s=N->noc;
			for(int i=s-1;i>=0;i--)
			{
				s1.push(N->child[i]);
			}
		}
	}
}
node *getNode(int k,int noc)
{
	node *N=new node;
	N->data=k;
	N->noc=noc;
	N->child=new node*[noc];
	for(int i=0;i<noc;i++)
	{
		N->child[i]=NULL;
	}
	return N;
}
int main()
{
	node *T=NULL;
	T=getNode(1,3);
	T->child[0]=getNode(2,3);
	T->child[1]=getNode(3,4);
	T->child[2]=getNode(4,0);
	T->child[0]->child[0]=getNode(5,0);
	T->child[0]->child[1]=getNode(6,0);
	T->child[0]->child[2]=getNode(7,0);
	T->child[1]->child[0]=getNode(8,0);
	T->child[1]->child[1]=getNode(9,0);
	T->child[1]->child[2]=getNode(10,0);
	T->child[1]->child[3]=getNode(11,0);
	printPostOrder(T);
}

- Yaduvir SIngh October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct node
{
	int data;
	int noc;
	node **child; 
};
node *getDummyNode()
{
	node *N=new node;
	N->data=-1;
	return N;
}
void printPostOrder(node *T)
{
	stack<node *> s1,s2;
	s1.push(T);
	while(!s1.empty())
	{
		node *N=s1.top();
		if(N->data==-1)
		{
			s1.pop();
			cout<<s2.top()->data<<" ";
			s2.pop();
		}
		else
		{
			s2.push(N);
			s1.pop();
			s1.push(getDummyNode());
			int s=N->noc;
			for(int i=s-1;i>=0;i--)
			{
				s1.push(N->child[i]);
			}
		}
	}
}
node *getNode(int k,int noc)
{
	node *N=new node;
	N->data=k;
	N->noc=noc;
	N->child=new node*[noc];
	for(int i=0;i<noc;i++)
	{
		N->child[i]=NULL;
	}
	return N;
}
int main()
{
	node *T=NULL;
	T=getNode(1,3);
	T->child[0]=getNode(2,3);
	T->child[1]=getNode(3,4);
	T->child[2]=getNode(4,0);
	T->child[0]->child[0]=getNode(5,0);
	T->child[0]->child[1]=getNode(6,0);
	T->child[0]->child[2]=getNode(7,0);
	T->child[1]->child[0]=getNode(8,0);
	T->child[1]->child[1]=getNode(9,0);
	T->child[1]->child[2]=getNode(10,0);
	T->child[1]->child[3]=getNode(11,0);
	printPostOrder(T);
}

- Yaduvir Singh October 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct Node {
	int val;
	int index;
	vector<Node*> children;
};

void createTree(Node *head)
{
	Node *node, *qNode;
	char ch;
	queue<Node *> q;

	cout << "Enter value of head node: ";
	cin >> head->val;
	head->index = 0;

	q.push(head);



	while (!q.empty())
	{
		qNode = q.front();
		q.pop();

		cout << "do you want to add child of " << qNode->val << "?" << endl;
		cin >> ch;

		while (ch == 'y' || ch == 'Y')
		{
			node = new Node();
			cout << "Enter value of head node: ";
			cin >> node->val;
			node->index = 0;

			qNode->children.push_back(node);
			q.push(node);
			cout << "do you want to add another child of " << qNode->val << "?" << endl;
			cin >> ch;

		}

	}
}

//Recursive solution
void postorderRec(Node *head)
{
	if (head == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	if (head->children.empty())
		cout << head->val << " ";
	else
	{
		for (vector<Node *>::iterator iter = head->children.begin(); iter != head->children.end(); iter++)
		{
			postorderRec(*iter);
		}
		cout << head->val << " ";
	}

}


//Iterative solution
void postorderiTer(Node *node)
{
	if (node == NULL)
	{
		cout << "empty tree" << endl;
		return;
	}

	stack <Node *>st;
	Node *temp;

	st.push(node);

	while (!st.empty())
	{
		temp = st.top();


		if (temp->index < temp->children.size())
		{
			node = temp->children[temp->index];
			temp->index++;
			st.push(node);
		}
		else
		{
			st.pop();
			cout << temp->val << " ";
		}

	}
	
}

int main()
{
	Node *head =  new Node();
	createTree(head);
	postorderRec(head);
	cout << endl;
	postorderiTer(head);
	return 0;
}

- diptivs December 18, 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