Facebook Interview Question for SDE1s


Country: United States




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

Since BinaryTree doesn't maintain any ordering properties for child nodes, worst case is in-order successor is the leaf node, which means we have to traverse the whole tree and find the next closest biggest element with O(n) complexity.
However we can try to optimize it and look for the node that have n.val+1 along the traversal, since n.val + 1 will be guaranteed the next successor, since there is no smaller int between n.val and v.val + 1.

- Marcello Ghali May 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We use an iterative inorder traversal. Once we find the needle, we return the next node in the inorder traversal.

TreeNode*
inOrderSuccessor(TreeNode* root, TreeNode* needle)
{
  if(root == nullptr) return nullptr;
  if(needle == nullptr) return nullptr;

  std::vector<TreeNode*> stk;
  bool found = false;
  while(root != nullptr && !stk.empty()){
    if(root != nullptr){
      stk.push_back(root);
      root = root->left;
    } else {
      root = stk.back();
      stk.pop_back();
      {
	if(found){
	  return root;
	}
	if(root == needle){
	  found = true;	
	}
      }
      root = root->right;
    }
  }
  return nullptr;
}

- fred May 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Language C#

public class TreeNode
{
	public int val;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int val)
	{
		this.val = val;
	}
}

public class Solution
{
	public TreeNode inOrderSucccessor(TreeNode root, TreeNode input)
	{
		SuccessorTreeNode successorNode = null;
		successorNode = inOrderSucccessor(root, input, successorNode);
	}
	
	private SuccessorTreeNode inOrderSucccessor(TreeNode root, TreeNode input, SuccessorTreeNode successorNode)
	{
		if(root == null)
		{
			return null;
		}
		SuccessorTreeNode node = inOrderSucccessor(root.left, input, successorNode);
		if(node != null && node.isFound && node.successorNode == null)
		{
			node.successorNode = root;
			return node;
		}
		else if(node != null && node.isFound)
		{
			return node;
		}
		if(root == input)
		{
			successorNode = new SuccessorTreeNode(true);
		}
		return inOrderSucccessor(root.right, input, successorNode);
	}
}

public class SuccessorTreeNode
{
	public TreeNode successorNode;
	public bool isFound;
	public SuccessorTreeNode()
	{
		isFound = false;
		successorNode = null;
	}
	public SuccessorTreeNode(bool isFound)
	{
		this.isFound = isFound;
	}
}

Complexity : O(N) + O(1)

- sonesh May 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use stack for the inorder traversal iteratively.
if the key is found, set a boolean flag ,which can be used in the next iteration to return the value of the inorder successor

public Integer inOrderSuccessor(BTreeNode current,Integer key) {
Stack<BTreeNode> s1=new Stack<BTreeNode>();

boolean elementFound=false;
while(true) {

while(current!=null) {
s1.push(current);
current=current.left;
}
if(s1.isEmpty())break;
current=s1.pop();
if(elementFound) {
return current.data; //next element to the key
}
if(current.data==key) {
elementFound=true; //this boolean can be used in the next iteration
}

//System.out.print(current.data+" ");
current=current.right;


}
return null;
}

- prahl May 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If the node has right child, the successor is the deepest left node, starting from the right child.
If the node doesn't have right child, we can get the path from root to to the node, and find the successor (iterating from the end of the path) as the first node which has left child.

class Node {
	public:
		Node(int val)
		{
			val_ = val;
			left_ = right_ = NULL;
		}
		int val_;
		Node *left_, *right_;		
};

vector<Node *> PathToNode(Node *root, Node *node)
{
	class StackEntry {
		public:
			Node *node_;
			int child_idx_;
			StackEntry(Node *node, int child_idx)
			{
				node_ = node;
				child_idx_ = child_idx;
			}
	};
	vector<Node *> path;
	if (root &&
		node)
	{
		stack<StackEntry> st;
		st.push(StackEntry(root, 0));
		while (!st.empty()) {
			StackEntry e = st.top();
			st.pop();
			if (e.node_) {
				if (e.node_ == node) {
					path.push_back(e.node_);
					while (!st.empty()) {
						path.push_back(st.top().node_);
						st.pop();
					}
					return path;
				}
				if (e.child_idx_ == 0) {
					st.push(StackEntry(e.node_, e.child_idx_ + 1));
					st.push(StackEntry(e.node_->left_, 0));
				} else if (e.child_idx_ == 1) {
					st.push(StackEntry(e.node_, e.child_idx_ + 1));
					st.push(StackEntry(e.node_->right_, 0));
				}
			}
		}
	}
	return path;
}

Node *DeepestLeft(Node *node)
{
	Node *n = node;
	while (n &&
			n->left_)
	{
		n = n->left_;
	}
	return n;
}

Node *GetInorderSuccessor(Node *root, Node *node)
{
	if (root &&
		node)
	{
		if (node->right_) {
			return DeepestLeft(node->right_);
		} else {
			vector<Node *> path = PathToNode(root, node);
			for (int i = 0; i + 1 < path.size(); ++i) {
				if (path[i + 1]->left_ == path[i]) {
					return path[i + 1];
				}
			}
		}
	}
	return NULL;
}

- Alex May 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

'''
Given a Binary tree (Not binary Search Tree ), find the inorder successor of a node.
     2
    / \
   0    4
    \  /  \
     1 3   5

'''

import sys

class node :

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        l = r = ''
        if self.left != None:
            l += str(self.left)

        result = str(self.value)

        if self.right != None:
            r += str(self.right)

        return l + ' ' + result + ' ' + r

def createBTree(low, high):

    if(low > high):
        return None

    mid = (low + high)/2
    #print 'low: '+ str(low) + ' mid: '+str(mid) + ' high: '+ str(high)
    n = node(mid)

    n.left = createBTree(low, mid-1)
    n.right = createBTree(mid+1, high)

    return n

def findInOrderSuccessor(root, key, found):

    l = r = None

    if root.left :
        l,found = findInOrderSuccessor(root.left, key, found)

    if (found) :
        return root, found

    if (root.value == key):
        found = True

    if root.right:
        r, found = findInOrderSuccessor(root.right, key, found)

    if l :
        return l, found
    elif r :
        return r, found
    else :
        return (None, found)

def main():
    root = createBTree(0, 10)
    print str(root)
    key = 5
    successor, found = findInOrderSuccessor(root, key, False)

    if successor:
        print 'successor for '+ str(key)+ ' is ' + str(successor.value)
    else:
        print 'successor not found '
if __name__ == '__main__':
    sys.exit(main())

- akshaydorwat June 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Complexity = O(n) 
public TreeNode inOrderSuccessor(TreeNode root, TreeNode n)  {
	if(n.right != null) {
		TreeNode ans = n;
		while(ans.left!=null)ans = ans.left;
		return ans;
	}
return findParent(root, n);
}

public TreeNode findParent(TreeNode root, TreeNode n) {
  if(root == null)return null;
   
  if(root.left == n || root.right == n) return root;
  TreeNode ans = findParent(root.left,n);
   if(ans !=null)return ans;
   return findParent(root.right,n);
}

- Anonymous May 01, 2017 | 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