Maximum weight path ending of last row in a matrix

Find the path having the maximum weight in integer matrix [N X M].

Conditions for moves:

Path should begin from top left element and can end at any element of last row. We can move to down (i+1, j) or diagonal forward (i+1, j+1).

public class MaxWeightPathMatrix {

    

     /**

      * Moves # down or forward diagonal.

      * @param matrix

      * @return Returns the maximum weight.

      */

     private static int getMaxWeightPath(int[][] matrix) {

           int row = matrix.length;

           int col = matrix[0].length;

           int[][] dp = new int[row][col];

           /** Initialize first row of total weight */

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

                dp[0][i] = matrix[0][i];

           }

           /** Initialize first column of total weight */

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

                dp[i][0] = matrix[i][0] + dp[i-1][0];

           }

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

                for(int j=1; j<col; j++) {

                     dp[i][j] = matrix[i][j] + Math.max(dp[i-1][j],

                                dp[i-1][j-1]);

                }

           }

           /** Max weight path sum to rech the last row */

           int result = 0;

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

                result = Math.max(dp[row-1][i], result);

           }

           return result;

     }

    

     /** Driver method. */

     public static void main(String[] args) {

          

           int[][] matrix = {{ 8, 4 ,6 ,8 ,2 },

                     { 4 , 18 ,2 ,20 ,10 },

                     {20, 2 ,6 , 0 ,40 },

                     {32 ,184, 82, 88 ,2},

                     {16, 302, 12, 8, 18}};

           int maxWeight = getMaxWeightPath(matrix);

           System.out.println("Maximum weight path ending at any"

                     + " element of last row in a matrix # "+ maxWeight);

     }

}

Advantages and disadvantages immutable objects

Advantages of immutable objects:

1. An immutable object remains in exactly one state, the state in which it was created. Therefore, immutable object is thread-safe so there is no synchronization issue. They cannot be corrupted by multiple threads accessing them concurrently. This is far and away the easiest approach to achieving thread safety.

2. Immutable classes are easier to design, implement, and use than mutable classes.

3. Immutable objects are good Map keys and Set elements, since these typically do not change once created.

4. Immutability makes it easier to write, use and reason about the code (class invariant is established once and then unchanged).

5. Immutability makes it easier to parallelize program as there are no conflicts among objects.

6. The internal state of program will be consistent even if you have exceptions.

7. References to immutable objects can be cached as they are not going to change. (i.e. in Hashing it provide fast operations).

Disadvantages of immutable objects:

Creating an immutable class seems at first to provide an elegant solution. However, whenever you do need a modified object of that new type you must suffer the overhead of a new object creation, as well as potentially causing more frequent garbage collections. The only real disadvantage of immutable classes is that they require a separate object for each distinct value.

Creating these objects can be costly, especially if they are large.

Single responsibility principle

A class should have only one reason to change.

This principle states that if we have 2 reasons to change for a class, we have to split the functionality in two classes. Each class will handle only one responsibility and if in the future we need to make one change we are going to make it in the class which handles it.

If there are two different reasons to change, it is conceivable that two different teams may work on the same code for two different reasons. Each will have to deploy its solution, which in the case of a compiled language (like C++, C# or Java), may lead to incompatible modules with other teams or other parts of the application.

This principle is closely related to the concepts of coupling and cohesion. Coupling refers to how inextricably linked different aspects of an application are, while cohesion refers to how closely related the contents of a particular class or package may be.  All of the contents of a single class are tightly coupled together, since the class itself is a single unit that must either be entirely used or not at all.

Open Closed Design Principle

In Design principle, SOLID – the "O" in "SOLID" stands for the open/closed principle.

Open Closed principle is a design principle which says that a class, modules and functions should be open for extension but closed for modification.

This principle states that the design and writing of the code should be done in a way that new functionality should be added with minimum changes in the existing code (tested code). The design should be done in a way to allow the adding of new functionality as new classes, keeping as much as possible existing code unchanged.

Benefit of Open Closed Design Principle:

1) Application will be more robust because we are not changing already tested class.

2) Flexible because we can easily accommodate new requirements.

3) Easy to test and less error prone.

Why Class CloneNotSupportedException is a checked Exception?

java.lang.CloneNotSupportedException - A Checked Exception

If the object's class does not support the Cloneable interface. Subclasses that override the clone method can also throw this exception to indicate that an instance cannot be cloned.

Why is it a checked Exception?

It was developed in earlier phase of the Java, there was very little experience of when it would make sense for an exception to be checked.

