A Knowledge Base: 2017

Jun 26, 2017

create a balance BST from a sorted list

#include <iostream>
#include <string.h>
using namespace std;

int max(int p, int q)
{
 return ((p>q) ? p : q);
}


class node;
class node
{
 public:
  char c;
  node* l;
  node* r;
};

void printinorder(node* root)
{
 if(!root)
 {
  return;
 }
 
 printinorder(root->l);
 cout << root->c << " ";
 printinorder(root->r);
}

int depth(node* root)
{
 if(!root)
  return 0;
 return 1 + max(depth(root->l), depth(root->r));
}

void printbylevel(node* root, int depth, int level)
{
 if(!root)
  return;
  
 if(depth == level)
 {
  cout << root->c;
 }
 else
 {
  printbylevel(root->l, depth, level+1);
  cout<<"  ";
  printbylevel(root->r, depth, level+1);
 }
}

void printlevelorder(node *root)
{
 int d = depth(root);
 for(int i=0; i<d; i++)
 {
  for(int j=0;j<d-i;j++)
   cout << " ";
  printbylevel(root, i, 0);
  cout << endl;
 }
}

node* createBalancedBST(char s[], int l, int r)
{
 if(l==r)
 {
  node* t = new node();
  t->c = s[l];
  t->l = NULL;
  t->r = NULL;
  return t;
 }
 else if(l>r)
  return NULL;
 
 int median = (l+r)>>1;
 node* t = new node();
 t->c = s[median];
 t->l = createBalancedBST(s, l, median-1);
 t->r = createBalancedBST(s, median+1, r);
 return t;
}

int main() {
 // your code goes here
 char s[100];
 cin >> s;
 node* root = createBalancedBST(s, 0, strlen(s)-1);
 cout << "tree input is:" << s << endl;
 cout << "inorder: ";
 printinorder(root);
 cout << "\ntree depth=" << depth(root) << endl;
 cout << "level order: \n";
 printlevelorder(root);
 
 return 0;
}

tree input is:abcdefghijklmnopqrstuvwxyz
inorder: a b c d e f g h i j k l m n o p q r s t u v w x y z 
tree depth=5
level order: 
     m
    f  t
   c  i  p  w
  a  d  g  k  n  r  u  y
   b    e    h  j  l    o  q  s    v  x  z

Print Diameter (max path) of a tree

#include <iostream>
#include <string.h>
using namespace std;

int max(int p, int q)
{
 return ((p>q) ? p : q);
}

int max3(int p, int q, int r)
{
 return ((p>q) ? (p>r? p:r) : (q>r ? q:r));
}
class node;
class node
{
 public:
  char c;
  node* l;
  node* r;
};

void insert(node** root, char c)
{
 if(!(*root))
 {
  node* t = new node();
  t->c = c;
  t->l=NULL;
  t->r=NULL;
  *root = t;
  //cout << "root=" << (*root)->c << endl;
 }
 else
 {
  if((*root)->c > c)
  {
   if(!(*root)->l)
   {
    node* t = new node();
    t->c = c;
    t->l=NULL;
    t->r=NULL;
    (*root)->l = t;
    //cout << "left=" << (*root)->l->c << endl;
   }
   else
    insert(&((*root)->l), c);
  }
  else
  {
   if(!(*root)->r)
   {
    node* t = new node();
    t->c = c;
    t->l=NULL;
    t->r=NULL;
    (*root)->r = t;
    //cout << "right=" << (*root)->r->c << endl;
   }
   else
    insert(&((*root)->r), c);
  }
 }
}

void printinorder(node* root)
{
 if(!root)
 {
  return;
 }
 
 printinorder(root->l);
 cout << root->c << " ";
 printinorder(root->r);
}

int depth(node* root)
{
 if(!root)
  return 0;
 return 1 + max(depth(root->l), depth(root->r));
}

void printaltbylevel(node* root, int depth, int level)
{
 if(!root)
  return;
  
 if(depth == level)
 {
  cout << root->c;
 }
 else
 {
  if(depth%2 == 0)
  {
   printaltbylevel(root->l, depth, level+1);
   printaltbylevel(root->r, depth, level+1);
  }
  else
  {
   printaltbylevel(root->r, depth, level+1);
   printaltbylevel(root->l, depth, level+1);
  }
 }
}

void printbylevel(node* root, int depth, int level)
{
 if(!root)
  return;
  
 if(depth == level)
 {
  cout << root->c;
 }
 else
 {
  printbylevel(root->l, depth, level+1);
  cout<<"  ";
  printbylevel(root->r, depth, level+1);
 }
}

