Google Interview Question for Site Reliability Engineers


Team: Google Engineering
Country: United States
Interview Type: Phone Interview




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

class node
{
    public node parent;
    public node left;
    public node right;
    object data;
}

node inorderSuccessor(node n)
{
    if (n.right != null)
	return min(n.right);

    node p = n.parent;
    while (p != null && n == p.right)
    {
	n = p;
	p = p.parent;
    }

    return p;
}

node min(node n)
{
    if (n.left == null)
	return n;
    return min(n.left);
}

- Code Jockey September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Algos: Dude.. If all you are given is the pointer to a node, and the node only has a parent pointer, then it is impossible.

Even if you are given the root node, it is still impossible.

So shut it.

- Code Jockey September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Algos:
How is it possible to have just a link to its parent and not have a right link at all.

also i think A bst remains a bst even if it is asked in Google.

- I September 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assumption: Each node has information whether it is a left child or a right child.

Pre process the tree using a map. Set the left and right pointers which point to left and right child respectively. This is done in O(n).


If it is HAS a right child then the successor is the child.
else if it does not then the successor is the parent's parent.

- Noobie September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If there are no left and right pointers in the node then use the map like this. key is the node whose parent, left right is in value.
<key, [parent, left, right]>.

buildMap(map, nodes[])
{
	for(i=0; i<nodes.length; i++)
	{
		n = node[i];
		map.put(n, null);
		if(map.containsKey(n.parent))
		{
			if(n.isLeftChild())	
				map.get(n.parent).leftChild = n;	//	Assume map is of object references.
			else
				map.get(n.parent).rightChild = n;
		}	
	}
}

- Noobie September 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

* Complexity O(n)

public class BinarySearchTree {

	static class Node{
		Node left, right;
		Node parent;
		int data;
		@Override
		public String toString() {
			return ""+data;
		}
		
	}
	
	public static void main(String[] args) {
		
		final Node node4 = new Node(){{left=null; right=null; parent=null; data=4;}};	
		final Node node8 = new Node(){{left=null; right=null; parent=null; data=8;}};
		final Node node7 = new Node(){{left=node4; right=node8; parent=null; data=7;}};
		node4.parent=node8.parent=node7;
		final Node node18 = new Node(){{left=null; right=null; parent=null; data=18;}};
		final Node node15 = new Node(){{left=null; right=node18; parent=null; data=15;}};
		node18.parent=node15;
		final Node root = new Node(){{left=node7; right=node15; parent=null; data=10;}};
		node7.parent=node15.parent=root;
		
		System.out.println(node4 + " : " + getInorderSuccessor(node4));
		System.out.println(node8 + " : " + getInorderSuccessor(node8));
		System.out.println(node7 + " : " + getInorderSuccessor(node7));
		System.out.println(root + " : " + getInorderSuccessor(root));
		System.out.println(node18 + " : " + getInorderSuccessor(node18));
		System.out.println(node15 + " : " + getInorderSuccessor(node15));
	}
	
	public static Node getInorderSuccessor(Node node){
		assert(node!=null);
		if (node.right!=null){
			return getLeftMost(node.right);
		}

		//node is left of parent
		if (node == node.parent.left)
			return node.parent;
		
		//node is right of parent
		return getParentWithRightBranch(node.parent);
	}

	private static Node getParentWithRightBranch(Node node) {
		if (node.parent==null)
			return null;
		if (node.parent.left==node){
			return node.parent;
		}
		
		return getParentWithRightBranch(node.parent);
	}

	private static Node getLeftMost(Node node) {
		if (node.left==null)
			return node;
		return getLeftMost(node.left);
	}
	
}

- rajanikant.malviya September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

typedef struct TNode {
	int key; 
	void* data;
	TNode* left;
	TNode* right;
	TNode* parent;
};


TNode* inorder_successor(TNode* root, TNode* p) {
	if( p && is_present_in_tree(root, p) ) {
		if(p->right) {
			return min_right_subtree(p->right);
		} else {
			TNode* X = p;
			TNode* Y = p->parent;
			while(Y && X==Y->right) {
				X = Y;
				Y = Y->parent;
			}
			return Y;
		}
	}else {
		return NULL;
	}
}

- mr September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;



public class Find_Next_Node_InOrder_In_BinaryTree {

public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
this.value=data;
}
}
public static void createParentmap(Node head,HashMap<Node,Node> parentmap){
if(head==null){
System.out.println("This tree is empty!");
return ;
}
Queue<Node> nodeQueue=new LinkedList<Node>();
nodeQueue.add(head);
parentmap.put(head, null);
while(!nodeQueue.isEmpty()){
Node currentNode=nodeQueue.poll();
if(currentNode.left!=null){
parentmap.put(currentNode.left,currentNode);
nodeQueue.add(currentNode.left);
}
if(currentNode.right!=null){
parentmap.put(currentNode.right,currentNode);
nodeQueue.add(currentNode.right);
}
}
}

