Bloomberg LP Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




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

public static boolean isValidBST(TreeNode root) {
	return validate(root, Integer.MIN_VALUE, INTEGER.MAX_VALUE);
}

public static boolean validate(TreeNode root, int min, int max) {
	if (root == null) {
		return true;
	}
	
	if (root.data <= min || root.data >= max) {
		return false;
	}
	
	return validate(root.left, min, root.data) && validate(root.right, root.data, max);
}

- nikamirulmukmeen March 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

I don't think this and any of the other solutions are sufficient
to make sure the BST properties are satisfied, we need to make sure all values in left subtree are smaller than the root (instead of only the left node value)

- Anonymous April 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't think this and all the other solutions here are sufficient

to check if a tree is a BST, we would need to check if all values in the left subtree are smaller than the value at the root (instead of only checking the left node value)
and vice versa for the right subtree

- nl April 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

public boolean isBST(Node n) {
	
	if (n == null) {

		return true;
	}

	boolean checkRight = (n.right == null) ? true : (n.right.value > n.value) ? true : false;
	boolean checkLeft = (n.left == null) ? true : (n.left.value < n.value) ? true : false;

	return checkRight && checkLeft && isBST(n.left) && isBST(n.right);
}

- Skor March 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I like nikamirumukmeen's solution but I didn't want to have to keep creating 2 extra temporary variables each time we validated another node although I ended up with the same problem by creating 2 bool each call. Also wasn't a fan of copying the whole object on each validate call when we could just pass a pointer.

bool IsValidBST(BTnode* rootNode)
{
	return ValidateNode(rootNode);
}

bool ValidateNode(BTnode* node)
{
	bool bValidLeft = true;
	bool bValidRight = true;

	if (node->m_pLeft != NULL)
	{
		if (node->m_pLeft->m_nKey < node->m_nKey)
			bValidLeft = ValidateNode(node->m_pLeft);
		else
			return false;
	}

	if (bValidLeft && node->m_pRight != NULL)
	{
		if (node->m_pRight->m_nKey > node->m_nKey)
			bValidRight = ValidateNode(node->m_pRight);
		else
			return false;
	}

	return bValidLeft && bValidRight;
}

- CareerCupDom March 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your solution is not correct. comparing every node with left child and right child won't lead to the correct solution. Actually left sub tree can't have value greater than the root and the right sub tree can't have value less than the root. That's the reason you need to keep track of min and max.

- maverick55 December 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool IsBinarySearchTree(node* n)
{
    if (n == null)
      return True;
    if (n->left == null and n->right == null)
      return True;

    bool checkleft = True, checkright = True;
    
    
    if (n->left != null)
        if (n->content < n->left->content)
            return False;
        else
            checkleft = IsBinarySearchTree(n->left);
            
    if (n->right != null)
        if (n->content > n->lright->content)
            return False;
        else
            checkright = IsBinarySearchTree(n->right);
     
     return (checkleft == checkright == True)?True:False;
}

- hiuhchan March 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Would this work on, say,

4
               2          6
            1    9    5    8

?

- Sid March 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Would these solutions work on, say,

4
                           2              6
                       1      9      5      8

?

- Sid March 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This seems to work better. I'm just doing an inorder traversal of the tree and checking if the elements are in increasing order.

bool checkTree(Node * n) {
	if ( n != NULL ) {
		static int previous = -2147483648;
		checkTree(n->left);
		if(n->data < previous){
			return false;
		}	
		else {
			previous = n->data;
		}
		checkTree(n->right);
			
	}
	return true;
}

- Siddhartha March 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static boolean isBST(Node root, int min, int max) {
	if(root == null)
		return true;
	if(root.left.data > max || root.right.data <= min)
		return false;
	return (isBST(root.left, min, root.data) && isBST(root.right.data, root.data, max));
}

- codegirl March 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool IsBST(BTnode* node)
{
if ( node == 0 )
return true;

if (node->m_left != NULL)
{
if (node->m_left->m_key > node->m_key)
return false;
if ( !IsBST(node->m_left) )
return false;
}

if (node->m_right != NULL)
{
if (node->m_right->m_key < node->m_key)
return false;
if ( !IsBST(node->m_right) )
return false;
}

return true;
}

- newbie April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isBinarySearchTree(TreeNode* root) {
  return (root->left != nullptr ? root->left->val < root->val : true)
         && (root->right != nullptr ? root->right->val > root->val : true)
         && (root->left != nullptr ? isBinarySearchTree(root->left) : true)
         && (root->right != nullptr ? isBinarySearchTree(root->right) : true);
}

