stevenh47
BAN USERNodeType* lowest(NodeType* root,NodeType* p,NodeType*q){
if(root==NULL)return NULL;
if(root==p||root==q)return root;
NodeType* left=lowest(root->left,p,q);
NodeType* right=lowest(root->right,p,q);
if(left!=NULL||right!=NULL)return root;
if(left!=NULL)return left;
if(right!=NULL)return right;
return NULL;
}
// for simplify, I just return the largest common BST root and number of nodes
#include <iostream>
using namespace std;
class NodeType{
public:
NodeType(int v=0):val(v),left(NULL),right(NULL){}
int val;
NodeType* left;
NodeType* right;
};
void updateMax(int & max,NodeType** common,int temp,NodeType* result){
if(max<temp){
max=temp;
*common=result;
}
}
int maxCommonBST(NodeType* root1,NodeType* root2,int & max,NodeType** common){
if(root1==NULL || root2==NULL)return 0;
if(root1->val<root2->val){
/////////////////////////////////////
// root1 can be left child of root2
// or root2 can be right child of root1
maxCommonBST(root1,root2->left,max,common);
maxCommonBST(root1->right,root2,max,common);
return 0;
}
else if(root1->val>root2->val){
////////////////////////////////////
// root1 can be right child of root2
// or root2 can be left child of root1;
maxCommonBST(root1->left,root2,max,common);
maxCommonBST(root1,root2->right,max,common);
return 0;
}
else{
int left=maxCommonBST(root1->left,root2->left,max,common);
int right=maxCommonBST(root1->right,root2->right,max,common);
int total=left+1+right;
updateMax(max,common,total,root1);
return total;
}
}
int main(int argc,char* argv[]){
NodeType* root1=new NodeType(30);
root1->left=new NodeType(15);
root1->right=new NodeType(45);
root1->left->left=new NodeType(10);
root1->left->left->left=new NodeType(5);
root1->left->left->right=new NodeType(13);
NodeType*root2=new NodeType(30);
root2->left=new NodeType(10);
root2->left->left=new NodeType(5);
root2->left->right=new NodeType(13);
int max=0;
NodeType* com=NULL;
maxCommonBST(root1,root2,max,&com);
cout<<com->val<<" "<<max<<endl;
}
#include <iostream>
#include <string>
#define LENGTH(chars) sizeof(chars)/sizeof(char)
using namespace std;
int main(int argc,char* argv[]){
char color[]={'a','b','c','d','e','f','g','h'};
char arr[]={'b','a','a','a','b','c','g','h','g','b'};
int targetIndex=0;
int colorIndex=0;
while(targetIndex<LENGTH(arr)&&colorIndex<LENGTH(color)){
int i=LENGTH(arr)-1;
while(i>=targetIndex){
if(arr[i]==color[colorIndex]){
if(arr[i]!=arr[targetIndex]){
cout<<"Swap:"<<arr[i]<<"("<<i<<") and "<<arr[targetIndex]<<"("<<targetIndex<<")"<<endl;
char temp=arr[targetIndex];
arr[targetIndex]=arr[i];
arr[i]=temp;
--i;
}
++targetIndex;
}
else --i;
}
++colorIndex;
}
for(int i=0;i<LENGTH(arr);++i){
cout<<arr[i]<<" ";
}
cout<<endl;
}
yeah, so if it was me, I would chat with interviewer about this.
- stevenh47 April 04, 2013