void printlevelorder(node *root)
{
 int d = depth(root);
 for(int i=0; i<d; i++)
 {
  for(int j=0;j<d-i;j++)
   cout << " ";
  printbylevel(root, i, 0);
  cout << endl;
 }
}

void printaltlevelorder(node *root)
{
 int d = depth(root);
 for(int i=0; i<d; i++)
 {
  printaltbylevel(root, i, 0);
 }
}

int diameter(node* root)
{
 if(!root)
  return 0;
  
 int lheight = depth(root->l);
 int rheight = depth(root->r);
 
 return (1 + max3(lheight + rheight, diameter(root->l), diameter(root->r)));
}

class dia
{
 public:
  char height[30];
  char diam[60];
};

dia* cdepth(node* root)
{
 if(!root)
 {
  dia *t = new dia();
  strcpy(t->height, "");
  strcpy(t->diam, "");
  return t;
 }
 
 dia* l = cdepth(root->l);
 dia* r = cdepth(root->r);
 if(strlen(l->height) >= strlen(r->height))
 {
  strcat(l->height, &(root->c));
  return l;
 }
 else
 {
  strcat(r->height, &(root->c));
  return r;
 }
}

dia* maxPath(node* root)
{
 if(!root)
 { 
  dia *t = new dia();
  strcpy(t->height,"");
  strcpy(t->diam,"");
  return t;
 }
 
 dia* lht = cdepth(root->l);
 dia* rht = cdepth(root->r);
 
 dia* lmaxpath = maxPath(root->l);
 dia* rmaxpath = maxPath(root->r);
 
 if((strlen(lht->height) + strlen(rht->height)) >= strlen(lmaxpath->diam))
 {
  if((strlen(lht->height) + strlen(rht->height)) >= strlen(rmaxpath->diam))
  {
   strcat(lht->diam, lht->height);
   strcat(lht->diam, &(root->c));
   strcat(lht->diam, rht->height);
   return lht;
  }
  else
  {
   strcat(rmaxpath->diam, &(root->c));
   return rmaxpath;
  }
 }
 else
 {
  if(strlen(lmaxpath->diam) >= strlen(rmaxpath->diam))
  {
   strcat(lmaxpath->diam, &(root->c));
   return lmaxpath;
  }
  else
  {
   strcat(rmaxpath->diam, &(root->c));
   return rmaxpath;
  }
 }
 
}


int main() {
 // your code goes here
 char s[100];
 cin >> s;
 node* root=NULL;
 for(int i=0; i<strlen(s);i++)
  insert(&root, s[i]);
 cout << "tree input is:" << s << endl;
 cout << "inorder: ";
 printinorder(root);
 cout << "\ntree depth=" << depth(root) << endl;
 dia* t = cdepth(root);
 cout << "tree height path= " << t->height << endl;
 cout << "level order: \n";
 printlevelorder(root);
 cout << "alt level order: \n";
 printaltlevelorder(root);
 cout << "\ndiameter of tree: " << diameter(root) <<endl;
 t = maxPath(root);
 cout << "max Path = " << t->diam << endl;
 return 0;
}

tree input is:fjghdklsamcbe
inorder: a b c d e f g h j k l m s 
tree depth=6
tree height path= mslkjf
level order: 
      f
     d  j
    a  e  g  k
     c        h    l
    b                  s
                       m  
alt level order: 
fjdaegklhcbsm
diameter of tree: 10
max Path = bcadfmslkj

Jun 25, 2017

Tree traversal and diameter

#include <iostream>
#include <string.h>
using namespace std;

int max(int p, int q)
{
 return ((p>q) ? p : q);
}

int max3(int p, int q, int r)
{
 return ((p>q) ? (p>r? p:r) : (q>r ? q:r));
}
class node;
class node
{
 public:
  char c;
  node* l;
  node* r;
};

void insert(node** root, char c)
{
 if(!(*root))
 {
  node* t = new node();
  t->c = c;
  t->l=NULL;
  t->r=NULL;
  *root = t;
  //cout << "root=" << (*root)->c << endl;
 }
 else
 {
  if((*root)->c > c)
  {
   if(!(*root)->l)
   {
    node* t = new node();
    t->c = c;
    t->l=NULL;
    t->r=NULL;
    (*root)->l = t;
    //cout << "left=" << (*root)->l->c << endl;
   }
   else
    insert(&((*root)->l), c);
  }
  else
  {
   if(!(*root)->r)
   {
    node* t = new node();
    t->c = c;
    t->l=NULL;
    t->r=NULL;
    (*root)->r = t;
    //cout << "right=" << (*root)->r->c << endl;
   }
   else
    insert(&((*root)->r), c);
  }
 }
}

