Check is a tree is a binary search tree

#include <iostream>
using namespace std;

struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node * newNode(int data)
{
  // Allocate memory for new node
  struct Node * node = (struct Node*)malloc(sizeof(struct Node));

  // Assign data to this node
  node->data = data;

  // Initialize left and right children as NULL
  node->left = NULL;
  node->right = NULL;
  return(node);
}

int isLeftSubtreeLesser(Node * root, int data) {
if (root->data > data) {
return 0;
}
if (isLeftSubtreeLesser(root->left, data) && isLeftSubtreeLesser(root->right, data))
return 1;

return 0;
}

int isRightSubtreeGreater(Node * root, int data) {
if (root->data <= data) {
return 0;
}
if (isRightSubtreeGreater(root->left, data) && isRightSubtreeGreater(root->right, data))
return 1;

return 0;
}

int isBinarySearchTree (Node * root) {
if (root == NULL) {
return 1;
}

if (isLeftSubtreeLesser(root->left, root->data) && isRightSubtreeGreater(root->right, root->data)
&& isBinarySearchTree(root->left) && isBinarySearchTree(root->right)){
return 1;
} else {
return 0;
}
}

int main() {

struct Node *root = newNode(1);

  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);

isBinarySearchTree(root);
return 0;
}

Permutations of a string with repeatitions

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

void permute(char * str, int len, char * data, int index) {

for (int i = 0; i < len; i++) {
data[index] = str[i];
if (index == len - 1) {
cout<<data<<"\n";
} else {
permute(str, len, data, index +1);
}
}
}

void allLexicographicString(char * str) {

int len = strlen(str);
sort(str, str + len - 1);
char * data = new char[len];
permute(str, len, data, 0);
}

int main() {

char str[] = "ABC";
allLexicographicString(str);
return 0;
}

Permutations of a String without repeatition

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute (char * a, int l, int r) {

if (l == r) {
cout<<a<<"\n";
} else {
for (int i = l; i<=r; i++) {
swap ((a + l), (a + i));
permute(a, l+1, r);
swap ((a + l), (a + i));
}
}
}

int main() {
// your code goes here
char str[] = "ABC";

int n = strlen(str);
    permute(str, 0, n-1);

return 0;
}

Matrix Chain Multiplication

//

//  main.cpp

//  MatrixChainMultiplication

//

//  Created by Manu Shah on 06/03/16.

//  Copyright © 2016 Manu. All rights reserved.

//

#include <iostream>

#include <climits>

using namespace std;

int getMinMultiplications (int * P, int n) {

    

    int M[n][n];

    

    for (int i = 1;i<n;i++){

        M[i][i] = 0;

    }

    

    //chain length

    for (int l=2; l <= n;l++) {

        for (int i = 1; i <= n - l +  1; i++) {

            int j = l+i-1;

            

            M[i][j] = INT_MAX;

            for (int k = i; k <= j-1; k++) {

                

                int thiscost = M[i][k] + M[k+1][j] + P[i-1]*P[k]*P[j];

                

                if (thiscost < M[i][j]) {

                    M[i][j] = thiscost;

                }

            }

        }

    }

    

    for (int i = 0;i<n;i++) {

        for (int j = 0;j<n; j++) {

            cout<<M[i][j]<<"\t";

        }

        cout<<"\n";

    }

    

    return M[1][n-1];

}

int main(int argc, const char * argv[]) {

    

    int n;

    cin>>n;

    

    int * P =  new int [n];

    

    for (int i = 0; i < n; i++) {

        cin>>P[i];

    }

    

    int m = getMinMultiplications (P, n);

    

    cout<<m;

    

    return 0;

}

Invert an integer

int getIntegerComplement(int n) {

    vector<int> binary;
    int rem = 0;
   
    while (n) {
        rem = !(n % 2);
        n = n/2;
        binary.push_back(rem);
    }
   
    int decimal = 0;
    int i = 0;
    std::vector<int>::iterator it = binary.begin();
    for (; it!= binary.end(); ++it) {
        decimal += *it * pow(2, i);
        ++i;
    }
   
    return decimal;
}

Strategy Pattern

import java.util.*;
import java.lang.*;
import java.io.*;

interface Strategy
{
public int doOperation(int a , int b);
}

class AddOperation implements Strategy
{
public int doOperation(int a , int b) {
return a + b;
}
}

class SubtractOperation implements Strategy
{
public int doOperation (int a , int b) {
return a - b;
}
}

class Context {
Strategy strategy;

Context (Strategy strategy) {
this.strategy = strategy;
}

int doOperation (int a, int b){
return strategy.doOperation(a, b);
}
}

class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int a = 5;
int b = 4;
Context c = new Context(new AddOperation());

System.out.println(c.doOperation(a, b));

c = new Context (new SubtractOperation());

System.out.println(c.doOperation (a, b));
}
}

Decorator Pattern

import java.util.*;
import java.lang.*;
import java.io.*;

