## 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);
}``````

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

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.

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);
}``````

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) );
}``````

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;
}``````

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.")
}

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.")
}

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.")
}

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);
}
}``````

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);
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;
}``````

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.

Comment hidden because of low score. Click to expand.
3

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.

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.

### 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.