CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person



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

BFS Iterator

import java.util.*;

class Practice5 {
	
	public static class Node {
		public Integer data;
		public Node left, right;

		public Node(Integer data){
			this.data = data;
		}

		@Override
		public String toString(){
			return this.data.toString();
		}
	}

	public static class Bst implements Iterable<Node> {
		public Node root;

		@Override
		public Iterator<Node> iterator(){
			return root == null ? Collections.emptyIterator() : new NodeIterator(root);
		}
	}

	public static class NodeIterator implements Iterator<Node> {
		
		Node start;
		LinkedList<Node> q;

		public NodeIterator(Node root){
			start = root;
			q = new LinkedList<>();
			q.add(start);
		}

		@Override
		public boolean hasNext(){
			return !q.isEmpty();
		}

		@Override
		public Node next(){
			Node ret = q.removeFirst();
			if(ret.left != null){
				q.add(ret.left);
			}
			if(ret.right != null){
				q.add(ret.right);
			}
			return ret;
		}

		@Override
		public void remove(){
			// empty
		}

	}

	public static void main(String[] args){
		Bst bst = new Bst();
		bst.root = new Node(19);
		bst.root.left = new Node(1);
		bst.root.right = new Node(5);
		bst.root.left.left = new Node(3);
		bst.root.left.right = new Node(242);
		for(Node n : bst){
			System.out.println(n);
		}
	}

}

- I.R. July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Bfs Iterator

import java.util.*;

class Practice5 {
	
	public static class Node {
		public Integer data;
		public Node left, right;

		public Node(Integer data){
			this.data = data;
		}

		@Override
		public String toString(){
			return this.data.toString();
		}
	}

	public static class Bst implements Iterable<Node> {
		public Node root;

		@Override
		public Iterator<Node> iterator(){
			return root == null ? Collections.emptyIterator() : new NodeIterator(root);
		}
	}

	public static class NodeIterator implements Iterator<Node> {
		
		Node start;
		LinkedList<Node> q;

		public NodeIterator(Node root){
			start = root;
			q = new LinkedList<>();
			q.add(start);
		}

		@Override
		public boolean hasNext(){
			return !q.isEmpty();
		}

		@Override
		public Node next(){
			Node ret = q.removeFirst();
			if(ret.left != null){
				q.add(ret.left);
			}
			if(ret.right != null){
				q.add(ret.right);
			}
			return ret;
		}

		@Override
		public void remove(){
			// empty
		}

	}

	public static void main(String[] args){
		Bst bst = new Bst();
		bst.root = new Node(19);
		bst.root.left = new Node(1);
		bst.root.right = new Node(5);
		bst.root.left.left = new Node(3);
		bst.root.left.right = new Node(242);
		for(Node n : bst){
			System.out.println(n);
		}
	}

}

- I.R. July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node implements Iterable<Node>
{
	private int value;
	private Node left;
	private Node right;
	private Iterator<Node> bti;
	
	public Node(int v)
	{
		this.value=v;
	}
	public Iterator<Node> iterator()
	{
		bti=new BinaryTreeIterator(this);
		return bti;
	}
	
	public static void main(String[] args)
	{
		//code to create tree
		Node n=new Node(6)
		Iterator<Node> treeIt=n.iterator();
		while(treeIt.hasNext())
		{
			System.out.println(treeIt.getNext().value);
		}
		
	}
		
	public class BinaryTreeIterator implements Iterator<Node>
	{
		private Node n;=
		public BinaryTreeIterator(Node rt)
		{
			n=rt;
		}
	
		public boolean hasNext()
		{
			return(n!=null);
		}
		public Node getNext() throws NoSuchElementException
		{
			if(hasNext())
			{
			Node ret=n;
			n=n.left!=null?n.left:n.right;
			return ret;
			}
		throw new NoSuchElementException();
	}
	public void remove() throws UnsupportedOperationException
	{
		throw new UnsupportedOperationException();
	}
	
	}
	
	
	
}

- Divya July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node implements Iterable<Node>
{
	private int value;
	private Node left;
	private Node right;
	private Iterator<Node> bti;
	
	public Node(int v)
	{
		this.value=v;
	}
	public Iterator<Node> iterator()
	{
		bti=new BinaryTreeIterator(this);
		return bti;
	}
	
	public static void main(String[] args)
	{
		//code to create tree
		Node n=new Node(6)
		Iterator<Node> treeIt=n.iterator();
		while(treeIt.hasNext())
		{
			System.out.println(treeIt.getNext().value);
		}
		
	}
		
	public class BinaryTreeIterator implements Iterator<Node>
	{
		private Node n;=
		public BinaryTreeIterator(Node rt)
		{
			n=rt;
		}
	
		public boolean hasNext()
		{
			return(n!=null);
		}
		public Node getNext() throws NoSuchElementException
		{
			if(hasNext())
			{
			Node ret=n;
			n=n.left!=null?n.left:n.right;
			return ret;
			}
		throw new NoSuchElementException();
	}
	public void remove() throws UnsupportedOperationException
	{
		throw new UnsupportedOperationException();
	}
	
	}
	
	
	
}

