Deshaw Inc Interview Question
Software Engineer / Developersnode * 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;
}
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?
Here you calculate only the hight of the binary tree without checking root->left->data < root->data <= root->right->data condition.
inorder is wrong...it goes wrong in the inorder successor of the root node...max length bst means max no of nodes
//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)))
}
//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)))
}
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;
}
}
//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;
}
}
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.
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.
#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;
}
#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;
}
From max length BST, does it mean maximum height BST?
- DashDash July 27, 2010