void printinorder(node* root)
{
 if(!root)
 {
  return;
 }
 
 printinorder(root->l);
 cout << root->c << " ";
 printinorder(root->r);
}

int depth(node* root)
{
 if(!root)
  return 0;
 return 1 + max(depth(root->l), depth(root->r));
}

void printaltbylevel(node* root, int depth, int level)
{
 if(!root)
  return;
  
 if(depth == level)
 {
  cout << root->c;
 }
 else
 {
  if(depth%2 == 0)
  {
   printaltbylevel(root->l, depth, level+1);
   printaltbylevel(root->r, depth, level+1);
  }
  else
  {
   printaltbylevel(root->r, depth, level+1);
   printaltbylevel(root->l, depth, level+1);
  }
 }
}

void printbylevel(node* root, int depth, int level)
{
 if(!root)
  return;
  
 if(depth == level)
 {
  cout << root->c;
 }
 else
 {
  printbylevel(root->l, depth, level+1);
  cout<<"  ";
  printbylevel(root->r, depth, level+1);
 }
}

void printlevelorder(node *root)
{
 int d = depth(root);
 for(int i=0; i<d; i++)
 {
  for(int j=0;j<d-i;j++)
   cout << " ";
  printbylevel(root, i, 0);
  cout << endl;
 }
}

void printaltlevelorder(node *root)
{
 int d = depth(root);
 for(int i=0; i<d; i++)
 {
  printaltbylevel(root, i, 0);
 }
}

int diameter(node* root)
{
 if(!root)
  return 0;
  
 int lheight = depth(root->l);
 int rheight = depth(root->r);
 
 return (1 + max3(lheight + rheight, diameter(root->l), diameter(root->r)));
}
int main() {
 // your code goes here
 char s[100];
 cin >> s;
 node* root=NULL;
 for(int i=0; i<strlen(s);i++)
  insert(&root, s[i]);
 cout << "tree input is:" << s << endl;
 cout << "inorder: ";
 printinorder(root);
 cout << "\ntree depth=" << depth(root) << endl;
 cout << "level order: \n";
 printlevelorder(root);
 cout << "alt level order: \n";
 printaltlevelorder(root);
 cout << "\ndiameter of tree: " << diameter(root) <<endl;
 return 0;
}

tree input is:jfmcnabkd
inorder: a b c d f j k m n 
tree depth=5
level order: 
     j
    f  m
   c    k  n
  a  d          
   b              
alt level order: 
jmfckndab
diameter of tree: 7

palindrome substring of a given string

#include <iostream>
#include <string.h>
using namespace std;

bool ispalindrome(char* s, int l, int r)
{
 int n = r-l+1;
 for(int i=0; i<n/2; i++)
 {
  if(s[l+i] != s[r-i])
   return false;
 }
 
 for(int i=l; i<=r; i++)
  cout << s[i];
 cout << endl;
 return true;
}
void palindromesubstrings(char* s)
{
 int n = strlen(s);
 for(int i=0; i<n; i++)
 {
  for(int j=i+1; j<n; j++)
  {
   if(s[i] == s[j])
   {
    //cout << "[" << i << "," << j << "]=" << s[i] << endl;
    ispalindrome(s,i,j);
   }
  }
 }
}

int main() {
 // your code goes here
 char s1[100], s2[100];
 cin >> s1;
 cin >> s2;
 //cout << "palindrome " << s1 << " " << (ispalindrome(s1,0,strlen(s1)-1)? "true" : "false");
 cout << "palindrome substrings of " << s2 << ":\n";
 palindromesubstrings(s2);
 return 0;
}

palindrome substrings of ABCBAHELLOHOWRACECARAREYOUIAMAIDOINGGOOD:
ABCBA
BCB
LL
OHO
RACECAR
ACECA
CEC
ARA
RAR
IAMAI
AMA
GG
OO

length of longest common subsequence of 2 strings

#include <iostream>
#include <string.h>
using namespace std;

/*

lcs(s1[1,m], s2[1,n]) = 1 + lcs(s1[1,m-1], s2[1,n-1]) 
       if s1[m] == s2[n]
 
 = max(lcs(s1[1,m-1], s2[1,n]) , lcs(s1[1,m], s2[1,n-1]) ) otherwise
*/
int max(int x, int y)
{
 return x>y?x:y; 
}
int lcs(char* s1, int m, char *s2, int n)
{
 if(m==0 || n==0)
  return 0;
  
 if(s1[m-1] == s2[n-1])
  return (1 + lcs(s1, m-1, s2, n-1));
  
 return max(lcs(s1, m-1, s2, n), lcs(s1, m, s2, n-1));
}