- balazskemenes August 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isBinarySearchTree(TreeNode* root) {
  return (root->left != nullptr ? root->left->val < root->val : true)
         && (root->right != nullptr ? root->right->val > root->val : true)
         && (root->left != nullptr ? isBinarySearchTree(root->left) : true)
         && (root->right != nullptr ? isBinarySearchTree(root->right) : true);

}

- balazskemenes August 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isBinarySearchTree(TreeNode* root) {
  return (root->left != nullptr ? root->left->val < root->val : true)
         && (root->right != nullptr ? root->right->val > root->val : true)
         && (root->left != nullptr ? isBinarySearchTree(root->left) : true)
         && (root->right != nullptr ? isBinarySearchTree(root->right) : true);

}

- balazskemenes August 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <limits>

struct bt_node
{
	int value;
	bt_node *left, *right;
};

static bool check_bst_left(bt_node *bt, int parent_value, int lbound, int rbound);
static bool check_bst_right(bt_node *bt, int parent_value, int lbound, int rbound);

bool check_bst(bt_node *bt, bt_node *parent)
{
	return check_bst_left(bt->left, bt->value, std::numeric_limits<int>::min(), bt->value)
		&& check_bst_right(bt->right, bt->value, bt->value, std::numeric_limits<int>::max());
}

static bool check_bst_left(bt_node *bt, int parent_value, int lbound, int rbound)
{
	if (!bt)
		return true;
	return bt->value >= lbound && bt->value <= parent_value
		&& check_bst_left(bt->left, bt->value, lbound, bt->value)
		&& check_bst_right(bt->right, bt->value, bt->value, rbound);
}

static bool check_bst_right(bt_node *bt, int parent_value, int lbound, int rbound)
{
	if (!bt)
		return true;
	return bt->value >= parent_value && bt->value <= rbound
		&& check_bst_left(bt->left, bt->value, lbound, bt->value)
		&& check_bst_right(bt->right, bt->value, bt->value, rbound);
}

- pavelp May 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool checkBST(treeNode* n){
    vector<int> cache;
    inOrderTraverse(n);

    int last = *cache.begin()
    for(auto it=cache.begin()+1; it!=cache.end(); it++){
        if (*it < last){ return false; }
    }
    return true;
}

void inOrderTraverse(treeNode* n, vector<int> &cache){
    if(n==NULL){ return ;}
    inOrderTraverse(n->Left, cache);
    visitNode(n, cache);
    inOrderTraverse(n->Right, cache);
}

void visitNode(treeNode* n, vector<int> &cache){
    cache.push_back(n->data);
}

- Jimmy July 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Order Traversal with data saved from last and current

static int prev = 0;
static int curr = 0;
public static boolean IsValidBST(BinaryTree root){
if (root == null)
return true;
if(!IsValidBST(root.left))
return false;
prev = curr;
curr = root.data;
if(prev >= curr){
System.out.println("Not a BST Tree");
return false;
}
if(!IsValidBST(root.right))
return false;
return true;
}

- HS September 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can always do in order traversal and save current and prev value..

static int prev = 0;
    static int curr = 0;
    public static boolean IsValidBST(BinaryTree root){
        if (root == null)
                return true;
        if(!IsValidBST(root.left))
            return false;
        prev = curr;
        curr = root.data;
        if(prev >= curr){
            System.out.println("Not a BST Tree");
            return false;
        }
        if(!IsValidBST(root.right))
            return false;
        return true;
    }

- HS September 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int prev = 0;
    static int curr = 0;
    public static boolean IsValidBST(BinaryTree root){
        if (root == null)
                return true;
        if(!IsValidBST(root.left))
            return false;
        prev = curr;
        curr = root.data;
        if(prev >= curr){
            System.out.println("Not a BST Tree");
            return false;
        }
        if(!IsValidBST(root.right))
            return false;
        return true;
    }

- HS September 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
private static boolean ans = true;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
ans = true;

solve(root);


return ans;
}

private void solve(TreeNode root) {

if(root == null) return;

dfs(root.left, root.val, -1);
dfs(root.right, root.val, 1);

solve(root.left);
solve(root.right);

}

void dfs(TreeNode node, int val, int p) {

if(node == null) return;

if(p==-1 && node.val >= val){
ans = false;
return;
}
else if(p==1 && node.val <= val) {
ans = false;
return;
}

dfs(node.left, val, p);
dfs(node.right, val, p);
}

}}

- Arthur Okeke March 05, 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