Space Complexity

Space Complexity:

Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size.

Space complexity includes both Auxiliary space and space used by input.

Space complexity = Auxiliary space + space used by input

For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be better criteria than Space Complexity.

Merge Sort uses O(n) auxiliary space (extra space), Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.

Prototype Design Pattern

This pattern is used when creation of object directly is costly. Prototype Pattern says that cloning of an existing object instead of creating new one and can also be customized as per the requirement.

For example,
Suppose we are doing a sales analysis on a set of data from a database. Normally, we would copy the information from the database, encapsulate it into an object and do the analysis. But if another analysis is needed on the same set of data, reading the database again and creating a new object is not the best idea. If we are using the Prototype pattern then the object used in the first analysis will be cloned and used for the other analysis.

public interface Prototype {

      public abstract Object clone ( );

}

public class ConcretePrototype implements Prototype {

      public Object clone() {

            return super.clone();

      }

}

public class Client {

      public static void main( String arg[] ) {

            ConcretePrototype obj1= new ConcretePrototype ();

            ConcretePrototype obj2 = (ConcretePrototype)obj1.clone();

      }

}

Application:

Session replication from one server to another server.

Generating the GUI having many numbers of similar controls.

Advantage of Prototype Pattern

It reduces the need of sub-classing.

It hides complexities of creating objects.

The clients can get new objects without knowing which type of object it will be.

It lets you add or remove objects at runtime.

Usage of Prototype Pattern

When the classes are instantiated at runtime.

When the cost of creating an object is expensive or complicated.

When you want to keep the number of classes in an application minimum.

When the client application needs to be unaware of object creation and representation.

Template Method Pattern

Template method defines the steps to execute an algorithm and it can provide default implementation that might be common for all or some of the subclasses.

package oops.design.patterns.template;

public abstract class InterviewProcess {

       abstract void written();

       abstract void technical();

       abstract void manager();

       abstract void hrRounds();

       // Template method - Sequence of processes.

       public final void judgeCandidate() {

              written();

              technical();

              manager();

              hrRounds();

       }

}

package oops.design.patterns.template;

public class OrangeInterview extends InterviewProcess {

       @Override

       void written() {

              System.out.println("written : Orange!");

       }

       @Override

       void technical() {

              System.out.println("technical : Orange!");

       }

       @Override

       void manager() {

              System.out.println("manager : Orange!");

       }

       @Override

       void hrRounds() {

              System.out.println("hr rounds : Orange!");

       }

}

package oops.design.patterns.template;

public class ExpediaInterview extends InterviewProcess {

       @Override

       void written() {

              System.out.println("written : Expedia!");

       }

       @Override

       void technical() {

              System.out.println("technical : Expedia!");

       }

       @Override

       void manager() {

              System.out.println("manager : Expedia!");

       }

       @Override

       void hrRounds() {

              System.out.println("hr rounds : Expedia!");

       }

}

package oops.design.patterns.template;

public class TestCandidate {

       public static void main(String[] args) {

              InterviewProcess orangeInterview = new OrangeInterview();

              orangeInterview.judgeCandidate();

             

              System.out.println("\n");

             

              InterviewProcess expediaInterview = new ExpediaInterview();

              expediaInterview.judgeCandidate();

       }

}

Output:

written : Orange!

technical : Orange!

manager : Orange!

hr rounds : Orange!

written : Expedia!

technical : Expedia!

manager : Expedia!

hr rounds : Expedia!

                                         

Template Method Pattern in JDK

1.All non-abstract methods of java.io.InputStream, java.io.OutputStream, java.io.Reader and java.io.Writer.

2.All non-abstract methods of java.util.AbstractList, java.util.AbstractSet and java.util.AbstractMap.

Things to remember

1.Template method should be final.

2.Template method should consist of certain steps whose order is fixed and for some of the methods; implementation differs from base class to subclass.

3.Most of the times, subclasses calls methods from super class however in template pattern, superclass template method calls methods from subclasses.

Longest Repeating Subsequence

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

Examples:

inputStr = "abc"

Output: 0

inputStr = "aab"

Output: 1

aab

 aab

inputStr = "aabb"

Output: 2

a a b b

  a a b b

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

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

} else {

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

}

package geeks.dp;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class LongestRepeatingSubsequence {

       public static void main(String[] args) throws IOException {

                 BufferedReader buffReader = new BufferedReader(

                                             new InputStreamReader(System.in));

                 char[] inputChars = buffReader.readLine().toCharArray();

                 int length = inputChars.length;

                

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

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

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

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

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

                                   } else {

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

                                   }

                          }

                 }

                 System.out.println(dp[length][length]);

         }

}