- divm01986 July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

That gets you down one side till a leaf, how do you go back up?

- taisinT July 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class BinaryDFSInterator<E> implements Iterator<E>{
    private E[] binaryTree;
    private boolean[] visited;
    private int currentIndex = -1;

    public BinaryDFSInterator(E[] binaryTree){
       this.binaryTree = binaryTree;
       this.visited = new boolean[binaryTree.length];
    }

   public boolean hasNext(){
        return currentIndex != binaryTree.length - 1;
    }

    public E next(){
      if(currentIndex  < 0){
         currentIndex = 0;
         visited[currentIndex] = true;
         return binaryTree[currentIndex];
      }
      if(isLeaf()){
       currentIndex = getParent();        
      }
      int nextNotVisitedNode = getNotVisitedChild();
      while(nextNotVisitedNode  == -1){
          currentIndex = getParent();
          nextNotVisitedNode = getNotVisitedChild();          
       }
        currentIndex = nextNotVisitedNode ;
         visited[currentIndex] = true;
         return binaryTree[currentIndex];
    }

    public void remove(){
        throw new UnsupportedOperationException();
    }

   private boolean isLeaf(){
       return  2*currentIndex + 1 >= binaryTree.length;
   }
   
   private int getParent(){
       int parentIndex = (currentIndex - 1)/2;
       return parentIndex >= 0? parentIndex  : 0;
   }

  private int getNotVisitedChild(){
      for(int i = 1; i <= 2; ++){
        int childIndex = 2*currentIndex + i;
        if(!visited[childIndex ]){
             return childIndex;
         }
      }
      return -1;
  }
}

- taisinT July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

__author__ = 'rohanmathure'


from Tree import Tree
from NodeParent import Node

import unittest

class TreeIterator:
    def __init__(self):
        self.__tree__ = Tree()
        self.__currentNode__ = Node()
        self.__isFirst = True

    def setTree(self,tree):
        self.__tree__=tree

    def next(self):
        tempNode=Node()
        if self.__tree__ == None:
            return False
        if self.__tree__.getRoot() == None:
            return False
        if self.__isFirst:
            self.__isFirst = False
            if not self.__tree__.getRoot().getLeft() == None:
                self.__currentNode__ = self.getLeftMostChild(self.__tree__.getRoot().getLeft())
            else:
                self.__currentNode__ = self.__tree__.getRoot()
        else:
            if not self.__currentNode__.getRight() == None:
                self.__currentNode__=self.getLeftMostChild(self.__currentNode__.getRight())
            elif self.__currentNode__.getParent() == None:
                return False
            elif self.__currentNode__ == self.__currentNode__.getParent().getLeft():
                self.__currentNode__ = self.__currentNode__.getParent()
            elif self.__currentNode__ == self.__currentNode__.getParent().getRight():
                tempNode=self.__currentNode__
                while not tempNode == None:
                    if tempNode == tempNode.getParent().getLeft():
                        self.__currentNode__ = tempNode.getParent()
                        return self.__currentNode__
                    else:
                        tempNode = tempNode.getParent()
                else:
                    return False
        return self.__currentNode__

    def getLeftMostChild(self,node):
        if not node.getLeft() == None:
            return self.getLeftMostChild(node.getLeft())
        else:
            return node