public static Node findNextNode(Node cur,HashMap<Node,Node> map){
if(!map.containsKey(cur)){
return null;
}
if(map.get(cur)==null||cur.right!=null){
return MostLeftNode(cur.right);
}
Node previous=map.get(cur);
Node current=cur;
while(previous.left!=current){
current=previous;
previous=map.get(previous);
if(previous==null){
return null;
}
}
return previous;
}
public static Node MostLeftNode(Node cur){
if(cur==null){
return null;
}
while(cur.left!=null){
cur=cur.left;
}
return cur;
}
public static void main(String[] args) {
Node head=new Node(16);
head.left=new Node(12);
head.right=new Node(18);
head.left.left=new Node(6);
head.left.right=new Node(14);
head.left.right.left=new Node(13);
head.left.right.right=new Node(15);
head.right.left=new Node(17);
head.right.right=new Node(24);
HashMap<Node,Node> parentMap= new HashMap<Node,Node>();
createParentmap(head, parentMap);
System.out.println(findNextNode(head.left.right,parentMap).value);

}

}

- Chengyun Zuo September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@bicepjai....how is the tree referred to? Giving the root of the tree does not make much sense. Is it given as a list of leaves at the lowest level?

- Anonymous September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can check my solution at github leafac/puzzles/tree/master/next-node:

class Node

  attr_reader :value, :parent, :direction

  def initialize(value, parent = nil, direction = nil)
    @value     = value
    @parent    = parent
    @direction = direction
  end

end

class NodeWithChildren

  attr_reader   :node
  attr_accessor :left, :right

  def initialize(node)
    @node = node
  end
end

class NextNodeResolver

  def initialize(leafs)
    @nexts = {}

    nodes_to_process              = leafs
    nodes_processed_with_children = []
    root                          = nil

    until nodes_to_process.empty?

      node_to_process = nodes_to_process.pop

      node_to_process_with_children = NodeWithChildren.new(node_to_process)

      nodes_processed_with_children.each do |node_processed_with_children|
        if node_processed_with_children.node.parent == node_to_process

          case node_processed_with_children.node.direction
          when :left  then node_to_process_with_children.left  = node_processed_with_children
          when :right then node_to_process_with_children.right = node_processed_with_children
          end

        end
      end


      if node_to_process.parent.nil?
        root = node_to_process_with_children
      elsif ! (nodes_to_process & nodes_processed_with_children.map(&:node)).include? node_to_process.parent
        nodes_to_process << node_to_process.parent
      end

      nodes_processed_with_children << node_to_process_with_children

    end

    previous_node = nil

    depth_first_seach = ->(node_with_children) do

      unless node_with_children.nil?

        depth_first_seach.(node_with_children.left)
        @nexts[previous_node]      = node_with_children.node unless previous_node.nil?
        previous_node              = node_with_children.node
        depth_first_seach.(node_with_children.right)

      end
    end

    depth_first_seach.(root)

  end

  def resolve(node)
    @nexts[node]
  end
end

- Leandro Facchinetti September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Is there any restrictions I missed? Why don't we do it like below?

public Node getNext(Node root) {
	if (root == null) return null;
	if (root.right == null) return root.parent;
	Node node = root.right;
	while (node.left != null) {
		node = node.left;
	}
	return node;
}

- Baibing September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Node nextNode(Node node) {
		if ( node == null ) { return null; }
		if ( node.right != null ) {
			node = node.right;
			while ( node.left != null) {
				node = node.left;
			}
			return node;
		} else {
			if ( node.parent == null) { // for root node parent  == null;
				return null;
			} else if ( node.parent.left == node) { // it is parent's left node.
				return node;
			} else {
				// node is the right child of parent and it has no right child.
				Node currNode = node;
				while ( node.parent != null ){ // current node is not root
					node = node.parent;
					if ( node.val > currNode.val) {
						return node;
					}
				}
				return null;
			}
		}
	}

- ovjforu October 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

For a given node, if the node has right pointer not null, return the maximum in the right tree else return the first successor node for which given node lies in left subtree.

- Neeraj Kumar Singh September 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that is the correct way to do it

- odie October 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that is the correct way to do it

- odie October 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

it'wrong, if the node has right child, return the right tree's min node value, else if the node has no father there's no next node, if it has father, and the node is father's left child then next node is father, else find father's father until the node is father's left child

- remlostime October 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Node *findNextNode(Node *node)
{
	if (node == NULL)
		return NULL;
	if (node->right)
	{
		Node *p = node->right;
		while(p->left)
			p = p->left;
		return p;
	}
	else
	{
		Node *parent = node->parent;
		while(parent && parent->right == node)
		{
			node = parent;
			parent = parent->parent;
		}
		return parent;
	}
}

- remlostime October 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Preorder Predecessor

package One;

