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.

Steps HMAC implementations

ð  Client and server share a secret access key and a public access key.

ð  Client create a request that contains three fundamental elements:

      public key header (in plain text),

      date header,

      Signature string calculated hashing data of the request with the secret access key.

This hash usually contains the http method, the URI path, the value of the date header

(for reply attacks), all the content of the request (for POST and PUT methods) and the  

content type.

ð  Client send the request to the server.

ð  Server read the public key header and use it to retrieve the corresponding private access key.

ð  Server use the private access key to calculate the signature in the same way as the client did.

ð  Server check if the just-calculated signature matches with the one sent by the client.

ð  To prevent replay attacks, We can also apply the acceptable time limit using date passed in header. Server checks that the value in the date header is within an acceptable limit (usually between 5 and 15 minutes to account clock discrepancy). The value cannot be manipulated by malicious attacker because the date it's used as part of the signature. If someone change the date header, the server will calculated a different signature of that calculated by the client, so above step will fail.

ð  Other than granting user identity (nobody should know the secret access key other than the client itself. and the server of course), this mechanism also ensure the integrity of the message. If someone change something in the request, the signature won't match.

Please check it:

http://www.smartjava.org/content/protect-rest-service-using-hmac-play-20

http://www.javacodegeeks.com/2012/04/dzoneprotect-rest-service-using-hmac.html

http://massimilianosciacco.com/implementing-hmac-authentication-rest-api-spring-security

@RequestBody, @ResponseBody, @RequestHeader and @CookieValue

@RequestBody

org.springframework.web.bind.annotation.RequestBody

@Target(value={PARAMETER})

@Retention(value=RUNTIME)

Annotation indicating a method parameter should be bound to the body of the web request.

The body of the request is passed through an HttpMessageConverter to resolve the method argument depending on the content type of the request.

Optionally, automatic validation can be applied by annotating the argument with @Valid.

Supported for annotated handler methods in Servlet environments.

@ResponseBody

org.springframework.web.bind.annotation.ResponseBody

@Target(value={METHOD, TYPE})

@Retention(value=RUNTIME)

Annotation that indicates a method return value should be bound to the web response body. Supported for annotated handler methods in Servlet environments.

As of version 4.0 this annotation can also be added on the type level in which case it is inherited and does not need to be added on the method level.

import org.springframework.beans.factory.annotation.Autowired;

import org.springframework.http.MediaType;

import org.springframework.stereotype.Controller;

import org.springframework.web.bind.annotation.RequestBody;

import org.springframework.web.bind.annotation.RequestMapping;

import org.springframework.web.bind.annotation.RequestMethod;

import org.springframework.web.bind.annotation.ResponseBody;

import org.apache.log4j.Logger;

import com.abusecore.model.Count;

import com.abusecore.model.Status;

import com.abusecore.model.Ticket;

import com.abusecore.services.IDataServices;

@Controller

@RequestMapping("/AbuseCore-1")

public class RestController {

       @Autowired

       IDataServices dataServices;

       /** Logger class to display logs. */

       static final Logger logger = Logger.getLogger(RestController.class);

       @RequestMapping(value = "/count-tickets.json", method = RequestMethod.GET)

       public @ResponseBody Count getTicketsCount() {

              Count count = dataServices.getTicketsCount();

              logger.info("total tickets :" + count);

              return count;

       }

       @RequestMapping(value = "/create", method = RequestMethod.POST,

                     consumes = MediaType.APPLICATION_JSON_VALUE)

       public @ResponseBody Status addEmployee(@RequestBody Ticket ticket) {

              try {

                     dataServices.addEntity(ticket);

                     return new Status(1, "Ticket added Successfully !");

              } catch (Exception e) {

                     // e.printStackTrace();

                     return new Status(0, e.toString());

              }

       }

}

@RequestHeader

org.springframework.web.bind.annotation.RequestHeader

@Target(value={PARAMETER})

@Retention(value=RUNTIME)

Annotation which indicates that a method parameter should be bound to a web request header.

Supported for annotated handler methods in Servlet and Portlet environments.

If the method parameter is Map<String, String> or MultiValueMap<String, String>, or HttpHeaders then the map is populated with all header names and values.

@CookieValue

org.springframework.web.bind.annotation.CookieValue

@Target(value={PARAMETER})

@Retention(value=RUNTIME)

Annotation which indicates that a method parameter should be bound to an HTTP cookie. Supported for annotated handler methods in Servlet and Portlet environments.

The method parameter may be declared as type javax.servlet.http.Cookie or as cookie value type (String, int, etc).

Stack vs. Heap Memory

Java Heap Memory

Heap memory is used by java runtime to allocate memory to Objects and JRE classes. Whenever we create any object, it’s always created in the Heap space.

Garbage Collection runs on the heap memory to free the memory used by objects that doesn’t have any reference. Any object created in the heap space has global access and can be referenced from anywhere of the application.

Java Stack Memory

Java Stack memory is used for execution of a thread. They contain method specific values that are short-lived and references to other objects in the heap that are getting referred from the method.

Stack memory is always referenced in LIFO (Last-In-First-Out) order. Whenever a method is invoked, a new block is created in the stack memory for the method to hold local primitive values and reference to other objects in the method. As soon as method ends, the block becomes unused and become available for next method.

Difference between Heap and Stack Memory

Heap memory	Stack memory
Heap memory is used by all the parts of the application.	whereas stack memory is used only by one thread of execution.
Whenever an object is created, it’s always stored in the Heap space and stack memory contains the reference to it.	Stack memory only contains local primitive variables and reference variables to objects in heap space.
Objects stored in the heap are globally accessible.	Stack memory can’t be accessed by other threads.
Heap memory is more complex because it’s used globally and  Heap memory is divided into Young-Generation, Old-Generation etc.	Memory management in stack is done in LIFO manner.
We can use -Xms and -Xmx JVM option to define the startup size and maximum size of heap memory.	We can use -Xss to define the stack memory size.
If heap memory is full, it throws java.lang.OutOfMemoryError: Java Heap Space error.	When stack memory is full, Java runtime throws java.lang.StackOverFlowError.
	Because of simplicity in memory allocation (LIFO), stack memory is very fast when compared to heap memory.
Heap memory lives from the start till the end of application execution.	Stack memory is short-lived.
Stack memory size is very less when compared to Heap memory.