Microsoft Interview Question Software Engineer / Developers
Use a inverted inorder tranversal.that is go to right child first instead of left child. recursively this can be obtained as follows: The most important issue that a global count must be used when considering recursive solution.
where n=2;
void NthMax(Node *root, int n){
if(root == NULL){
return;
}
max(root->right, n);
if(--n == 0){
cout<<"Number is: "<<root->value<<endl;
}
max(root->left, n);
}
}
}
<pre lang="" line="1" title="CodeMonkey2475" class="run-this">
int count=0;
BNode sMax;
public BNode secondMax()
{
secondMax(root);
return sMax;
}
private void secondMax(BNode root)
{
if(root == null)
return;
else
{
secondMax(root.right);
count++;
if(count==2)
{
sMax = root;
return;
}
secondMax(root.left);
}
}
</pre><pre title="CodeMonkey2475" input="yes">to use,
1. place code into your BinaryTree class.
2. in the main() method, call the class by calling secondMax().
i.e. BNode node = secondMax();</pre>
can u pl give me an insertion sequence for which without the line secondMax(root.left) gives wrong output?
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
typedef struct bst * bst;
struct bst
{
int ele;
bst left;
bst right;
};
bst root=NULL;
bst insert(bst root,int x)
{
if(root==NULL)
{
root=(bst)malloc(sizeof(struct bst));
root->ele=x;
root->left=root->right=NULL;
}
else if(x<root->ele)
{
root->left=insert(root->left,x);
}
else
root->right=insert(root->right,x);
return root;
}
void inorder(bst root)
{
if(root)
{
inorder(root->left);
printf("%d ",root->ele);
inorder(root->right);
}
}
int max(bst root)
{
if(root->right==NULL)
return root->ele;
else
return max(root->right);
}
int secondlargest(bst root)
{
if(root->right==NULL)
return max(root->left);
if(root->right&&root->right->right==NULL&&root->right->left==NULL)//checking if right child is leaf node or not
return root->ele;
else
return secondlargest(root->right);
}
int main()
{
int x;
int i=0;
for(;i<6;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
//inorder(root);
printf("\n%d\n",secondlargest(root));
return 0;
}
1) O(lg N)
- Find maximum O(lg N)
- Find predecessor O(lg N)
2) You could also use in-order traversation. But this would be O(N).
first method costs O(n) too in worst case. What if tree is skewed to right, i.e. height = n-1.
int secondMaxInBST(node* root)
{
int max=0, secondMax=0;
getSecondMaxInBST(root,max,secondMax);
return secondMax;
}
void getSecondMaxInBST(node* root, int& max, int& secondMax)
{
if(root)
{
getSecondMaxInBST(root->left, max, secondMax);
secondMax=max;
max=root->data;
getSecondMaxInBST(root->right, max, secondMax);
}
}
@Anonymous
Good point. In case of duplicates we can have following three implementation of BST:
1. Each node contains a count variable. So when there is a duplicate value then no need to add new node just increase count.
2. Add new node at right.
3. Add new node at left.
Above implementation works correctly for 1 but need to add check
if(secondMax < max)
seconMax=max;
to work with 2 and 3.
Here's the pseudo-code for my approach
Node Helper(node)
if(node is leaf)
return null
else if(only left subtree exists)
return FindMax(root->left)
else
tempNode = helper(root->right)
if(tempNode is null)
return node
else return node
Node Find2ndLargest(root)
if(root is null)
error()
node = Helper(root)
if(node is null)
error()
else return node
I Guess its easy to write the FindMax(node) function, so i'll not write it here. In case of a balanced BST, this should have a complexity of O(log(N))
this is different::::
#include<stdio.h>
#include <conio.h>
#include<malloc.h>
#include<ctype.h>
struct node{
int data;
struct node* lchild;
struct node* rchild;
}*root;
int inorder(struct node* ptr){
int j;
static int i=0,a=0;
if(root->lchild == NULL && root->rchild == NULL)
{
printf("\nonly largest or ");
return root->data;
}
if(ptr){
inorder(ptr->lchild);
i++;
if(i==2)
a=ptr->data;
inorder(ptr->rchild);
}
return a;
}
struct node * makenode()
{
struct node * root;
int data;
printf("\n Enter the node data : ");
scanf("%d",&data);
root = (struct node *) malloc (sizeof(struct node));
root->data=data;
root->lchild=NULL;
root->rchild=NULL;
return (root);
}
void maketree(struct node * root)
{
char ans;
printf("\n Do you want to create the left subtree of %d (y/n)? ",root->data);
fflush(stdin);
ans=toupper(getche());
if (ans=='Y')
{
root->lchild=makenode();
maketree(root->lchild);
}
printf("\n Do you want to create the Right subtree %d (y/n)? ",root->data );
fflush(stdin);
ans=toupper(getche());
if (ans=='Y')
{
root->rchild=makenode();
maketree(root->rchild);
}
}
void main(){
int b;
root=NULL;
root=makenode();
maketree(root);
b=inorder(root);
printf("\nthe second largest data %d",b);
}
#include<stdio.h>
#include <conio.h>
#include<malloc.h>
#include<ctype.h>
struct node{
int data;
struct node* lchild;
struct node* rchild;
}*root;
int inorder(struct node* ptr){
int j;
static int i=0,a=0;
if(root->lchild == NULL && root->rchild == NULL)
{
printf("\nonly largest or ");
return root->data;
}
if(ptr){
inorder(ptr->rchild);
i++;
if(i==2)
a=ptr->data;
inorder(ptr->lchild);
}
return a;
}
struct node * makenode()
{
struct node * root;
int data;
printf("\n Enter the node data : ");
scanf("%d",&data);
root = (struct node *) malloc (sizeof(struct node));
root->data=data;
root->lchild=NULL;
root->rchild=NULL;
return (root);
}
void maketree(struct node * root)
{
char ans;
printf("\n Do you want to create the left subtree of %d (y/n)? ",root->data);
fflush(stdin);
ans=toupper(getche());
if (ans=='Y')
{
root->lchild=makenode();
maketree(root->lchild);
}
printf("\n Do you want to create the Right subtree %d (y/n)? ",root->data );
fflush(stdin);
ans=toupper(getche());
if (ans=='Y')
{
root->rchild=makenode();
maketree(root->rchild);
}
}
void main(){
int b;
root=NULL;
root=makenode();
maketree(root);
b=inorder(root);
printf("\nthe second largest data %d",b);
}
Check for the highest node
A) If its left is NUll then its parent is 2nd highest.
B)else find the maximum in its left sub tree.
struct node *second_highest(struct node *p)
{
struct node *k;
while(p->right!=NULL)
{
k=p;
p=p->right;
}
if(p->left!=NULL)
{
k=p->left;
while(k->right!=NULL)
{
k=k->right;
}
return(k);
}
else
return(k);
}
node *max(node *root)
{
if(root==NULL)
return NULL;
else if(root->right==NULL)
return root;
else
return max(root->right);
}
node *secondmax(node *root,node *temp)
{
if(root==NULL) return root;
else if(root->left==NULL && root->right==NULL) return temp;
else if(root->right==NULL)
return max(root->left);
else
return secondmax(root->right,root);
}
it is actually to find the in-order predecessor of the last node, say N.
simple two cases.
1. N has no left child, then the parent of N is the return. (no need to traverse, use an additional point to the parent while doing recursive)
2. N does have a left child. the rightmost left child of N is the return.
both cases are O(lgN) since it is BST, not binary tree.
public TreeNode secondLargest(TreeNode root){
if(root == null || root.left==null && root.right==null)
return null;
if(root.right != null){
while(root.right.right != null){
root = root.right;
}
}
else{
root = root.left;
while(root.right != null){
root = root.right;
}
}
return root;
}
O(logN) instead of O(N)
- wangxuyang October 08, 2012NodeType* getSecondMax(NodeType* root) { if(root == NULL) { return NULL; } NodeType* pre = NULL; NodeType* max = root; while(max->r) { pre = max; max = max->r; } if(pre == NULL) { if(root->l == NULL) { return NULL; } else { return rightMostNode(root->l); } } else if(pre->l == NULL) { return pre; } else { return rightMostNode(pre); } }