Goldman Sachs Interview Question for Software Engineer / Developers


Team: Strategies Group
Country: India
Interview Type: In-Person




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

Managing (or actually emulating) call stack explicitly;

class StackFrame{
       Node node;
       boolean isRecursive;
       
       public StackFrame( Node node, boolean isRecursive ){
          this.node = node;
          this.isRecursive = isRecursive;
       }
   }
   
   public void printInOrder( Node root ){
      Stack<StackFrame> callStack = new Stack<StackFrame>();
      callStack.push( new StackFrame( root, true ));
      
      while( !callStack.isEmpty() ){
         StackFrame frame = callStack.pop();
         Node node = frame.node;
         if( node != null ){
            if( frame.isRecursive ){
               callStack.push( new StackFrame( node.right, true) );
               callStack.push( new StackFrame( node, false) );
               callStack.push( new StackFrame( node.left, true) );
            }else{
               System.out.println( node );
            }
         }
      }
   }

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

Why use isRecursive boolean? I think it can be replaced by checking node.leftchild/rightchild. In this way, we can also avoid the stackframe class and using implicit stack class. I also donnot understand why every time we need to pop and then push, we can do this check by a single if(node!=null)

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

@ds can you please post some code. I can make comments on that.

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

nice coding! I think it works just as the recursive way.

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

@hakanserce, and that's why u add the boolean

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

/*
* Inorder Tree Traversal without recursion and without stack
*
* Morris Traversal :
* 1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
*
*/

public void morrisinorder(Node node){
if(node == null)
return;
Node current = node;
while(current != null){
if(current.left == null){
System.out.println(current.val);
current = current.right;
}else{
Node pre = current.left;
while(pre.right != null && pre.right !=current){
pre = pre.right;
}

if(pre.right == null){
pre.right = current;
current = current.left;
}else{
pre.right = null;
System.out.println(current.val);
current = current.right;
}
}
}
}

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

/*
* Inorder Tree Traversal without recursion and without stack
*
* Morris Traversal :
* 1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
*
*/

public void morrisinorder(Node node){
		if(node == null)
			return;		
		Node current = node;
		while(current != null){
			if(current.left == null){
				System.out.println(current.val);
				current = current.right;
			}else{
				Node pre = current.left;
				while(pre.right != null && pre.right !=current){
					pre = pre.right;
				}
				
				if(pre.right == null){
					pre.right = current;
					current = current.left;
				}else{
					pre.right = null;
					System.out.println(current.val);
					current = current.right;
				}				
			}
		}		
	}

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

void Inorder_WORecursion(Tree *root)
{
if(root == NULL)
{
return;
}
else
{
Push(root);
}
while(top != -1)
{
if(root->Left != NULL)
{
Push(root->Left);
root = root->Left;
}
else
{
root = Pop();
printf("%d->",root->data);
if(root->Right != NULL)
{
Push(root->Right);
root = root->Right;
}

}
}

}

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

Use Morris Traversal

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

// Iterative Inorder
void Inorder(Node root)
{
	Stack *stack = new Stack();
	stack->Push(root);
	Node temp = root->left;

	while(true)
	{
		while(temp)
		{
			stack->Push(temp);
			temp = temp->left;
		}
		if(stack->IsEmpty()) break;
		temp = stack->Pop();
		printf("%d ",temp->value);
		temp = temp->right;
	}
}

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

elegant solution

- Anonymous August 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Function to traverse binary tree without recursion and 
   without stack */
void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;
 
  if(root == NULL)
     return; 
 
  current = root;
  while(current != NULL)
  {                 
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;      
    }    
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;
 
      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }
             
      /* Revert the changes made in if part to restore the original 
        tree i.e., fix the right child of predecssor */   
      else 
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;      
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}

- Putta June 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple Solution:

-Have a linked list where we can store nodes and a ArrayList

-Insert Root in linked list

-Insert 'Root->left' and 'Root->right' in ArrayList

-In case 'Root->left' exists insert 'Root->left' at Root's just left

-In case 'Root->right' exists insert 'Root->right' at Root's just right

-Repeat above steps for each level of tree

For Ex:
Let's say we have a tree
Inorder= D B E A F C G
Root = A

Procedure:
-Insert Root 'A' in Linked List
-Insert Roots Left 'B' and Right 'C' in ArrayList.

-Insert 'A' -> left (B) just before A
-Insert 'A' -> right (C) just after A
-Linked List is now = B A C

-Now Perform root action in all node present in Array List
-Linked List is now = D B E A F C G

- PKT October 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

public void InorderPrint(Node root)
{
    Stack<Node> s = new Stack<Node>();
    if (root!=null)
    {
       s.push(root);
       while(!s.IsEmpty())
        {
              Node nd = s.pop();
              if (nd!=null)
              {
                  if(nd.rightchild)
                   {  s.push(nd.rightchild);}
                  s.push(nd);
                  if(nd.leftchild)
                   {  s.push(nd.leftchild);}
               }
         }
         foreach(Node n in s)
         {  print n.data; }
      
     }
     else
     { print error msg;}
}

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

I think this code results in an infinite loop. Try with a tree with just a single node (root) for instance.

In the while loop the node is first popped then pushed everytime, so the stack will never be empty.

- hakanserce January 01, 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