public class PredecessorsNSuccessors {
	public static void main(String[] args) {
		
		BT root=new BT(1);
		BT l=new BT(2);
		BT r=new BT(3);
		BT ll=new BT(4);
		BT lr=new BT(5);
		BT rl=new BT(6);
		BT rr=new BT(7);
		
		root.left=l;	root.right=r;	l.parent=r.parent=root;
		l.left=ll;	l.right=lr;	ll.parent=lr.parent=l;
		r.left=rl;	r.right=rr;	rl.parent=rr.parent=r;
		
		BT.PreorderPredecessor(rr);
	}

}

class BT{
	int v;
	BT parent;
	BT left;
	BT right;
	
	public BT(int v)
	{
		this.v=v;
	}
	
	public static void PreorderPredecessor(BT node)
	{
		if(node==null)
		{
			System.out.println("The node id null");
			return;
		}
		
		if(node.parent==null)
		{
			System.out.println("No PreorderPredecessor exists");
			return;
		}
		
		if(node.parent.left==node)
		{
			System.out.println(node.parent.v);
			return;
		}
		
		if(node.parent.right==node)
		{
			if(node.parent.left==null)
			{
				System.out.println(node.parent.v);
				return;
			}
			
			BT temp=BT.getLastInPreorderTraversal(node.parent.left);		
			System.out.println(temp.v);
		}
	}
	
	public static BT getLastInPreorderTraversal(BT node)
	{
		BT temp;
		
		if(node.right!=null)
		{
			temp=getLastInPreorderTraversal(node.right);
		}
		else if(node.left!=null)
		{
			temp=getLastInPreorderTraversal(node.left);
		}
		else
		{
			temp=node;
		}
		
		return temp;
	}
}

- Deepak Gupta October 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Preorder Successor

public static void  PreorderSuccessor(BT node)
	{
		if(node.left!=null)
		{
			System.out.println(node.left.v);
			return;
		}
		
		if(node.left==null && node.right!=null)
		{
			System.out.println(node.right.v);
			return;
		}
		
		if(node.parent==null)
		{
			System.out.println("NO Successor");
			return;
		}
		
		if(node.parent.left==node && node.parent.right!=null)
		{
			System.out.println(node.parent.right.v);
			return;
		}
		
		BT child=node;
		BT par=node.parent;
		
		BT ps=BT.getPreSuc(child,par);
		
		if(ps==null)
		{
			System.out.println("No Successor");
		}
		else
		{
			System.out.println(ps.v);
		}
	}
	
	public static BT getPreSuc(BT child,BT par)
	{
		if(par==null)
		{
			return null;
		}
		
		if(par.left==child)
		{
			if(par.right!=null)
			{
				return par.right;
			}
		}
		
		return getPreSuc(par,par.parent);
	}

- Deepak Gupta October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inorder Predecessor

public static void InorderPredecessor(BT node)
	{
		if(node.left!=null)
		{
			node=node.left;
			while(node.right!=null)
			{
				node=node.right;
			}
			System.out.println(node.v);
			return;
		}
		
		while(node.parent!=null && node.parent.left==node)
		{
			node=node.parent;
		}
		
		if(node.parent!=null)
		{
			System.out.println(node.parent.v);
		}
		else
		{
			System.out.println("No Inorder Predecessor");
		}
	}

- Deepak Gupta October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Inorder Successor

public static void InorderSuccessor(BT node)
	{
		if(node.right!=null)
		{
			node=node.right;
			
			while(node.left!=null)
			{
				node=node.left;
			}
			
			System.out.println(node.v);
			return;
		}
		
		while(node.parent!=null && node.parent.right==node)
		{
			node=node.parent;
		}
		
		if(node.parent!=null)
		{
			System.out.println(node.parent.v);
		}
		else
		{
			System.out.println("No Inorder Successor");
		}
	}

- Deepak Gupta October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Postorder Predecessor

public static void PostorderPredecessor(BT node)
	{
		if(node.right!=null)
		{
			System.out.println(node.right.v);
			return;
		}
		
		if(node.left!=null)
		{
			System.out.println(node.left.v);
			return;
		}
		
		BT child=null;
		
		while(node.parent!=null && (node.parent.left==null || node.parent.left==node))
		{
			child=node;
			node=node.parent;
		}
		
		if(node.parent==null)
		{
			System.out.println("No Postorder Predecessor");
			return;
		}
		else
		{
			System.out.println(node.parent.left.v);
			return;
		}
	}

- Deepak Gupta October 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Postorder Successor

public static void PostorderSuccessor(BT node)
	{
		if(node.parent==null)
		{
			System.out.println("No Postorder Successor");
			return;
		}
		
		if(node.parent.right==node)
		{
			System.out.println(node.parent.v);
			return;
		}
		
		if(node.parent.right==null)
		{
			System.out.println(node.parent.v);
			return;
		}
		
		BT temp=BT.getFirstInPostOrder(node.parent.right);
		
		System.out.println(temp.v);
	}
	
	public static BT getFirstInPostOrder(BT node)
	{
		if(node.left!=null)
		{
			return getFirstInPostOrder(node.left);
		}
		
		if(node.right!=null)
		{
			return getFirstInPostOrder(node.right);
		}
		
		return node;
	}

- Deepak Gupta October 14, 2012 | 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