Some exceptions which are checked but probably shouldn't be and occasions where the exception is unchecked but should be checked.

Integer.parseInt throwing NumberFormatException probably being the clearest example.

Why should it a unchecked exception?
http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4220218

Chain of Responsibility Design Pattern

Decoupling is one of the prominent mantras in software engineering.

Chain of responsibility helps to decouple sender of a request and receiver of the request with some trade-offs.

Chain of responsibility is a design pattern where a sender sends a request to a chain of objects, where the objects in the chain decide themselves who to honor the request. If an object in the chain decides not to serve the request, it forwards the request to the next object in the chain.

In a chain of objects, the responsibility of deciding who to serve the request is left to the objects participating in the chains.

                          

èIt is similar to ‘passing the question in a quiz scenario’. When the quiz master asks a question to a person, if he doesn’t knows the answer, he passes the question to next person and so on. When one person answers the question, the passing flow stops. Sometimes, the passing might reach the last person and still nobody gives the answer.

Currency.java

public class Currency {

     private int amount;

     public Currency(int amt){

           this.amount = amt;

     }

     public int getAmount(){

           return this.amount;

     }

}

DispenseChain.java

public interface DispenseChain {

     void setNextChain(DispenseChain nextChain);

    

     void dispense(Currency cur);

}

Rupees1000Dispenser.java

public class Rupees1000Dispenser implements DispenseChain {

     private DispenseChain chain;

    

     @Override

     public void setNextChain(DispenseChain nextChain) {

           this.chain=nextChain;

     }

     @Override

     public void dispense(Currency cur) {

           if(cur.getAmount() >= 1000){

                int num = cur.getAmount()/1000;

                int remainder = cur.getAmount() % 1000;

                System.out.println("Dispensing "+num+" Rs. 1000 note");

                if(remainder !=0) this.chain.dispense(new Currency(remainder));

           } else {

                this.chain.dispense(cur);

           }

     }

}

Rupees500Dispenser.java

public class Rupees500Dispenser implements DispenseChain{

     private DispenseChain chain;

     @Override

     public void setNextChain(DispenseChain nextChain) {

           this.chain=nextChain;

     }

     @Override

     public void dispense(Currency cur) {

           if(cur.getAmount() >= 500){

                int num = cur.getAmount()/500;

                int remainder = cur.getAmount() % 500;

                System.out.println("Dispensing "+num+" Rs. 500 note");

                if(remainder !=0) this.chain.dispense(new Currency(remainder));

           } else {

                this.chain.dispense(cur);

           }

     }

}

Rupees100Dispenser.java

public class Rupees100Dispenser implements DispenseChain {

     private DispenseChain chain;

    

     @Override

     public void setNextChain(DispenseChain nextChain) {

           this.chain=nextChain;

     }

     @Override

     public void dispense(Currency cur) {

           if(cur.getAmount() >= 100) {

                int num = cur.getAmount()/100;

                int remainder = cur.getAmount() % 100;

                System.out.println("Dispensing "+num+" Rs. 100 note");

                if(remainder !=0) this.chain.dispense(new Currency(remainder));

           } else {

                this.chain.dispense(cur);

           }

     }

}

ATMDispenseChain.java

public class ATMDispenseChain {

     private DispenseChain chainStart;

     public ATMDispenseChain() {

          

           // initialize the chain

           this.chainStart = new Rupees1000Dispenser();

           DispenseChain chain500 = new Rupees500Dispenser();

           DispenseChain chain100 = new Rupees100Dispenser();

           // set the chain of responsibility

           chainStart.setNextChain(chain500);

           chain500.setNextChain(chain100);

     }

    

     public DispenseChain getChainStart() {

           return chainStart;

     }

}

TestChainPattern.java

import java.util.Scanner;

public class TestChainPattern {

     public static void main(String[] args) {

           ATMDispenseChain atmDispenser = new ATMDispenseChain();

           int amount = 0;

           System.out.println("Enter amount to dispense");

           Scanner input = new Scanner(System.in);

           amount = input.nextInt();

           if (amount % 100 != 0) {

                System.out.println("Amount should be in multiple of 100s.");

                return;

           }

           // process the request

           atmDispenser.getChainStart().dispense(new Currency(amount));

           input.close();

     }

}

Chain of Responsibility Pattern Examples

ATM dispense machine.

Struts interceptor.

Usage of Chain of Responsibility Pattern in JDK

java.util.logging.Logger#log()

javax.servlet.Filter#doFilter()