email.suman.roy
BAN USERlogn solution
/*
Given - a number (n) and a sorted i_array
Find a number in the i_array having least difference with the given number (n).
Developed By :Suman roy
Email : email.suman.roy@gmail.com
*/
#include<iostream>
#include<stdlib.h>
using namespace std;
int Min( int data1 , int data2, int search){
if ( data2 > data1 ){
int k=data2-search;
int l=search - data1;
if ( k > l ) return data1;
else return data2;
}
else {
int k=data1-search;
int l=search - data2;
if ( k> l)return data2;
else return data1;
}
}
int mid;
int Search ( int * i_array , int i_start , int i_end , int& i_search ){
mid= ( i_start + i_end ) / 2;
if ( i_array [ mid ] == i_search ) return i_search;
else {
if ( mid == 0 )
return Min( i_array [mid ] , i_array [mid+1],i_search );
if ( mid== i_end ) return Min ( i_array [ mid ] , i_array [ mid - 1 ] , i_search );
if ( i_array[mid ] <=i_search & i_search<= i_array [ mid + 1] ) return Min( i_array [ mid] ,i_array [mid + 1], i_search );
if( i_array [mid ] >=i_search & i_search >=i_array [ mid - 1 ] )retUrn Min ( i_array [ mid ] , i_array [mid - 1 ] , i_search );
if( i_array [ mid ] >i_search ) Search ( i_array , i_start , mid-1 , i_search );
else Search ( i_array , mid+1 , i_end , i_search );
}
}
int main(){
int i_array[]={2, 5 ,7 , 12 , 17 , 24 , 26 , 29};
int i_array_size , i_search_no;
i_array_size=8;
std::cout<<"Enter search element \n";
std::cin>>i_search_no;
int i_start=0;
std::cout<<Search( i_array , i_start , i_array_size - 1 , i_search_no );
return 0;
}
My code is working you can try ,I always welcome peoples who will find out sum issue :
/*
Pattern Matching
----------------
Characters: a to z
Operators: * +
* -> matches zero or more (of the character that occurs previous to this operator)
+ -> matches one or more (of the character that occurs previous to this operator)
Output if a given pattern matches a string.
Example:
pattern:a*b
string:aaab b, ab, aab, aaab, ab
output:1
pattern:a+aabc
string:ab aabc, aaabc, aaaabc ..
output:0
pattern:aa*b*ab+
string:aab aab, aabab, aaaabbab
output:1
pattern: a+a*b*
string: a ab, aab, aaabb
output: 1
Valid Assumptions: Please assume that both the pattern and string input are valid
*/
#include<iostream>
#include<string>
using namespace std;
typedef std::string::iterator i_string;
i_string temp;
bool Match( i_string re_start , i_string str_start , i_string re_end , i_string str_end ){
if ( re_start != re_end || str_start != str_end ){
if( *( re_start + 1 ) == *"*" ){
if( *re_start == *str_start ){
if ( Match(re_start + 2 , str_start , re_end , str_end ) |
Match ( re_start , str_start + 1 , re_end , str_end ) |
Match( re_start + 2 , str_start + 1 , re_end , str_end ) ) return true ;
else return false;
}
else
return ( Match (re_start + 2 , str_start , re_end , str_end ) );
}
else if( * ( re_start + 1 ) == *"+" ){
if ( *re_start == *str_start ){
*(re_start + 1 )=*"*";
return ( Match ( re_start , str_start + 1 , re_end , str_end ) );
}
else return false;
}
else if ( *re_start == *str_start ) return ( Match(re_start + 1 , str_start +1 , re_end , str_end ) );
else return false;
}
else{
if( re_start==re_end & str_start==str_end )
return true;
else return false;
}
}
int main(){
string s_re, s_string;
std::cout<<"enter RE\n";
std::cin>>s_re;
std::cout<<"Enter string\n";
std::cin>>s_string;
i_string inm_re,inm_str,inm_re_end, inm_str_end;
inm_re=s_re.begin();
inm_str=s_string.begin();
inm_re_end=s_re.end();
inm_str_end=s_string.end();
bool k=Match ( inm_re , inm_str , inm_re_end , inm_str_end );
k==false?std::cout<<"Not accepted\n":std::cout<<"Accepted\n";
return 0;
}
#include<iostream>
#include<string>
using namespace std;
int main(){
int *check=new int[256];
int heighest=0,pos1=0;
int second_heighest=0,pos2=0;
string s="ssssaaxxx";
for ( std::string::iterator ii=s.begin() ; ii!=s.end() ; ii++ ){
//std::cout<<( *ii)<<std::endl;
check[ int(*ii)]+=1;
if ( check [ int (* ii ) ]>heighest ){
//std::cout<<"1st"<<( *ii)<<std::endl;
if( second_heighest != 0 ){
second_heighest=heighest;
pos2=pos1;
}
heighest=check [ * ii ];
pos1=int(*ii);//std::distance( s.begin(), ii );
//std::cout<<":pos2=:"<<pos2<<std::endl;
} else {
if ( check [ int (* ii ) ] > second_heighest ){
//std::cout<<"2nd"<<( *ii)<<std::endl;
second_heighest=check [ * ii ];
pos2=int(*ii);
}
}//std::cout<<pos1<<":"<<pos2<<std::endl;
//std::cout<<*ii;
}
int a;
//std::cout<<"Pos2="<<pos2<<std::endl;
char c=(char)pos2;
//std::cout<<c<<std::endl;
std::cout<<"second heighest "<<c<<" : "<<second_heighest<<std::endl;
}
output :
suman@suman-laptop:/media/D/coding/c++_stuff$ ./a.out
second heighest x : 3
we can construct a tree then we can print data breadth wise(bfs )
- email.suman.roy July 15, 2013Void DiffPiar( int array , int array_size){
map<int , int> store //cretae a map to store resulte
int temp;
for ( i=array_size -1 ; i>= 0 ; i-- ){
for( j=0; j<i ; j++{
temp=Difference ( array[0] , array [ j+ 1 ] )
array[j]=temp;
ii=search the map to see whether this temp element is already present inside the map or not , if present return the map index.
if it's present then just increment it's no of occur enc , ie second field in my code.
else
insert this temp element inside the map and keep second element 1.
}
}
after completing this search the map-second elements which are divisible by 2 , and prints those data ..
Example:
array : 1 2 3 6
pass1: 1 2 5
pass 2: 1 4
pass 3: 3
map contains
1->;2
2->;1
3->;1
4->;1
5->;1
Void DiffPiar( int array , int array_size){
map<int , int> store //cretae a map to store resulte
int temp;
for ( i=array_size -1 ; i>= 0 ; i-- ){
for( j=0; j<i ; j++{
temp=Difference ( array[0] , array [ j+ 1 ] )
array[j]=temp;
ii=search the map to see whether this temp element is already present inside the map or not , if present return the map index.
if it's present then just increment it's no of occur enc , ie second field in my code.
else
insert this temp element inside the map and keep second element 1.
}
}
after completing this search the map-second elements which are divisible by 2 , and prints those data ..
Example:
array : 1 2 3 6
pass1: 1 2 5
pass 2: 1 4
pass 3: 3
map contains
1->;2
2->;1
3->;1
4->;1
5->;1
list1=1->2->.......
head=NULL;
temp=NULL;
while( list1 !=NULL ){
temp=getnode(list1->data);
temp->next=head;
head=temp;
list1=list1->next;
}
o(nlogn) solution
/*
Developed By :Suman Roy
Email : email.suman.roy@gmail.com
*/
#include<iostream>
using namespace std;
int i_length;
void Print(int *a , int *b){
for( int i=0 ;i<i_length ;i ++)
std::cout<<a[i];
std::cout<<std::endl;
for ( int i=0 ; i<i_length ; i++ )
std::cout<<b[i];
}
int Break( int *array , int i_start , int i_end ,int i_pivot){
int i=i_start - 1;
int temp;
while ( i_start != i_end ){
if ( array [ i_start ] == i_pivot ){
temp=array[ i_start ];
array [ i_start]=array [ i_end ];
array[ i_end ]=temp;
}
if ( array [ i_start ] < i_pivot ) {
temp=array [ i_start ];
array [ i_start ]=array [ ++i ];
array [ i ]=temp;
}
i_start ++;
}
temp=array [ ++ i ];
array[i] = array [ i_end ];
array [i_end]=temp;
return i;
}
int count=0;
void Quicksort( int *array , int i_start , int i_end , int *b){
while ( i_start < i_end ){
int k=Break( array , i_start , i_end ,b[i_start]);
Break( b , i_start , i_end , array[k] );
count ++;
Quicksort( array , i_start , k-1 , b );
Quicksort( array , k+1 , i_end, b);
return ;
}
return ;
}
int main(){
int b[]={0,9,1,6,7,4};
int a[]={4,7,1,6,0,9};
i_length=6;
Quicksort( a, 0 , i_length-1 , b);
Pr int( a , b );
}
Output
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
014679
014679
A dynamic algo solution :
/*
Find the longest substring that is the same in reverse.
As an example, if the input was "I like racecars that go fast"
the answer would be "racecar".
Test your code in the following String:
"FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"
Developed By : Suman Roy
Email : email.suman.roy@gmail.com
*/
#include<iostream>
#include<stdlib.h>
#include<fstream>
#include<string>
using namespace std;
typedef struct node{
char c_value;
int i_count;
}node;
void Print( node ** array , int i_size ){
for( int i=0; i<i_size ; i++){
for (int j=0 ; j<i_size ; j++ ){
std::cout<<array[i][j].c_value<<":"<<array[i][j].i_count<<" ";
}
std::cout<<std::endl;
}
}
void Find( node **array , int i_length ){
int i_max=0;
int x,y;
for( int i=1; i< i_length ; i++){
for( int j=1 ; j<i_length ; j++){
if ( array[0][j].c_value == array[i][0].c_value ){
array[i][j].i_count=array[i-1][j-1].i_count + 1;
if( array[i][j].i_count >i_max ){
i_max=array[i][j].i_count;
x=i;y=j;
}
}
}
}
std::cout<<i_max<<std::endl;
std::cout<<x<<y<<std::endl;
std::cout<<"Maximum substring is \n";
while( ( x>=0 ) & ( y>= 0 ) & ( array[x][y].i_count > 0 ) ){
std::cout<<array[0][y--].c_value;
x--;
}
std::cout<<std::endl;
// Print( array , i_length);
}
int main(){
string s_value="I like racecars that go fast";
//std::cin>>s_value;
int i_length=s_value.length();
i_length ++;
int j=1;
node **array=new node* [ i_length ];
for( int i=0 ; i <i_length ; i++ ){
array[ i ]=new node [ i_length ];
}
for( std::string::iterator ii =s_value.begin () ; ii!=s_value.end() ;ii++ ){
array[0][j].i_count=0;
array[0][j++].c_value=*ii;
}
j=1;
for( std::string::reverse_iterator ii=s_value.rbegin() ; ii!=s_value.rend() ; ii ++ ){
array[j][0].i_count=0;
array[j++][0].c_value=*ii;
}
array[0][0].i_count=0;
//Print( array , i_length );
Find(array , i_length );
// Print( array , i_length );
}
Output:
1. ( for 1st string )
suman@suman-laptop:/media/D/coding/algo/Dynamic$ ./a.out
Maximum substring is
racecar
2.(for long string)
suman@suman-laptop:/media/D/coding/algo/Dynamic$ ./a.out
Maximum substring is
ranynar
//If the element is not present in the array I printed that array is not present rather printing -1 -1 , it's an easy thing to change
/*Given a sorted integer array and a number, find the start and end indexes of the number in the array.
Ex1: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 3 --> Output = {3,6}
Ex2: Array = {0,0,2,3,3,3,3,4,7,7,9} and Number = 5 --> Output = {-1,-1}
Complexity should be less than O(n)
Developed by : Suman Roy
Email: email.suman.roy@gmail.com
*/
#include<iostream>
#include<stdlib.h>
using namespace std;
int MAX,MIN;
bool flag1=false;
bool flag2=false;
void Search(int *array , int i_start , int i_end , int i_search){
if ( flag1 & flag2 )
exit( EXIT_SUCCESS);
// std::cout<<"start ="<<i_start<<"end ="<<i_end<<std::endl;
int i_mid= ( i_start+i_end ) /2;
// std::cout<<"Mid= "<<i_mid<<":"<<array[i_mid]<<std::endl;
if ( array[i_mid ] == i_search) {
if ( ( array [ i_mid - 1 ] !=i_search || i_mid==0 ) & !flag1 ){
std::cout<<"left_index= "<< i_mid<<std::endl;
flag1=true;
Search( array , i_mid + 1 , MAX , i_search );
std::cout<<"Rightindex = "<<i_mid<<std::endl;
flag2=true;
exit(EXIT_SUCCESS);
return ;
} if( !flag1 ){ Search ( array , MIN ,i_mid -1 , i_search ); }
if ( (array [ i_mid +1 ] !=i_search || i_mid == MAX ) & !flag2){
std::cout<<"right_index= "<<i_mid<<std::endl;
flag2=true;
Search ( array , MIN , i_mid-1 , i_search ) ;
std::cout<<"Left index="<<i_mid<<std::endl;
flag1=true;
exit(EXIT_SUCCESS);
return ;
}
if( !flag2 ){ Search ( array , i_mid + 1 , MAX , i_search );}
}
if( ( * ( array + i_mid ) >i_search )){
if( i_mid-1 >= i_start ){
MAX=i_mid-1;
Search ( array , i_start , i_mid-1 , i_search ) ;
}
}
else{
if( * ( array + i_mid ) < i_search ){
if( i_mid + 1 <=i_end ){
MIN=i_mid+1;
Search( array , i_mid + 1 ,i_end , i_search );
}
}
}
}
int main(){
int i_search;
MIN=0;
MAX=11;//no of elements in array
int array[]={0,0,2,3,3,3,3,3,4,7,7,9};
std::cout<<"enter the element\n";
std::cin>>i_search;
Search ( array , MIN ,MAX , i_search );
std::cout<<"Element not present\n";
}
Out Put:
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
enter the element
1
Element not present
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
enter the element
0
left_index= 0
right_index= 1
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
enter the element
2
left_index= 2
Rightindex = 2
suman@suman-laptop:/media/D/coding/algo/search$ ./a.out
enter the element
3
left_index= 3
right_index= 7
suman@suman-laptop:/media/D/coding/algo/search$
Void DiffPiar( int array , int array_size){
map<int , int> store //cretae a map to store resulte
int temp;
for ( i=array_size -1 ; i>= 0 ; i-- ){
for( j=0; j<i ; j++{
temp=Difference ( array[0] , array [ j+ 1 ] )
array[j]=temp;
ii=search the map to see whether this temp element is already present inside the map or not , if present return the map index.
if it's present then just increment it's no of occur enc , ie second field in my code.
else
insert this temp element inside the map and keep second element 1.
}
}
after completing this search the map-second elements which are divisible by 2 , and prints those data ..
Example:
array : 1 2 3 6
pass1: 1 2 5
pass 2: 1 4
pass 3: 3
map contains
1->2
2->1
3->1
4->1
5->1
logic is quite simple scan the tree breath wise and use some logic to calculate sum of same level . i used one structure that will hold the start and end position of nodes of a same level in the queue.
- email.suman.roy July 12, 2013My solution is little big, i implemented my code by c++ , i created BST , that is also a binary tree , my file BST.hpp contains all functions required to implement this program, and from main.cpp I called all the header function , and input file contains data for creating BST .
1st line of input indicates no of nodes for bst and rest are values for BST.
1.BST.hpp
/*
BST.hpp
Developed By: Suman Roy
Email : email.suman.roy@gmail.com
*/
#ifndef BST_H
#define BST_H
#include<iostream>
#include<stdlib.h>
#include<math.h>
using namespace std;
typedef struct node{
int i_value;
struct node * l_child;
struct node * r_child;
}node;
typedef struct level{
int i_start;
int i_end;
int i_sum;
}level;
class Queue_t{
private:
node **i_queue;
int rear;
int front;
public:
node* Get_Value();
int Insert_Value( node* );
Queue_t ( int );
Queue_t( void );
};
Queue_t::Queue_t ( void ){};
Queue_t::Queue_t( int i_size){
i_queue=new (std::nothrow) node* [ i_size ];
front=rear=-1;
}
int Queue_t::Insert_Value( node *temp){
std::cout<<"inserted ="<<temp->i_value<<std::endl;
i_queue[++front]=temp;
// std::cout<< i_queue[front]->i_value;
return front;
}
node* Queue_t::Get_Value(){
if ( front == rear ){
front=rear=-1;
return NULL;
}
else return ( i_queue[ ++rear ] );
}
class Bst : public Queue_t{
private:
node *root;
level *level_store;
public:
Bst();
bool Find ( int& );
node * Getnode( int& );
bool Insert ( int& );
void Print(node * );
void Print_Level(int& , int& );
};
Bst::Bst(){
root=NULL;
Queue_t();
}
void Bst::Print_Level ( int &level_limit, int &bst_size){
level_store=new ( std::nothrow ) level[ bst_size ] ;
Queue_t l_queue( bst_size );
node *temp=root;
int i_temp;
int level=l_queue.Insert_Value( temp );
level_store[ level ].i_start=0;
level_store[ level ].i_end=0;
int check=true;
while ( check ){
level_store[level].i_sum=0;
int flag=0;
check=false;
std::cout<<"queue start & end"<<level_store[level].i_start<<":"<<level_store[level].i_end<<std::endl;
int ii=level;
for ( int i=level_store[ii].i_start ; i<=level_store[ii].i_end ; i++ ){
temp=l_queue.Get_Value();
level_store[ii].i_sum+=temp->i_value;
if ( temp->l_child != NULL ) {
check=true;
i_temp=l_queue.Insert_Value( temp->l_child );
if ( flag == 0) {
level_store [ ++ level ].i_start=i_temp;
flag =1;
}
}
if ( temp->r_child != NULL ){
check=true;
i_temp=l_queue.Insert_Value ( temp->r_child );
if (flag==0 ){
level_store[ ++ level ].i_start=i_temp;
flag=1;
}
}
// std::cout<<"sum at level "<<ii<<"="<<level_store[ii].i_sum<<std::endl;
}
std::cout<<"sum at level "<<ii<<"="<<level_store[ii].i_sum<<std::endl;
std::cout<<"..................."<<std::endl;
level_store [ level ].i_end=i_temp;
}
//print sum
std::cout<<"PRINTING FINAL RESULT\n";
int i_pow=0;
int i_print_level=0;
do {
std::cout<<"Sum for level = "<<i_print_level<<" : "<<level_store[ i_print_level ].i_sum<<std::endl;
i_print_level=pow( level_limit , i_pow ++);
}while ( i_print_level <=level );
// std::cout<<"Sum for level "<<level_limit<<" ="<<level_store[level_limit].i_sum<<std::endl;
}
void Bst::Print( node * temp){
std::cout<<temp->i_value<<temp->l_child<<temp->r_child<<std::endl;
}
bool Bst::Find( int &i_val ){
node *temp=root;
while( temp!=NULL ){
if( temp->i_value == i_val )
return true;
else {
if ( temp->i_value > i_val ) temp=temp->l_child;
else temp=temp->r_child;
}
}
return false;
}
node * Bst::Getnode(int &i_val){
node *temp=new node;
if ( temp == NULL ) {
std::cout<<"Out of memory \n ";
return NULL;
}
temp->i_value=i_val;
temp->l_child==NULL;
temp->r_child=NULL;
Print(temp);
return temp;
}
bool Bst::Insert( int &i_val ){
if( root == NULL ){
root=Getnode(i_val);
return true;
}
node * temp=root;
node * temp2;
while ( temp != NULL ){
if ( temp->i_value == i_val ){
std::cout<<"Data alradey exist \n";
return false;
}
else {
temp2=temp;
if( temp->i_value > i_val )
temp=temp->l_child;
else temp=temp->r_child;
}
}
if( temp2->i_value > i_val )
temp2->l_child=Getnode ( i_val );
else
temp2->r_child=Getnode( i_val );
return true;
}
#endif
2. main.cpp
/*
main.cpp
You are given a binary tree and a number k.
Print the sum of levels k^0, k^1, k^2, k^3..... untill all levels are exhausted.
Each K^ith level sum should be printed separately.
I saved sum for all level and printing the sum by given level no
developed by : Suman
Date:13 7 2013
time : 4.23 am
*/
#include<iostream>
#include<stdlib.h>
#include<fstream>
#include"BST.hpp"
using namespace std;
int main(int argc , char **argv){
if( argc <1 ) {
std::cout<<"Provide Arguments\n";
exit(EXIT_FAILURE);
}
fstream file;
file.open( argv [1] , ios::in);
if( !file.is_open() ){
std:cout<<"Can't open file\n";
exit(EXIT_FAILURE);
}
int i_num , i_val;
file>>i_num;
Bst bst;
for ( int i=0 ;i<i_num ; i++ ){
file>>i_val;
bst.Insert( i_val);
}
int i_level;
std::cout<<"print the value of k\n";
std::cin>>i_level;
//int i_level=2;
bst.Print_Level( i_level , i_num); //i_level=k
}
3.input
7
5
3
4
1
10
12
30
4. output
suman@suman-laptop:/media/D/coding/algo/Graph/BST/level_sum$ ./a.out input
500
300
400
100
1000
1200
3000
print the value of k
3
inserted =5
queue start & end0:0
inserted =3
inserted =10
sum at level 0=5
...................
queue start & end1:2
inserted =1
inserted =4
inserted =12
sum at level 1=13
...................
queue start & end3:5
inserted =30
sum at level 2=17
...................
queue start & end6:6
sum at level 3=30
...................
PRINTING FINAL RESULT
Sum for level = 0 : 5
Sum for level = 1 : 13
Sum for level = 3 : 30
suman@suman-laptop:/media/D/coding/algo/Gr
c++ solution of this problem
/*
Given a sorted array. Find the number of couples with the same difference. For example we can have an array with 2 couples whose difference is 3 and 4 couples whose difference is 5. The Output should be 2 & 4.
developed by : Suman Roy
Email : email.suman.roy@gmail.com
*/
#include<iostream>
#include<stdlib.h>
#include<fstream>
#include<map>
using namespace std;
int Diff( int &num1 , int &num2 ){
if ( num1 > num2 ) return num1-num2;
else return num2-num1;
}
typedef std::map< int , int > storage;
void Print ( storage store ){
std::cout<<"pair output-->\n";
for( storage::iterator ii=store.begin() ; ii!=store.end() ; ii++ ){
int temp=ii->second;
if ( temp % 2 == 0 )
std::cout<<ii->first<<" == "<<ii->second <<std::endl;
}
}
void DiffPair(int *i_array , int &i_num ){
storage store;
storage::iterator ii;
int temp;
for ( int i=i_num-1 ; i>=0 ; i-- ){
for( int j=0 ;j<i ; j++ ){
temp=Diff ( * i_array , * ( i_array + j + 1 ) );
* ( i_array + j ) = temp;
ii=store.find ( temp );
if ( ii== store.end() )
store[ temp ] =1;
else
ii->second++;
}
}
Print ( store ) ;
}
int main(){
int i_size;
std::cin>>i_size;
int *i_array=new int [ i_size ];
int i_value;
for ( int i=0 ; i<i_size ; i++ )
std::cin>> * ( i_array + i );
std::cout<<"Print sorted array\n";
for( int i=0 ; i<i_size ; i++ )
std::cout<<* ( i_array + i )<<" ";
std::cout<<std::endl;
DiffPair( i_array , i_size );
}
1. Find the lowest common ancestor of two nodes value
2. then from lowest common ancestor node find the path of source and destination ( simple traversal ) and store the all traversed node in some DS by sorted order .
I can provide you c++ code.
take a map and linked list , map will store node_value and corresponding linked_list start address.
Linked list will keep information about those nodes with whom that node is connected.
what about adding a new node by function : addNode(Object nodeData)
- email.suman.roy July 12, 2013void Bst::Path(int &i_source , int &i_destination ){ // give two node value for searching path
node *temp=FindBreak( root , i_source , i_destination );
if( temp->i_value == i_source && temp->i_value == i_destination ){
std::cout<<temp->i_value<<std::endl;
}
Push( temp , i_source );
Push(temp , i_destination);
PrintMap();
}
node *Bst::FindBreak( node *temp, int &i_source , int &i_destination ){ // find the breaking node after which source & destination nodes became ( left , righ ) of break point node
//node *temp=root;
while ( temp!=NULL ){
int i_change=0;
while ( temp->i_value >i_source & temp->i_value>i_destination ){
std::cout<<"left\n";
temp=temp->l_child;
i_change=1;
}
while( temp->i_value <i_source & temp->i_value<i_destination ){
std::cout<<"Right\n";
temp=temp->r_child;
i_change=1;
}
//std::cout<<temp->i_value<<std::endl;
if ( i_change == 0 ) return temp;
FindBreak ( temp , i_source , i_destination);
}
}
void Bst::PrintMap(){
std::cout<<"The path is -------- \n";
for ( Track::iterator ii=m_track.begin() ; ii!=m_track.end() ; ii ++ )
std::cout<<ii->first<<"-->";
std::cout<<"END"<<std::endl;
}
void Bst::Push ( node *temp , int &i_search ){
while( temp!=NULL ){
m_track[ temp->i_value ]=temp->i_value;
if( temp->i_value == i_search )
return ;
else {
m_track[ temp->i_value ]=temp->i_value;
if ( temp->i_value > i_search ) temp=temp->l_child;
else temp=temp->r_child;
}
}
return ;
}
If it's a bst then there must be one unique path between any two of nodes. the complexity of searching in BST is log(n) .
- email.suman.roy July 11, 2013#include<iostream>
#include<string.h>
using namespace std;
void GenarateString ( string s_pattern , int index ){
int i_size=s_pattern.size();
if( index == i_size ){
std::cout<<s_pattern<<std::endl;
return;
}
if( s_pattern[index]== '?' ){
s_pattern[index]='0';
GenarateString ( s_pattern , index + 1 );
s_pattern[index]='1';
GenarateString ( s_pattern , index + 1 );
}
else
GenarateString ( s_pattern , index + 1 );
}
int main(){
int i_num;
std::cin>>i_num;
string s_pattern;
for( int i=0 ; i<i_num ; i++ ){
std::cin>>s_pattern;
std::cout<<"The pattern is= "<<s_pattern<<std::endl;
GenarateString(s_pattern , 0 );
}
}
for my solution every times array size is reduced to half
c++ code :
/*
Given - a number (n) and a sorted array
Find a number in the array having least difference with the given number (n)
*/
for( int i=0 ; i<n_array_size ; i++)
std::cin>>*( array_elementss + i );
for(int j=0 ; j<n_array_size ; j++ )#include<iostream>
using namespace std;
int Difference ( int temp1 , int temp2 ){
if( temp1 > temp2 ) return (temp1 - temp2 );
else return ( temp2 - temp1);
}
int Search( int *array_elements , int i_start_index , int i_end_index , int &i_middle, int &i_search){
int i_returnvalue;
i_middle= ( i_start_index + i_end_index ) / 2;
std::cout<<" middle = "<<i_middle<<std::endl;
int i_temp1=Difference ( * ( array_elements + i_middle ) , i_search );
//int i_temp2=Difference ( * ( aray_element + ( i_middle - 1) , i_search) );
if(i_temp1 ==0 )
return 0;
else {
if ( i_middle > i_start_index && i_middle < i_end_index ) {
int i_temp2=Difference ( * ( array_elements + ( i_middle - 1) ) , i_search) ;
int i_temp3= Difference ( * ( array_elements + ( i_middle + 1) ) , i_search ); std::cout<<"i_temp1 = "<<i_temp1<<"\n i_temp2= "<<i_temp2<<"\n i_temp3= "<<i_temp3<<std::endl;
if( i_temp2 < i_temp3){
if ( i_temp1 < i_temp2 )
return i_temp1;
else
Search ( array_elements , i_start_index , i_middle - 1 , i_middle , i_search );
}
else {
if ( i_temp1 < i_temp3 )
return i_temp1;
else{
std::cout<<"call\n";
Search ( array_elements , i_middle + 1 , i_end_index , i_middle , i_search ) ;
}
}
}
else{
std::cout<<i_start_index<<" " <<i_middle<<" "<<i_end_index<<std::endl;
if( i_middle == i_start_index & i_middle == i_end_index ) return ( Difference ( * (array_elements + i_middle ) , i_search ) );
else{
std::cout<<"call inside i_middle > start \n";
if ( i_middle > i_start_index ){
int i_temp2=Difference ( * ( array_elements + ( i_middle - 1 ) ) , i_search) ;
if ( i_temp1 < i_temp2 )
return i_temp1;
else
Search ( array_elements , i_start_index , i_middle - 1 , i_middle , i_search );
}
else
{
std::cout<<" call inside middle < end\n";
int i_temp3= Difference ( * ( array_elements + ( i_middle + 1) ) , i_search );
if ( i_temp1 < i_temp3 )
return i_temp1;
else
Search ( array_elements , i_middle + 1 , i_end_index , i_middle , i_search ) ;
}
}
}
// std::cout<<i_middle;
// return 1;
}
}
int main(){
int n_array_size , middle , i_search, i_temp1, i_temp2;
std::cin>>n_array_size;
std::cin>>i_search;
int *array_elementss=new int[ n_array_size ];
std::cout<< *( array_elementss + j )<<std::endl;
int i_result=Search( array_elementss , 0 , n_array_size - 1 , middle ,i_search);
std::cout<<"Result is :="<<i_result<<std::endl;
}
#include<stdio.h>
int main()
{
int i,buy=-1,profit=0;
int array[]={3,7,4,10,11,8,5,4,8,6};
for(i=0;i<9;i++)
{
if(buy==-1 && (array[i+1]-array[i])>0 )
{buy=array[i];
profit-=buy;
printf("bought day %d ",i+1);
}
else
if(buy!=-1 && (array[i+1]-array[i])<0)
{
profit+=array[i];
buy=-1;
printf("sell stoch day %d",i+1);
}
}
}
what is the ultimate solution??
- email.suman.roy August 04, 2012monkey:2 1 2 3 2 4 3 2 1 2 1 2 1 2 1 2 1
gun @ :2 3 3 4 4 5 5 6 6 5 5 4 4 3 3 2 2
I think nt working..
wow..gr8.. hats off..
- email.suman.roy August 03, 2012tree itself is not a linkedlist??
- email.suman.roy July 15, 2012
I solved this , posted without logging in.
- email.suman.roy July 17, 2013