Design Patterns & Principles

Design patterns and principles
1.	Design Principle vs. Design Pattern
2.	What algorithm is used in modern day elevators?
3.	Singleton Design Pattern - A Creational Design Patterns
4.	Factory Method Pattern (Virtual Constructor)
5.	Prototype Design Pattern
6.	Builder Design Pattern in Java
7.	Abstract Factory
8	Proxy Pattern
9	Flyweight Pattern - A Structural design pattern
10	Decorator design pattern
11	Adapter Pattern
12	Bridge Pattern
13	Composite Pattern
14	Facade pattern
15	Template Method Pattern
16	Strategy Pattern (Policy Pattern) - A behavioral design pattern
17	Iterator pattern or Cursor
18	Mediator pattern
19	Memento Design Pattern in Java
20	Observer pattern or Publish-subscribe pattern
21	State
22	Pizza Factory design in Java

What is Interceptor in Struts2?

Interceptor is an object that is invoked at the preprocessing and post processing of a request. In Struts 2, interceptor is used to perform operations such as validation, exception handling, internationalization, displaying intermediate result etc.

ActionInvocation is responsible to encapsulate Action classes and interceptors and to fire them in order. The most important method for use in ActionInvocation is invoke() method that keeps track of the interceptor chain and invokes the next interceptor or action. This is the best example of Chain of Responsibility pattern in J2EE.

Interceptors are conceptually the same as servlet filters or the JDKs Proxy class.

Advantage of interceptors

Interceptor plays a crucial role in achieving high level of separation of concerns.

Providing preprocessing/post processing logic before/after the action is called.

Catching exceptions so that alternate processing can be performed.

Pluggable if we need to remove any concern such as validation, exception handling, logging etc. from the application, we don't need to redeploy the application. We only need to remove the entry from the struts.xml file.

Which design pattern is implemented by Struts2 interceptors?

Struts2 interceptors are based on intercepting filters design pattern. 

The invocation of interceptors in interceptor stack closely resembles Chain of Responsibility design pattern.

Longest Repeating Subsequence

Find length of the longest repeating subsequence such that the two subsequences don’t have same string character at same position, i.e., any k’th character in the two subsequences shouldn’t have the same index in the original string.

This problem can be solved using the Longest Common Subsequence problem. LRS(str, str) where str is the input string with the restriction that when both the characters are same, they shouldn’t be on the same index in the two strings.

package amazon.dp;

public classLongestRptSubseq {

     private static int getLRS(String string) {

          

           char[] charArray = string.toCharArray();

           int len = charArray.length;

          

           int[][] dp = new int[len+1][len+1];

          

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

               

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

                     // If characters match and indexes are not same

                     if (charArray[i-1] == charArray[j-1] && i!=j) {

                           dp[i][j] =  1 + dp[i-1][j-1];

                          

                     } else {

                           // If characters do not match

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

                     }

                }

           }

          

           return dp[len-1][len-1];

     }

     public static voidmain(String[] args) {

           String string = "amazonazom";

           int len = getLRS(string);

           System.out.println("Longest Repeating Subsequence "+len);

     }

}

Count number of ways to cover a distance

Count total number of ways to cover the distance with 1, 2 and 3 steps.

Recursion solution time complexity is exponential i.e. O(3n).

Since same sub problems are solved again, this problem has overlapping sub problems property. So min square sum problem has both properties of a dynamic programming problem.

public class MaxStepsCount {

     /** Dynamic Programming. */

     private static int getMaxWaysDP(int distance) {

           int[] count = new int[distance+1];

           count[0] = 1;

           count[1] = 1;

           count[2] = 2;

           /** Memorize the Sub-problem in bottom up manner*/

           for (int i=3; i<=distance; i++) {

                count[i] = count[i-1] + count[i-2] + count[i-3];               

           }

           return count[distance];

     }

     /** Recursion Approach. */

     private static int getMaxWaysRecur(intdistance) {

           if(distance<0) {

                return 0;

           } else if(distance==0) {

                return 1;

           }

           return getMaxWaysRecur(distance-1)+getMaxWaysRecur(distance-2)

                     +getMaxWaysRecur(distance-3);

     }

     public static void main(String[] args) {

           // Steps pf 1, 2 and 3.

           int distance = 10;

           /** Recursion Approach. */

           int ways = getMaxWaysRecur(distance);

           System.out.println(ways);

           /** Dynamic Programming. */

           ways = getMaxWaysDP(distance);

           System.out.println(ways);

     }

}