class TestTreeIterator(unittest.TestCase):
    def setUp(self):
        self.treeIterator=TreeIterator()
        tree=Tree()
        node1=Node()
        node2=Node()
        node3=Node()
        node4=Node()
        node5=Node()
        node6=Node()
        node7=Node()
        node8=Node()
        node9=Node()
        node12=Node()
        node2.setValue(2)
        node3.setValue(3)
        node1.setValue(1)
        node4.setValue(4)
        node5.setValue(5)
        node6.setValue(6)
        node7.setValue(7)
        node8.setValue(8)
        node9.setValue(9)
        node12.setValue(12)
        tree.setRoot(node12)
        node12.setLeft(node1)
        node12.setRight(node9)
        node9.setLeft(node2)
        node9.setRight(node4)
        node2.setRight(node8)
        node8.setLeft(node5)
        node8.setRight(node6)
        node4.setLeft(node3)
        node4.setRight(node7)
        node3.setParent(node4)
        node7.setParent(node4)
        node4.setParent(node9)
        node9.setParent(node12)
        node1.setParent(node12)
        node2.setParent(node9)
        node8.setParent(node2)
        node5.setParent(node8)
        node6.setParent(node8)
        self.treeIterator.setTree(tree)

    def testIteration(self):

        self.assertEqual(self.treeIterator.next().getValue(), 1)
        self.assertEqual(self.treeIterator.next().getValue(), 12)
        self.assertEqual(self.treeIterator.next().getValue(), 2)
        self.assertEqual(self.treeIterator.next().getValue(), 5)
        self.assertEqual(self.treeIterator.next().getValue(), 8)
        self.assertEqual(self.treeIterator.next().getValue(), 6)
        self.assertEqual(self.treeIterator.next().getValue(), 9)
        self.assertEqual(self.treeIterator.next().getValue(), 3)
        self.assertEqual(self.treeIterator.next().getValue(), 4)
        self.assertEqual(self.treeIterator.next().getValue(), 7)

- Rohan Mathure July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

__author__ = 'rohanmathure'


from Tree import Tree
from NodeParent import Node

import unittest

class TreeIterator:
    def __init__(self):
        self.__tree__ = Tree()
        self.__currentNode__ = Node()
        self.__isFirst = True

    def setTree(self,tree):
        self.__tree__=tree

    def next(self):
        tempNode=Node()
        if self.__tree__ == None:
            return False
        if self.__tree__.getRoot() == None:
            return False
        if self.__isFirst:
            self.__isFirst = False
            if not self.__tree__.getRoot().getLeft() == None:
                self.__currentNode__ = self.getLeftMostChild(self.__tree__.getRoot().getLeft())
            else:
                self.__currentNode__ = self.__tree__.getRoot()
        else:
            if not self.__currentNode__.getRight() == None:
                self.__currentNode__=self.getLeftMostChild(self.__currentNode__.getRight())
            elif self.__currentNode__.getParent() == None:
                return False
            elif self.__currentNode__ == self.__currentNode__.getParent().getLeft():
                self.__currentNode__ = self.__currentNode__.getParent()
            elif self.__currentNode__ == self.__currentNode__.getParent().getRight():
                tempNode=self.__currentNode__
                while not tempNode == None:
                    if tempNode == tempNode.getParent().getLeft():
                        self.__currentNode__ = tempNode.getParent()
                        return self.__currentNode__
                    else:
                        tempNode = tempNode.getParent()
                else:
                    return False
        return self.__currentNode__

    def getLeftMostChild(self,node):
        if not node.getLeft() == None:
            return self.getLeftMostChild(node.getLeft())
        else:
            return node


class TestTreeIterator(unittest.TestCase):
    def setUp(self):
        self.treeIterator=TreeIterator()
        tree=Tree()
        node1=Node()
        node2=Node()
        node3=Node()
        node4=Node()
        node5=Node()
        node6=Node()
        node7=Node()
        node8=Node()
        node9=Node()
        node12=Node()
        node2.setValue(2)
        node3.setValue(3)
        node1.setValue(1)
        node4.setValue(4)
        node5.setValue(5)
        node6.setValue(6)
        node7.setValue(7)
        node8.setValue(8)
        node9.setValue(9)
        node12.setValue(12)
        tree.setRoot(node12)
        node12.setLeft(node1)
        node12.setRight(node9)
        node9.setLeft(node2)
        node9.setRight(node4)
        node2.setRight(node8)
        node8.setLeft(node5)
        node8.setRight(node6)
        node4.setLeft(node3)
        node4.setRight(node7)
        node3.setParent(node4)
        node7.setParent(node4)
        node4.setParent(node9)
        node9.setParent(node12)
        node1.setParent(node12)
        node2.setParent(node9)
        node8.setParent(node2)
        node5.setParent(node8)
        node6.setParent(node8)
        self.treeIterator.setTree(tree)

    def testIteration(self):

        self.assertEqual(self.treeIterator.next().getValue(), 1)
        self.assertEqual(self.treeIterator.next().getValue(), 12)
        self.assertEqual(self.treeIterator.next().getValue(), 2)
        self.assertEqual(self.treeIterator.next().getValue(), 5)
        self.assertEqual(self.treeIterator.next().getValue(), 8)
        self.assertEqual(self.treeIterator.next().getValue(), 6)
        self.assertEqual(self.treeIterator.next().getValue(), 9)
        self.assertEqual(self.treeIterator.next().getValue(), 3)
        self.assertEqual(self.treeIterator.next().getValue(), 4)
        self.assertEqual(self.treeIterator.next().getValue(), 7)

