Deshaw Inc Interview Question for Software Engineer / Developers






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

From max length BST, does it mean maximum height BST?

- DashDash July 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

node * findMaxBST(node * root, int & N)
{
   if (!root) return N=0, NULL;
   if (!root->left && !root->right) return N=1, root;

   int n1=0;
   node * rootL=findMaxBST(root->left, n1);
   int n2=0;
   node * rootR=findMaxBST(root->right, n2);

   if (!n1 && !n2) return N=1, root;

   bool left = rootL==root->left && rootL->data<root->data;
   bool right = rootR==root->right && rootR->data>=root->data;

   if (left && right) return N=n1+n2+1, root;\

   if (left)
      if (n1+1>n2) return N=n1+1, root;
      else return N=n2, rootR;

   if (right)
      if (n2+1>n1) return N=n2+1, root;
      else return N=n1, rootL;

   if (n1>n2) return N=n1, rootL;

   return N=n2, rootR;
}

- fiddler.g July 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is not clear. The statement does not say how is the input: given a root or given an adjacency matrix of a directed or undirected graph. If it given as an adjacency matrix, the problem is a little hard (at least for me) because the maximum length could be the longest path between 2 leafs.
Also, maximum path is the maximum path from the root to leafs?
In case of a rooted binary tree where a node has a left and a right children and they want to know the height of the tree from the root, the problem is simple:

int height(node n) 
{ 
 if(n == null) return 0; //empty tree or child of a leaf
 if(n.left == null && n.right == null) return 0; // leaf

 return 1 + max(height(n.left), height(n.right));
}

Does anyone know an algorithm when the tree is given as adjacency matrix of a directed graph?

- S July 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here you calculate only the hight of the binary tree without checking root->left->data < root->data <= root->right->data condition.

- fiddler.g July 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't need to know that the tree is BST. So, I don't care about the values inside the tree; I need only the structure of the tree.

- S July 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we not do an inorder traversal and then check for the maximum ascending sequence. This is for a BST with the maximum number of nodes.

If we need to find the BST for the maximum height then think about a different algorithm

- DashDash July 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

inorder is wrong...it goes wrong in the inorder successor of the root node...max length bst means max no of nodes

- Anonymous July 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why is it wrong Anonymous?
If there is a BST in a BT its inorder will give me elements in ascending order, right?

- DashDash July 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

mere naam par kaun post daal raha hai be...

- ajay July 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Abe asise hi masti me daala....

- Surath July 28, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think the poster of this question is not ajay but ss

- Anonymous July 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the question is wrong!!

- Anonymous July 28, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Muh me lega bhenchod .... ??

- Betichod July 28, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

guys plz dont spam here...
this is not the right place flor this work

- Anonymous July 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

well i think the question is worngly framed by the poster

- Anonymous July 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i m afraid some persons are using this site for fun & discussing the placements procedure of their college, its really misuse of this site

- Anonymous July 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

tera kya jaa raha hai be