int lcsdp(char* s1, int m, char* s2, int n)
{
 int lcs[m+1][n+1];
 
 for(int i=0;i<=m; i++)
  for(int j=0; j<=n; j++)
   lcs[i][j] = 0;
 
 for(int i=1;i<=m; i++)
 {
  for(int j=1; j<=n; j++)
  {
   if(s1[i-1] == s2[j-1])
   {
    lcs[i][j] = 1 + lcs[i-1][j-1];
    //cout << s1[i-1] << " ";
   }
   else
   {
    lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j]);
    //cout << i << " " << j << " lcs:" << lcs[i][j] <<endl;
   }
  }
 }
 
 for(int i=0; i<=m; i++)
 {
  for(int j=0; j<=n;j++)
  {
   cout << lcs[i][j] << " ";
  }
  cout << endl;
 }
 return lcs[m][n];
}

int lcsdp2(char* s1, int m, char* s2, int n)
{
 int lcs[m+1][n+1];
 
 for(int i=0;i<=m; i++)
  for(int j=0; j<=n; j++)
   lcs[i][j] = 0;
 
 for(int i=1;i<=m; i++)
 {
  for(int j=1; j<=n; j++)
  {
   if(s1[i-1] == s2[j-1] & i!=j)
   {
    lcs[i][j] = 1 + lcs[i-1][j-1];
    //cout << i << " -" << j << " lcs:" << lcs[i][j] <<endl;
   }
   else
   {
    lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j]);
    //cout << i << " " << j << " lcs:" << lcs[i][j] <<endl;
   }
  }
 }
 
 for(int i=0; i<=m; i++)
 {
  for(int j=0; j<=n;j++)
  {
   cout << lcs[i][j] << " ";
  }
  cout << endl;
 }
 return lcs[m][n];
}

int main() {
 // your code goes here
 char s1[100], s2[100];
 cin >> s1;
 cin >> s2;
 cout << "length of longest increasing subsequence of "<<\
 s1 << " and " << s2 << " is: " << lcsdp(s1,strlen(s1),s2,strlen(s2));
 return 0;
}

input:
abba
acbfabc

output:
length of longest increasing subsequence of abba and acbfabc is: 3

edit distance of two strings

#include <iostream>
#include <string.h>
using namespace std;

int min(int x, int y, int z)
{
 return (x<y)?(x<z?x:z):(y<z?y:z);
}
/*

ed(s1[1,m], s2[1,n]) = ed(s1[1,m-1], s2[1,n-1]) if s1[m] == s2[n];
      = 1+ min( ed(s1[1-m-1], s2[1,n]),  remove  s1[m]
      ed(s1[1-m-1], s2[1,n-1])   replace s1[m] with s2[n]  
      ed(s1[1-m], s2[1,n-1]) )   insert s2[n] 
      if s1[m] != s2[n] 

*/
int editDistance(char* s1, int m, char* s2, int n)
{
 if(m==0)
  return n;
 if(n==0)
  return m;
  
 if(s1[m-1] == s2[n-1])
 {
  return editDistance(s1, m-1, s2, n-1);
 }
 return 1+ min(editDistance(s1,m-1, s2,n), \
 editDistance(s1, m-1, s2, n-1), editDistance(s1, m, s2, n-1));
}
int main() {
 // your code goes here
 char s1[] = "banana";
 char s2[] = "bana";
 char s3[] = "apple";
 char s4[] = "banaba";
 char s5[] = "bonanza";
 char s6[] = "banamf";
 
 cout << "edit of " << s1 << "-" << s2 << "=" \
 << editDistance(s1,strlen(s1), s2, strlen(s2)) << endl;
 cout << "edit of " << s1 << "-" << s3 << "=" \
 << editDistance(s1,strlen(s1), s3, strlen(s3)) << endl;
 cout << "edit of " << s1 << "-" << s4 << "=" \
 << editDistance(s1,strlen(s1), s4, strlen(s4)) << endl;
 cout << "edit of " << s1 << "-" << s5 << "=" \
 << editDistance(s1,strlen(s1), s5, strlen(s5)) << endl;
 cout << "edit of " << s1 << "-" << s6 << "=" \
 << editDistance(s1,strlen(s1), s6, strlen(s6)) << endl;
 return 0;
}

edit of banana-bana=2
edit of banana-apple=5
edit of banana-banaba=1
edit of banana-bonanza=2
edit of banana-banamf=2