CareerCup

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

Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person



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

static bool IsBST(Node root, int low, int high)
        {
            if (root == null)
                return true;

            if (root.data < low || root.data > high)
                return false;

            return IsBST(root.left, low, root.data-1) && IsBST(root.right, root.data+1, high);
        }

- codealtecdown September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node {	

	...
	
	public boolean isBST() {
		boolean valid = true;
		
		if (left != null) {
			if (left.data <= data) {
				valid = left.isBST();
			} else {
				return false;
			}
		}
		
		if (!valid) {
			return false;
		}
		
		if (right != null) {
			if (right.data > data) {
				valid = right.isBST();
			} else {
				return false;
			}
		}
		
		return valid;
	}
	
}

O(N) time, O(1) space

- Iuri Sitinschi September 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is not O(1) space. You are using recursion, that means implicit method stacks.

Worst case space complexity O(N) -- In case it is a totally unbalanced binary search tree, like a linked list, the space complexity would be O(N) since all the nodes have to be traversed as part of successive recursion.

Average case space complexity: O(lg(n)) -- In case of a balanced binary search tree, the space complexity would be O(lg(n)). First all left, then all right.

Best case space complexity O(1) -- In case of a failure at early stages.

- Shivam Maharshi October 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the C++ solution of the question.
BST should have left side of trees smaller than parent and right side of trees larger than the parent.
After inorder search, checking if the order is preserved can tell whether the tree is BST.

#include <iostream>
#include <vector>
using namespace std;

struct node {
  node* left;
  node* right;
  int value;
  node(int v):value(v), left(0), right(0){}
};

vector<int> results;

void inorder(node *n)
{
  if (!n)
    return;
  inorder(n->left);
  results.push_back(n->value);
  inorder(n->right);
}

bool check_order(vector<int>&result)
{
  int ascending = INT_MIN;

  for (int i = 1; i < result.size(); i++)
  {
    if (result[i-1]==result[i])
      continue;

    if (ascending == INT_MIN)
    {
      ascending = (result[i-1]< result[i]);
    }else if (ascending != (result[i-1]<result[i]))
    {
      return false;
    }
  }
  return true;
}

bool is_bst(node *r)
{
  inorder(r);
  return check_order(results);
}

- hankm2004 October 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int isBST(struct node* node) { 
  return(checkIsBST(node, INT_MIN, INT_MAX)); 
}

int checkIsBST(struct node* node, int min, int max) { 
  if (node==NULL) 
	return true;

  if (node->data<min || node->data>max) 
	return false;

  return 
     ( checkIsBST(node->left, min, node->data) && 
       checkIsBST(node->right, node->data+1, max) ); 
}

- R@M3$H.N October 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool IsBST(const Node *root)
{
	if (root == NULL) {
		return true;
	}
	
	vector<int> elements;
	return InorderOrderTravel(root, elements);
}

bool InorderOrderTravel(const Node *root, vector<int>& elements)
{
	if (root == NULL) {
		return true;
	}
	
	if (root->left != NULL &&
		!InorderOrderTravel(root->left, elements)) {
		return false;
	}
	
	// fast fail
	if (elements.size() > 0 &&
		elements[elements.size() - 1] > root->data) {
		return false;
	}
	elements.push_back(root->data);
	
	if (root->right != NULL &&
		!InorderOrderTravel(root->right, elements)) {
		return false;
	}
	
	return true;
}

- Rohit J December 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class TreeNode {
var value: Int?
var leftChild: TreeNode?
var rightChild: TreeNode?
}

func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
print("value: " + String(node.value!))
print("min: " + String(min))
print("max: " + String(max))

if node.value! < min || node.value! > max
{
return false
}

if let leftChild = node.leftChild {
if isBST(leftChild, min: min, max: node.value!) == false {
return false
}
}

if let rightChild = node.rightChild {
if isBST(rightChild, min: node.value!, max: max) == false {
return false
}
}

return true
}

// Creating BST
let minValue = Int.min
let maxValue = Int.max

let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil

let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil

let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil

let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil

let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7

let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15

let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13

if isBST(node10, min: minValue, max: maxValue) == true {
print("Tree is BST.")
}else {
print("Tree is not BST.")
}

- @HappyCoding, Swift version April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class TreeNode {
var value: Int?
var leftChild: TreeNode?
var rightChild: TreeNode?
}

func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
print("value: " + String(node.value!))
print("min: " + String(min))
print("max: " + String(max))

if node.value! < min || node.value! > max
{
return false
}

if let leftChild = node.leftChild {
if isBST(leftChild, min: min, max: node.value!) == false {
return false
}
}

if let rightChild = node.rightChild {
if isBST(rightChild, min: node.value!, max: max) == false {
return false
}
}

return true
}

// Creating BST
let minValue = Int.min
let maxValue = Int.max

let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil

let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil

let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil

let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil

let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7

let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15

let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13

if isBST(node10, min: minValue, max: maxValue) == true {
print("Tree is BST.")
}else {
print("Tree is not BST.")
}

- @HappyCoding, Swift version April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class TreeNode {
var value: Int?
var leftChild: TreeNode?
var rightChild: TreeNode?
}

func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
print("value: " + String(node.value!))
print("min: " + String(min))
print("max: " + String(max))

if node.value! < min || node.value! > max
{
return false
}

if let leftChild = node.leftChild {
if isBST(leftChild, min: min, max: node.value!) == false {
return false
}
}

if let rightChild = node.rightChild {
if isBST(rightChild, min: node.value!, max: max) == false {
return false
}
}

return true
}

// Creating BST
let minValue = Int.min
let maxValue = Int.max

let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil

let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil

let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil

let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil

let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7

let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15

let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13

if isBST(node10, min: minValue, max: maxValue) == true {
print("Tree is BST.")
}else {
print("Tree is not BST.")
}

- Anonymous April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In-order traversal solution, O(1) space. you only need to remember the previous visited node.

struct Node {
   Node* left, *right;
   int val;
};

//global variable
bool foundFirst = false;
int previous = 0;

bool isBST(Node* root) {
   if (root == NULL) return true;
 
   if(isBST(root->left) ){
      if(!foundFirst) {
		 foundFirst = true;
	  } else {
	     if (root->val < previous) 
		    return false;
		 }		 
	  }
	  previous = root->val;
	  return isBST(root->right);   
   }
}

- DavidHo April 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void inorder(Node node, ArrayList nodes) {
        if (node != null) {
            inorder(node.left, nodes);
            nodes.add(node.value);
            inorder(node.right, nodes);
        }
    }

boolean isBST(ArrayList<Integer> inorder) {
        for(int i = 0; i < inorder.size() - 1; i++) {
            if (inorder.get(0).compareTo(inorder.get(i + 1)) > 0){
                return false;
            }
        }

        return true;
    }

- Yogourta May 30, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why is facebook ask such easy question? Just do inorder tree traversal and that is, everytime you traversal to it's own node, put that content into some data structure. Doesn't matter what it is. the data structure can be array, stack, queue. Then check the content in the data structure. For example, for stack, check and make sure every time you pop something from the stack, the next item you pop has to be less than or equal to the previous item it was pop. That it all.

- hiuhchan September 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

maybe think about how you can solve it without a data structure first before judging the level of a question. every question has a easy solutions but it's the optimization that makes a question hard.

- Nio October 12, 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