- saurav jain July 30, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//one function is like isThisBst(node *root)
// this will return 1 if tree is BST else it will return 0
// following approach will count number of nodes in the max bst in a tree
int max_length_bst(node *root)
{
if(root == NULL)
return(0);

i = 0;
j = 0;
k = 0;


if(isbst(root))
i = count(root);
if(isbst(root->left))
j = count(root->left);
if(isbst(root->right)
k = count(root);
return(max(i,j,k,max_length_bst(root->left),max_length_bst(root->right)))
}

- nagpal_dce August 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//one function is like isThisBst(node *root)
// this will return 1 if tree is BST else it will return 0
// following approach will count number of nodes in the max bst in a tree
int max_length_bst(node *root)
{
if(root == NULL)
return(0);

i = 0;
j = 0;
k = 0;


if(isbst(root))
i = count(root);
if(isbst(root->left))
j = count(root->left);
if(isbst(root->right)
k = count(root);
return(max(i,j,k,max_length_bst(root->left),max_length_bst(root->right)))
}

- nagpal_dce August 07, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Surround your code with

and

to preserve whitespace.

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

class node{
int info;
node left;
node right;

public int getinfo()
{
return info;
}
public int getleft(){
return left;
}
public int getright(){
return right;
}
}

class maxb{
public static void main(String[] args)
{
ArrayList<node> st=new ArrayList<node>();
st=maxbst(root,st);
for(node nn: st)
{
System.out.println(nn.getInfo());
}
}
public static ArrayList<node> maxbst(node n, ArrayList<node> s);
{
ArrayList<node> templ=new ArrayList<node>();
templ=s;

if(n.getleft()!=null)
if(n.getinfo()>n.getleft().getinfo())
{
templ.add(n);
maxbst(n.getleft(),templ);
}
else{
templ=maxbst(n.getleft(),new ArrayList<node>());
if(templ.getSize()<s.getSize())
templ=s;
}

ArrayList<node> tempr=new ArrayList<node>();
tempr=s;
if(n.getright()!=null)
if(n.getinfo()<n.getright().getinfo())
{
templ.add(n);
maxbst(n.getright(),tempr);
}
else
{
tempr=maxbst(n.getright(), new ArrayList<node>());
if(tempr.getSize()<s.getSize())
tempr=s;
}

if(templ.getSize()>tempr.getSize())
return templ;
else
return tempr;

}

}

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

//This should work fine if you want to find maximum length BST.

class node{
int info;
node left;
node right;

public int getinfo()
{
return info;
}
public int getleft(){
return left;
}
public int getright(){
return right;
}
}

class maxb{
public static void main(String[] args)
{
ArrayList<node> st=new ArrayList<node>();
st=maxbst(root,st);
for(node nn: st)
{
System.out.println(nn.getInfo());
}
}
public static ArrayList<node> maxbst(node n, ArrayList<node> s);
{
ArrayList<node> templ=new ArrayList<node>();
templ=s;

if(n.getleft()!=null)
if(n.getinfo()>n.getleft().getinfo())
{
templ.add(n);
maxbst(n.getleft(),templ);
}
else{
templ=maxbst(n.getleft(),new ArrayList<node>());
if(templ.getSize()<s.getSize())
templ=s;
}

ArrayList<node> tempr=new ArrayList<node>();
tempr=s;
if(n.getright()!=null)
if(n.getinfo()<n.getright().getinfo())
{
templ.add(n);
maxbst(n.getright(),tempr);
}
else
{
tempr=maxbst(n.getright(), new ArrayList<node>());
if(tempr.getSize()<s.getSize())
tempr=s;
}

if(templ.getSize()>tempr.getSize())
return templ;
else
return tempr;

}

}

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

visit cacktheinterview.org for more interview questions

- CrackTheInterview November 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int MIN = 0, MAX = 0, maxNodes = 0;
Tree *largestBst = NULL, *child = NULL;

int findLargestBst (Tree *p, int min, int max, int maxNodes, Tree &* largestBst, Tree &* child)
{
    if (!p)
        return 0;
    if (min < p->info && p->info < max)
    {
        int leftNodes = findLargestBst (p->left, MIN, p->data, maxNodes, largestBst, child);
        Tree *leftchild = (leftNodes == 0)? NULL:child;

        int rightNodes = findLargestBst (p->right , p->data, MAX, maxNodes, largestBst, child);
        Tree *rightchild = (rightNodes == 0)?NULL:child;

        Tree *parent = new Tree (p->data);
        parent->left = leftchild;
        parent->right = rightchild;
        child = parent;

        maxNodes = leftNodes + rightNodes + 1;
        if (maxNodes > totalNodes)
        {
            totalNodes = maxNodes;
            largestBst = parent;
        }
        return totalNodes;
    }
    else 
    {
        findLargestBst (p, MIN, MAX, maxNodes, largestBst, child);
        return 0;
    }
}
Had found this code on some site. Commen if there are any extreme test cases that have been left out.

- Siraj January 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The above code has slight modifications

int findLargestBst (Tree *p, int min, int max, int &maxNodes, Tree &* largestBst, Tree &* child)
{
    if (!p)
        return 0;
    if (min < p->info && p->info < max)
    {
        int leftNodes = findLargestBst (p->left, MIN, p->data, maxNodes, largestBst, child);
        Tree *leftchild = (leftNodes == 0)? NULL:child;
        int rightNodes = findLargestBst (p->right , p->data, MAX, maxNodes, largestBst, child);
        Tree *rightchild = (rightNodes == 0)?NULL:child;
        Tree *parent = new Tree (p->data);
        parent->left = leftchild;
        parent->right = rightchild;
        child = parent;
        int totalNodes = leftNodes + rightNodes + 1;
        if (maxNodes < totalNodes)
        {
            maxNodes = totalNodes;
            largestBst = parent;
        }
        return totalNodes;
    }
    else
    {
        findLargestBst (p, MIN, MAX, maxNodes, largestBst, child);
        return 0;
    }
}
Had found this code on some site. Comment if there are any extreme test cases that have been left out.

- Anonymous January 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int max_bst(node *ptr,int count)
  {        int height;
           if(ptr==null)
              return count;
           else if(ptr<ptr->left||ptr>ptr->right)count=0; 
           else count++;
           int l=max_bst(ptr->left,count);
           int r=max_bst(ptr->right,count);
           
           if(l>r)
               count=l;
           else if(l<=r)
              count=r;
  }

- ritika August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am assuming that by size you mean number of the nodes present in the BST . Well it actually doesn't matter. 

Searching BST in binary tree (with max size) is same as finding out maximum increasing substring in inorder traversal of that tree.

- sumit September 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include<stdlib.h>
#include<limits.h>

struct node
{
int data;
struct node *left, *right;
};

//function to create a node
struct node * createNode(int val)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp ->right = NULL;
return temp;
}

//print tree in inorder
void printInorder(struct node *head)
{
if(!head)
return;
else
{
printInorder(head->left);
printf("%d->",head->data);
printInorder(head->right);
}
}

//function to check maximum length in a binary tree
int findLength(struct node *root, int min,int max,int len)
{
int max_len = len;
int max_right, max_left;

//if root is null then return length-1.
//len-1 because node is null so parent should get original length back
if(!root)
return len-1;

//check if node satisifes bst property
//if yes then increment length by 1 and process child nodes
//left child node will be smaller than this node
//right child node will be atleast equal to this node
if((min <= root->data) && (root->data < max))
{
//printf("\nmin : %d max: %d data : %d len : %d",min,max,root->data,max_len);
max_left = findLength(root->left,min,root->data,len+1);
max_right = findLength(root->right,root->data,max,len+1);
}
else
{
//else start fresh from current node as length equal to 0
//and min max rules as stated above in comment
max_left = findLength(root->left,min,root->data,0);
max_right = findLength(root->right,root->data,max,0);
}

//finally max length is maximum of current length, left tree length and right tree length
if(max_len < max_left)
max_len = max_left;
if(max_len < max_right)
max_len = max_right;


return max_len;

}

//program execution starts from here
int main(void)
{
int min = INT_MIN;
int max = INT_MAX;

// create a binary tree
struct node *head = NULL;
head = createNode(1);
head->left = createNode(2);
head->right = createNode(3);

(head->left)->left = createNode(4);
(head->left)->right = createNode(9);

(head->left)->right->left = createNode(7);
(head->left)->right->right = createNode(19);

(head->right)->left = createNode(12);
(head->right)->right = createNode(16);

head->right->right->left = createNode(14);
//head->right = createNode(2);

head->right->right->left->left = createNode(8);
head->right->right->left->right = createNode(15);

head->right->right->left->left->left = createNode(5);
head->right->right->left->left->right = createNode(10);

// print binary tree created using inorder
printInorder(head);

//function call to check length
printf("\nmax length is : %d\n", findLength(head,min,max,0));
return 0;
}

- AmritaP August 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include<stdlib.h>
#include<limits.h>

struct node 
{
	int data;
	struct node *left, *right;
};

//function to create a node
struct node * createNode(int val)
{
	struct node *temp = (struct node *)malloc(sizeof(struct node));
	temp->data = val;
	temp->left = temp ->right = NULL;
	return temp;
}

//print tree in inorder
void printInorder(struct node *head)
{
	if(!head)
		return;
	else
	{
		printInorder(head->left);
		printf("%d->",head->data);
		printInorder(head->right);
	}
}

//function to check maximum length in a binary tree
int findLength(struct node *root, int min,int max,int len)
{
	int max_len = len;
	int max_right, max_left;
	
	//if root is null then return length-1. 
	//len-1 because node is null so parent should get original length back
	if(!root)
		return len-1;
	
	//check if node satisifes bst property
	//if yes then increment length by 1 and process child nodes
	//left child node will be smaller than this node
	//right child node will be atleast equal to this node
	if((min <= root->data)  && (root->data < max))
	{
		//printf("\nmin : %d max: %d data : %d len : %d",min,max,root->data,max_len);
		max_left = findLength(root->left,min,root->data,len+1);
		max_right = findLength(root->right,root->data,max,len+1);
	}
	else
	{
		//else start fresh from current node as length equal to 0
		//and min max rules as stated above in comment
		max_left = findLength(root->left,min,root->data,0);
		max_right = findLength(root->right,root->data,max,0);
	}
		
	//finally max length is maximum of current length, left tree length and right tree length
	if(max_len < max_left)
		max_len = max_left;
	if(max_len < max_right)
		max_len = max_right;
		
	
	return max_len;
		
}

//program execution starts from here
int main(void) 
{
	int min = INT_MIN;
	int max = INT_MAX;
	
	// create a binary tree
	struct node *head = NULL;
	head = createNode(1);
	head->left = createNode(2);
	head->right = createNode(3);
	
	(head->left)->left = createNode(4);
	(head->left)->right = createNode(9);
	
	(head->left)->right->left = createNode(7);
	(head->left)->right->right = createNode(19);
	
	(head->right)->left = createNode(12);
	(head->right)->right = createNode(16);
	
	head->right->right->left = createNode(14);
	//head->right = createNode(2);
	
	head->right->right->left->left = createNode(8);
	head->right->right->left->right = createNode(15);
	
	head->right->right->left->left->left = createNode(5);
	head->right->right->left->left->right = createNode(10);
	
	// print binary tree created using inorder
	printInorder(head);
	
	//function call to check length
	printf("\nmax length is : %d\n", findLength(head,min,max,0));	
	return 0;
}

- AmritaP August 07, 2014 | 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