- Rohan Mathure July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

__author__ = 'rohanmathure'


from Tree import Tree
from NodeParent import Node

import unittest

class TreeIterator:
    def __init__(self):
        self.__tree__ = Tree()
        self.__currentNode__ = Node()
        self.__isFirst = True

    def setTree(self,tree):
        self.__tree__=tree

    def next(self):
        tempNode=Node()
        if self.__tree__ == None:
            return False
        if self.__tree__.getRoot() == None:
            return False
        if self.__isFirst:
            self.__isFirst = False
            if not self.__tree__.getRoot().getLeft() == None:
                self.__currentNode__ = self.getLeftMostChild(self.__tree__.getRoot().getLeft())
            else:
                self.__currentNode__ = self.__tree__.getRoot()
        else:
            if not self.__currentNode__.getRight() == None:
                self.__currentNode__=self.getLeftMostChild(self.__currentNode__.getRight())
            elif self.__currentNode__.getParent() == None:
                return False
            elif self.__currentNode__ == self.__currentNode__.getParent().getLeft():
                self.__currentNode__ = self.__currentNode__.getParent()
            elif self.__currentNode__ == self.__currentNode__.getParent().getRight():
                tempNode=self.__currentNode__
                while not tempNode == None:
                    if tempNode == tempNode.getParent().getLeft():
                        self.__currentNode__ = tempNode.getParent()
                        return self.__currentNode__
                    else:
                        tempNode = tempNode.getParent()
                else:
                    return False
        return self.__currentNode__

    def getLeftMostChild(self,node):
        if not node.getLeft() == None:
            return self.getLeftMostChild(node.getLeft())
        else:
            return node


class TestTreeIterator(unittest.TestCase):
    def setUp(self):
        self.treeIterator=TreeIterator()
        tree=Tree()
        node1=Node()
        node2=Node()
        node3=Node()
        node4=Node()
        node5=Node()
        node6=Node()
        node7=Node()
        node8=Node()
        node9=Node()
        node12=Node()
        node2.setValue(2)
        node3.setValue(3)
        node1.setValue(1)
        node4.setValue(4)
        node5.setValue(5)
        node6.setValue(6)
        node7.setValue(7)
        node8.setValue(8)
        node9.setValue(9)
        node12.setValue(12)
        tree.setRoot(node12)
        node12.setLeft(node1)
        node12.setRight(node9)
        node9.setLeft(node2)
        node9.setRight(node4)
        node2.setRight(node8)
        node8.setLeft(node5)
        node8.setRight(node6)
        node4.setLeft(node3)
        node4.setRight(node7)
        node3.setParent(node4)
        node7.setParent(node4)
        node4.setParent(node9)
        node9.setParent(node12)
        node1.setParent(node12)
        node2.setParent(node9)
        node8.setParent(node2)
        node5.setParent(node8)
        node6.setParent(node8)
        self.treeIterator.setTree(tree)

    def testIteration(self):

        self.assertEqual(self.treeIterator.next().getValue(), 1)
        self.assertEqual(self.treeIterator.next().getValue(), 12)
        self.assertEqual(self.treeIterator.next().getValue(), 2)
        self.assertEqual(self.treeIterator.next().getValue(), 5)
        self.assertEqual(self.treeIterator.next().getValue(), 8)
        self.assertEqual(self.treeIterator.next().getValue(), 6)
        self.assertEqual(self.treeIterator.next().getValue(), 9)
        self.assertEqual(self.treeIterator.next().getValue(), 3)
        self.assertEqual(self.treeIterator.next().getValue(), 4)
        self.assertEqual(self.treeIterator.next().getValue(), 7)

- rohan.rapidwolverine July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby impl. Using stack to capture stack-frames of depth-first search. Running time: O(|V|+|E|). Space: O(|V|).

require 'tree'
require 'ds'

root_node = Tree::TreeNode.new("1", 1)
child1 = Tree::TreeNode.new("2",2)
child2 = Tree::TreeNode.new("3",3)
grandchild1=Tree::TreeNode.new("4",4)
grandchild2=Tree::TreeNode.new("5",5)
grandchild3=Tree::TreeNode.new("6",6)
grandchild4=Tree::TreeNode.new("7",7)
child1 << grandchild1
child1 << grandchild2
child2 << grandchild3
child2 << grandchild4
root_node << child1
root_node << child2
root_node.print_tree

