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

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

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?

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

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

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

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.

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

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

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

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

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

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

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

Abe asise hi masti me daala....

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

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

the question is wrong!!

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

Muh me lega bhenchod .... ??

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

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

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

well i think the question is worngly framed by the poster

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

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

tera kya jaa raha hai be

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

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

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

``and``

to preserve whitespace.

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())
{
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())
{
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;

}

}

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())
{
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())
{
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;

}

}

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

visit cacktheinterview.org for more interview questions

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

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

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

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

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
{
return;
else
{
}
}

//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

// print binary tree created using inorder

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

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
{
return;
else
{
}
}

//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

// print binary tree created using inorder

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

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.