Goldman Sachs Interview Question for Software Engineer / Developers






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

using another Stack to save the immediate value, then print the Stack

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

breadth first search requires queue, and during deque, push these values in a stack.

- tetura March 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A small change to your algo , while doing BFS add the right child to the Q prior to the left child - although this is not explicitly asked in the question, but in case if it is then this must be taken care of - o.w. one will end up printing the levels from R-L

- hary March 07, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

is this kind of question has to be written in full java code or psudeo code only

- ana April 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ana: I was given a choice in C++ or Java.

- xankar July 09, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/*Function protoypes*/
void printGivenLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);

/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for(i=h; i>=1; i--)
printGivenLevel(root, i);
}

/* Print nodes at a given level */
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);
}
}

/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);

/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);

getchar();
return 0;
}

- Sachin Gupta B.tech MNNIT,allahabad @2008 July 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/*Function protoypes*/
void printGivenLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);

/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for(i=h; i>=1; i--)
printGivenLevel(root, i);
}

/* Print nodes at a given level */
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);
}
}

/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);

/* use the larger one */
if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Level Order traversal of binary tree is \n");
printLevelOrder(root);

getchar();
return 0;
}

- Sachin Gupta B.tech MNNIT,allahabad @2008 July 22, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <queue>
#include <stack>
#include <iostream>

using namespace std;

void traverseLevelOrder(btree *p)
{
	if(p == NULL)
		return;
	queue<btree*> pNodes;
	stack<btree*> allNodes;
	pNodes.push(p);
	int count;
	btree* node;
	/* add all level nodes in stack */
	while(!pNodes.empty())
	{
		count = pNodes.size();
		for(int i = 1; i <= count; i++)
		{
			node = pNodes.front();
			allNodes.push(node);
			if(node->left != NULL)
				pNodes.push(node->left);
			if(node->right != NULL)
				pNodes.push(node->right);

			pNodes.pop();
		}
	}

	while(!allNodes.empty())
	{
		cout << allNodes.top()->key << "\t";
		allNodes.pop();
	}
}

- Anonymous June 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static string TraverseBreadthFirstDepthReverse<T>(this BinaryNode<T> root)
        {
            var queue = new Queue<BinaryNode<T>>();
            var stack = new Stack<BinaryNode<T>>();
            var sb = new StringBuilder();

            queue.Enqueue(root);

            while (queue.Count > 0)
            {
                var node = queue.Dequeue();
                stack.Push(node);

                if (node.RightNode != null)
                    queue.Enqueue(node.RightNode);

                if (node.LeftNode != null)
                    queue.Enqueue(node.LeftNode);
            }

            while (stack.Count > 0)
            {
                var node = stack.Pop();
                sb.Append(node.Value);
            }

            return sb.ToString();
        }

- Den_russian August 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package goldmansach;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import main.java.algorithms.binarytree.BinaryTree;
import main.java.algorithms.binarytree.Node;

public class LevelOrderReverse {
	
	public void reverseUtil(Queue<Node> mainQueue) {
		Queue<Node> q= new LinkedList<>();
		int k = mainQueue.size();
		while(k>0){
			Node n = mainQueue.poll();
			q.add(n);
			if(n.left!=null)mainQueue.add(n.left);
			if(n.right!=null)mainQueue.add(n.right);
			k--;
		}
		if(mainQueue.size() >0)reverseUtil(mainQueue);
		while(!q.isEmpty()) {
			System.out.print(q.poll().root+" ");
		}
		System.out.println();
		
	}
	public void levelOrderReversal(BinaryTree tree){
		Queue<Node> q= new LinkedList<>();
		q.add(tree.root);
		reverseUtil(q);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LevelOrderReverse l = new LevelOrderReverse();
		BinaryTree tree= new BinaryTree();
		tree.root = new Node(1);
		tree.root.left =new Node(2);
		tree.root.right =new Node(3);
		tree.root.left.left =new Node(4);
		tree.root.left.right =new Node(5);
		tree.root.right.left =new Node(6);
		tree.root.right.right =new Node(7);
		l.levelOrderReversal(tree);
	}

}

- Siddhi October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package goldmansach;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import main.java.algorithms.binarytree.BinaryTree;
import main.java.algorithms.binarytree.Node;

public class LevelOrderReverse {
	
	public void reverseUtil(Queue<Node> mainQueue) {
		Queue<Node> q= new LinkedList<>();
		int k = mainQueue.size();
		while(k>0){
			Node n = mainQueue.poll();
			q.add(n);
			if(n.left!=null)mainQueue.add(n.left);
			if(n.right!=null)mainQueue.add(n.right);
			k--;
		}
		if(mainQueue.size() >0)reverseUtil(mainQueue);
		while(!q.isEmpty()) {
			System.out.print(q.poll().root+" ");
		}
		System.out.println();
		
	}
	public void levelOrderReversal(BinaryTree tree){
		Queue<Node> q= new LinkedList<>();
		q.add(tree.root);
		reverseUtil(q);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LevelOrderReverse l = new LevelOrderReverse();
		BinaryTree tree= new BinaryTree();
		tree.root = new Node(1);
		tree.root.left =new Node(2);
		tree.root.right =new Node(3);
		tree.root.left.left =new Node(4);
		tree.root.left.right =new Node(5);
		tree.root.right.left =new Node(6);
		tree.root.right.right =new Node(7);
		l.levelOrderReversal(tree);
	}

}

- Siddhi October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package goldmansach;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import main.java.algorithms.binarytree.BinaryTree;
import main.java.algorithms.binarytree.Node;

public class LevelOrderReverse {

public void reverseUtil(Queue<Node> mainQueue) {
Queue<Node> q= new LinkedList<>();
int k = mainQueue.size();
while(k>0){
Node n = mainQueue.poll();
q.add(n);
if(n.left!=null)mainQueue.add(n.left);
if(n.right!=null)mainQueue.add(n.right);
k--;
}
if(mainQueue.size() >0)reverseUtil(mainQueue);
while(!q.isEmpty()) {
System.out.print(q.poll().root+" ");
}
System.out.println();

}
public void levelOrderReversal(BinaryTree tree){
Queue<Node> q= new LinkedList<>();
q.add(tree.root);
reverseUtil(q);
}

public static void main(String[] args) {
// TODO Auto-generated method stub
LevelOrderReverse l = new LevelOrderReverse();
BinaryTree tree= new BinaryTree();
tree.root = new Node(1);
tree.root.left =new Node(2);
tree.root.right =new Node(3);
tree.root.left.left =new Node(4);
tree.root.left.right =new Node(5);
tree.root.right.left =new Node(6);
tree.root.right.right =new Node(7);
l.levelOrderReversal(tree);
}

}

- Siddhi October 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Postorder traversal will also work in this case. It will first print the left child then right child and then parent.

- Ritika Rathi March 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Postorder can't work. They want it in level order. e.g. if you do postorder, the immediate left child of root will get printed before the leaves of the right child. We don't want that, do we?

- Anonymous April 10, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

exactly, you are right..its very true that post order cant work in this case because the roots at the same level gets printed before the right child of these roots.

- Anant Upadhyay July 06, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

exactly, you are right..its very true that post order cant work in this case because the roots at the same level gets printed before the right child of these roots.

- Anant Upadhyay July 06, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I do not understand. The question simply says that if the array is 1,2,3 the program should print 1,3,2 and that is post - order - tree - walk. So why not post-order-tree walk?

- Hello April 06, 2011 | 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