interface Shape
{
void draw ();
}

class Rectangle implements Shape
{
public void draw () {
System.out.println("A rectangle");
}
}

class Circle implements Shape
{
public void draw () {
System.out.println("A circle");
}
}

abstract class ShapeDecorator implements Shape
{
protected Shape decoratedShape;

public ShapeDecorator (Shape s) {
this.decoratedShape = s;
}

public void draw (){
decoratedShape.draw();
}
}

class RedShapeDecorator extends ShapeDecorator
{
public RedShapeDecorator (Shape s) {
super(s);
}

@Override
public void draw() {
decoratedShape.draw();    
      setRedBorder(decoratedShape);
}

private void setRedBorder (Shape s) {
System.out.println("Red Border");
}
}

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
Shape circle = new Circle();
Shape rectangle = new Rectangle();

Shape redCircle = new RedShapeDecorator (new Circle());
Shape redRectangle = new RedShapeDecorator (new Rectangle ());

circle.draw();

redCircle.draw();

redRectangle.draw();
}
}

Code borrowed from
http://www.tutorialspoint.com/

Coin change problem

#include <iostream>
using namespace std;

int count (int * a, int m , int amount) {

int s[amount+1][m];
int x, y;

for (int i = 0; i < m; i++) {
s[0][i] = 1;
}

for (int i = 1 ;i <= amount; i++) {
for (int j = 0; j < m ; j++) {
x = i - a[j] >= 0 ?  s[i-a[j]][j] : 0;
y = j-1 >= 0 ? s[i][j-1] : 0;

s[i][j] = x + y;
}
}

return s[amount][m-1];
}

int main() {
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int amount = 4;
    printf(" %d ", count(arr, m, amount));
    return 0;
}

Minimum cost path between two points in a matrix

#include <iostream>
using namespace std;

int min_num (int a , int b, int c) {

int m = a;

if (m > b) {
m = b;
}

if (m > c) {
m = c;
}

return m;
}

int minCost (int a[3][3] , int m, int n) {

int cost[m][n];

cost[0][0] = a[0][0];

for (int i = 1; i <= n ; i++) {
cost[0][i] = cost[0][i-1] + a[0][i];
}

for (int j = 1; j <= m; j++) {
cost[j][0] = cost[j-1][0] + a[j][0];
}

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cost[i][j] = a[i][j] + min_num (cost[i-1][j-1] , cost[i][j-1] ,cost[i-1][j]);
}
}

return cost[m][n];
}

int main() {
int cost[3][3] = { {1, 2, 3},
                      {4, 8, 2},
                      {1, 5, 3} };
    printf(" %d ", minCost(cost, 2, 2));
    return 0;
}

Edit distance between two strings

The edit distance between two strings is the minimum changes required to make two strings identical.
There can be three operations

• Insertion of character
• Deletion of character
• Replace the character

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

int min (int a, int b, int c) {

int m = a;

if (a > b) {
m = b;
}

if (c > m) {
return m;
} else {
return c;
}
}

int editDistance (string s1, string s2, int m, int n) {

int dp[m+1][n+1];

for (int i = 0; i<= m; i++) {
for (int j = 0; j <=n ; j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1 + min (dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
}
}
}

return dp[m][n];
}

int main() {
    string str1 = "mist";
    string str2 = "misty";

    cout << editDistance(str1, str2, str1.length(), str2.length());

    return 0;
}

Longest Increasing Subsequence

#include <iostream>
using namespace std;

int lis (int arr[], int len) {

int * lis = new int[len];
int max = 0;

for (int i = 0; i< len; i++){
lis[i] = 1;
}

for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
lis[i] = lis[j] + 1;
}
}
}

for (int i = 0;i< len ;i++) {
if (max < lis[i]) {
max = lis[i];
}
}

delete (lis);

return max;
}

int main() {
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Length of LIS is %d\n",  lis( arr, n ));
    return 0;
}

Pattern Matching KMP Algorithm

#include <iostream>
#include <string>

using namespace std;

int main() {
string text = "abxabcabcaby";
string pattern = "abcaby";

int n  = text.length();
int m  = pattern.length();
int j = 0;

int * prefix = new int [m];
prefix [0] = 0;

for (int i = 1; i< m; i++) {
if (pattern[i] == pattern[j]) {
prefix[i] = j + 1;
j++;
} else if (prefix[i-1] == 0){
continue;
} else {
j = prefix[i - 1];
}
}

for (int i = 0; i< m; i++) {
cout<<prefix[i];
}

int i = 0;
j = 0;

while(i < n) {

if (pattern[j] == text[i]) {
j++;
i++;
}

if (j == m) {
printf("Found pattern at index %d \n", i-j);
        j = prefix[j-1];
} else if (i < n && pattern[j] != text[i]){
if (j != 0)
          j = prefix[j-1];
        else
          i = i+1;
}
}

delete (prefix);
return 0;
}