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;
}