module Iterator
  def next
    nil
  end
  
  def has_next?
    false
  end
end

class TreeIterator
  include Iterator
  
  def initialize(root_node)
    @stack=DS::Stack.new
    @stack.push(root_node)
  end
  
  def next
    node = @stack.pop
    
    node.children.each do |child|
      @stack.push(child)
    end
    
    node
  end
  
  def has_next?
    !@stack.empty?
  end
end

class MyTree
  def initialize(root_node)
    @root_node=root_node
  end
  
  def iterator
    TreeIterator.new(@root_node)
  end
end

iterator = MyTree.new(root_node).iterator

while iterator.has_next?
  print "#{iterator.next.name}"
  print ' -> ' if iterator.has_next?
end

Output:
* 1
|---+ 2
| |---> 4
| +---> 5
+---+ 3
|---> 6
+---> 7

1 -> 3 -> 7 -> 6 -> 2 -> 5 -> 4

- Yev July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution. When I've read the question, I assumed that we should iterate in-order. If it's not the case, your solution is just fine.

- damluar July 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java implementation that does non-recursive in-order traversal using a stack.

public class TreeIterator implements Iterator<TreeNode> {

    Stack<TreeNode> inorder = new Stack<>();

    public TreeIterator(TreeNode node) {
        goAsLeftAsPossible(node);
    }

    public void inorderTraversal() {
        goAsLeftAsPossible(inorder.pop().right);
    }

    private void goAsLeftAsPossible(TreeNode node) {
        while (node != null) {
            inorder.push(node);
            node = node.left;
        }
    }

    @Override
    public boolean hasNext() {
        return !inorder.isEmpty();
    }

    @Override
    public TreeNode next() {
        if (!hasNext()) {
            throw new IllegalStateException();
        }

        TreeNode next = inorder.peek();
        inorderTraversal();
        return next;
    }
}

- damluar July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inorder traversal

public static void main(String args[])
    {
        Node c = new Node(1,new Node(2, new Node(3, null, new Node(4, null, null)), new Node(5, new Node(6, null, null), new Node(7, null, null))), new Node(8, null, null));
        It it = new It(c);
        while (it.hasNext()) {
            Node next = it.next();
            System.out.println(Integer.toString(next.value));
        }
    }
    
    public static class It {
        Stack<Node> s;
        Node current;
        public It(Node n) {
            s = new Stack<Node>();
            current = n;
            while (current.left != null) {
                s.push(current);
                current = current.left;
            }
        }
        
        public Node next() {
            Node result = current;
            if (current.right != null) {
                s.push(current);
                current = current.right;
                while (current.left != null) {
                    s.push(current);
                    current = current.left;
                }   
            } else {
                while(s.size() > 0 && current == s.peek().right) {
                    current = s.pop();
                }
                if (s.size() == 0) {
                    current = null;
                } else {
                    current = s.pop();
                }
            }
            return result;
        }
        public boolean hasNext() {
            return current != null;
        }
    }
    
    public static class Node {
        int value;
        Node left;
        Node right;
        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

- yaronbic October 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

Performing action on the given (processing\visiting) node is denoted as "D". And traversing left child node denoted with "L" and right child node denoted with "R". So, there are three possible ways one can traverse the tree.
1. Preorder (DLR) traversal
2. Inorder (LDR) traversal
3. Postorder (LRD) traversal

All of them are O(n) complexity and O(n) space complexity. No major difference between them except the sequence of the actions. All of them can be achieved using either recursive or non-recursive method. Here is one of the implementation using PreOrder Traversal with recursive method.

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

//
// Pre-Order Traversal method (DLR)
// i.e. 1. Visit the root 2. Traverse Left subtree 3. Traverse the right subtree
//
void BinaryTreeTraversal(struct Node *root)
{
    if (root) // make sure the node is not NULL, that is the recursive terminator
    {
        printf("%d ", root->data);
        BinaryTreeTraversal(root->left);
        BinaryTreeTraversal(root->right);
    }
}

- Mohan July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

But you did not implement an iterator.
They are probably asking for a lazy iterator, which will require stack based traversal.

- Gil July 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Mohan, you are implementing tree traversal. The question asked for an iterator. In Java, for example, that would be a class implementing the Iterator interface (next(), hasNext() and remove() methods).

- carlosgsouza July 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's a good point. I agree, implementing the iterator itself is probably the expectation here.

- Mohan July 08, 2015 | 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