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.

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]);

         }

}

Flyweight Pattern - A Structural design pattern

To reuse the object those are already created.

1. Reuse the object that already existing (earlier created and stored)

2. Create new object when no matching object is found.

This can be used to reduce memory requirements and substantiation time and related costs (object creational cost).

Similarities between objects are stored inside of the objects (intrinsic), and differences are moved outside of the objects and placed in client code (extrinsic).

Advantages

It reduces the number of objects.

It reduces the amount of memory and storage devices required if the objects are persisted.

Usage

When an application uses number of objects

When the storage cost is high because of the quantity of objects.

When the application does not depend on object identity.

Flyweight Pattern Example in JDK

All the wrapper classes valueOf() method uses cached objects showing use of Flyweight design pattern.

The best example is Java String class String Pool implementation.

Real Life Examples

Web browser

Modern web browsers use this technique to prevent loading same images twice. When browser loads a web page, it traverses through all images on that page. Browser loads all new images from Internet and places them the internal cache. For already loaded images, a flyweight object is created, which has some unique data like position within the page, but everything else is referenced to the cached one.

Game of war

A game of war, were there is a large number of soldier objects; a soldier object maintain the graphical representation of a soldier, soldier behaviour such as motion, and firing weapons, in addition soldiers health and location on the war terrain. Creating a large number of soldier objects is a necessity however it would incur a huge memory cost. Note that although the representation and behaviour of a soldier is the same their health and location can vary greatly.