jaiwardhan.live
BAN USERAlgorithmic complexity O(n)
Correct me if I am wrong on a case
//using the fact that it is BT and not BST
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <list>
using namespace std;
typedef struct node snode;
struct node
{
int data;
struct node *left, *right;
};
// helper function to allocate new node with given data
struct node* newNode(int data)
{
struct node* node = (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = node->right = NULL;
return (node);
}
//maintain two lists
list<snode *> s1,s2;
//function to search the data for existance
int searchData(snode *root,int data,int mode){
//null node base
if(root==NULL){
return -1;
}
//data is in this node, hence return 1
if(root->data == data){
return 1;
}
//else look left and right for possibilities
//lf is left flag, rf is right flag
int lf,rf;
switch(mode){
//mode 1 for first num, mode 2 for second num
case 1:
if(root->left != NULL){
//first push this node
s1.push_back(root->left);
//then search
lf=searchData(root->left,data,mode);
//since it is found then return 1 flag
if(lf==1){
return 1;
}
//else revert the list to the old state
s1.pop_back();
}
if(root->right!=NULL){
//first push this node
s1.push_back(root->right);
//then search
rf=searchData(root->right,data,mode);
//since it is found then return 1 flag
if(rf==1){
return 1;
}
//else revert the list to the old state
s1.pop_back();
}
break;
case 2:
if(root->left != NULL){
s2.push_back(root->left);
lf=searchData(root->left,data,mode);
if(lf==1){
return 1;
}
s2.pop_back();
}
if(root->right!=NULL){
s2.push_back(root->right);
rf=searchData(root->right,data,mode);
if(rf==1){
return 1;
}
s2.pop_back();
}
break;
}
return -1; //to be safe
}
#define debugStates
void monitorLCA(snode * root,int data1,int data2){
int lf,rf;
//initialize the lists with the root
s1.push_back(root);
s2.push_back(root);
//search entries
lf = searchData(root,data1,1);
rf = searchData(root,data2,2);
#ifdef debugStates
//DEBUG control
cout<<"lf is "<<lf<<", rf is "<<rf<<endl;
//contents display
for(list<snode *>::iterator it=s1.begin();it!=s1.end();++it){
cout<<(*it)->data<<" ";
}
cout<<endl;
//contents display
for(list<snode *>::iterator it=s2.begin();it!=s2.end();++it){
cout<<(*it)->data<<" ";
}
cout<<endl;
#endif // debugStates
if(lf==-1 || rf==-1){
cout<<"data invalid"<<endl;
return;
}
//now maintain the last matched node and start popping
snode * last;
while((s1.front())->data == (s2.front())->data){
last = s1.front();
s1.pop_front();
s2.pop_front();
}
//display answer
cout<<"the lca was "<<(last->data)<<endl;
}
//DRIVER
int main(){
snode * root = newNode(5);
root->left = newNode(3);
root->left->left=newNode(1);
root->left->right=newNode(6);
root->right=newNode(2);
root->right->left=newNode(9);
root->right->right=newNode(8);
monitorLCA(root,100,6);
return 0;
}
simply great solution... :)
- jaiwardhan.live August 17, 2013* i did this in O(n).
* i did this by maintaining a map of characters in a numerical array. since possible values of alphabets relative to 'a' is only from 0-25. so maintained a numerical array of 26 length and initialize each element to 0.
* next to do was traverse the given string and increase each index of the current characcter by one on occurence. [I ASSUMED THAT THE INPUT WAS NOT IN CAPS OR I WOULD HAD ADDED A SMALL stlwr TO FORMAT STRINGS TO LOWER CASE].
* also i ignored occurences of space and eliminated its processing. after mapping the first, i traversed the second and checcked of the index of that character was >0.
* also at the end i made a check for the residue if any related to corner cases. rest comments in the code
/***************************************
* great codes are not starstruck
- you have to bear pain, lots of pain
*code_jazz, anagram
******************************************/
#include<stdio.h>
#include<string.h>
int mapping[26] = {0};
void mapFirst(char *initial)
{
while(*initial != '\0')
{
if(*initial != ' ') //space has not to be processed
{
mapping[*initial-'a']++; //hence record it
}
initial++; //increment it
}//while ends
return;
}//end of mapfirst
int traverseAndCheck(char *ref)
{
int i;
while(*ref != '\0')
{
if(*ref != ' ')
{
if(mapping[*ref-'a'] > 0)
mapping[*ref-'a']--;
else
return 0;
}
ref++;
}
for(i=0;i<26;i++) //checking residue
{
if(mapping[i]!=0)
return 0;
}
return 1;
}//end of trav&chk
int main()
{
char string1[15] = {'\0'};
char string2[15] = {'\0'};
gets(string1); fflush(stdin);
gets(string2); fflush(stdin);
mapFirst(&string1[0]);
if(!traverseAndCheck(&string2[0]))
printf("False");
else
printf("True");
return 0;
}
Simple DP approach to this problem.
Correct me if any corner cases or mistakes
- jaiwardhan.live September 02, 2014