Friday, 21 July 2017

Algorithms | Maximum difference between two elements where larger element appears after the smaller number

Given an array of integers, find out the difference between any two elements such that larger element appears after the smaller number in the array.

Examples:
If an array is {80, 2, 6, 3, 100} then returned value should be 98 (Difference between 100 and 2).

package com.algorithms.forum.array;
/**
 * In a given array of numbers, identify maximum difference between
 * 2 numbers such that array[i]<array[j] where i<j.
 * @author algos.debug
 */
public class MaximizeDifference {
    
     private static int getMaximumDiff(int[] array) {

           int length = array.length;
           int maxSoFar = array[length-1];
          
           int maxDiff = Integer.MIN_VALUE;
          
           for (int i = length-2; i >=0 ; i--) {
                maxDiff =  Math.max(maxSoFar-array[i], maxDiff);
                maxSoFar = Math.max(array[i], maxSoFar);
           }
           return maxDiff;
     }
    
     public static void main(String[] args) {
           int[] array = {80, 2, 6, 3, 100};
          
           int diff = getMaximumDiff(array);
          
           System.out.println(diff);
     }
}
Output: 98

Thursday, 20 July 2017

Design Patterns | Factory Method Pattern (Virtual Constructor)

When we want to return one sub-class object from multiple sub-classes using an input, should use Factory design pattern. Factory class takes responsibility of instantiation the class (We can return Singleton instance from static factory method).
In Factory pattern, we create an object without exposing the creation logic to the client and refer to a newly created object using a common interface.



Example:
Coffee/Vending machine, give input from options and as per input coffee, lemon tea, plain milk or hot water will be an output.

package com.algorithm.forum.design.patterns;

enum Choice {
     Coffee, LemonTea, PlainWater;
}

interface Drink {
     void prepare();
}

class Coffee implements Drink {
     @Override
     public void prepare() {
           System.out.println("Coffee is prepared !!");
     }
}

class LemonTea implements Drink {
     @Override
     public void prepare() {
           System.out.println("Lemon Tea is prepared !!");
     }
}

class PlainWater implements Drink {
     @Override
     public void prepare() {
           System.out.println("Plain Water is prepared !!");
     }
}

class VedingMachine {
     private static String pck = "com.algorithm.forum.design.patterns.";

     /**
      * This method will return the Drink on the basis of required data.
      * Simple if else blocks are used here.
      */
     public static Drink getDrink(Choice choice) {
           Drink drink = null;
           if(choice==Choice.PlainWater) {
                drink = new PlainWater();
           } else if(choice==Choice.Coffee) {
                drink = new Coffee();
           } else if(choice==Choice.LemonTea) {
                drink = new LemonTea();
           }
           return drink;
     }

     /**
      * This method will create the Drink using Reflection as per the requested data.
      */
     public static Drink getDrinkReflection(Choice choice) {
           Drink drink = null;
           String className = pck +choice.toString();
           try {
                drink = (Drink) Class.forName(className).newInstance();
           } catch (InstantiationException | IllegalAccessException
                     | ClassNotFoundException e) {
           }
           return drink;
     }
}

public class FactoryPatternTest {
     public static void main(String[] args) {
           System.out.println("Create factory using if else:");
           Drink drink = VedingMachine.getDrink(Choice.Coffee);
           drink.prepare();

           System.out.println("\nCreate factory using Reflection:");
           drink = VedingMachine.getDrinkReflection(Choice.LemonTea);
           drink.prepare();
     }
}
Output:
Create factory using if else:
Coffee is prepared!!

Create factory using Reflection:
Lemon Tea is prepared!!

Benefits of Factory Method Pattern:
Factory Method Pattern provides an approach to code for interface rather than implementation and it provides the abstraction between implementation and client classes through inheritance.
Factory Method Pattern allows the sub-classes to choose the type of objects to create. We can easily change the implementation of sub-class because client program is unaware of this. It makes the code more robust, less coupled and easy to extend (client interacts solely with the resultant interface or abstract class).

Usage in JDK:
java.util.Calendar, ResourceBundle and NumberFormat getInstance() methods uses Factory pattern.
valueOf() method in wrapper classes like Boolean, Integer etc.
Spring and Hibernate frameworks.


Algorithms | Generate n unique Random numbers

 Fisher–Yates shuffle Algorithm works in O(1) time complexity to generate the random number. The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.

RandomGenerator.java
package com.algorithmforum.rand;
import java.util.Random;
public class RandomGenerator {

     private static int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

     private static int maxIdx = array.length-1;

     /** This function to generate a random number for every new request. */
     private static int genRand() {
           /*
            * Start from the last element and swap one by one.
            * We don't need to run for the first element that's why i> 0
            */

           /** Pick a random index from 0 to i.*/
           Random rand = new Random();
           int randIdx = rand.nextInt(50);
           int j = randIdx % (maxIdx+1);

           /** Swap array[i] with the element at random index. */
           swap(maxIdx, j);
          
           return array[maxIdx--];
     }

     /** A utility function to swap to integers. **/
     private static void swap (int i, int j) {
           int temp = array[i];
           array[i] = array[j];
           array[j] = temp;
     }

     /** Driver method. */
     public static void main(String[] args) {
           for (int i = 0; i <=10; i++) {
                int random = RandomGenerator.genRand();
                System.out.println("Random number "+i+": "+ random);
           }
     }
}

Output:
Random number 0: 7
Random number 1: 8
Random number 2: 10
Random number 3: 6
Random number 4: 5
Random number 5: 9
Random number 6: 0
Random number 7: 3
Random number 8: 2
Random number 9: 4
Random number 10: 1


Related Posts Plugin for WordPress, Blogger...