How to make the session in a Web Application secure

• Using HTTPS to transfer session id and cookies as well. (If cookie is transferred over HTTP it can be easily stolen and used for impersonation)
• Sending an entropic unique token in the hidden field in the page. The server authenticates the user based on this token, otherwise rejects the user request.
• Session id/token should be unpredictable. Could be generated using java.security.SecureRandom class in Java or as explained in the post: http://technocratme.blogspot.in/2012/04/universally-unique-identifier-uuid.html
• To confirm the authenticity of the sender of request, one can compare the sender's IP address with the IP of the user who created the session.

Prime No., GCD, LCM calculations

// Calculate all primes upto N, set the boolean to true for all composites

  boolean isComposite[] = new boolean[N+1];
// calculate all primes upto N
for(int i=2;i*i<=N;i++){
if(!isComposite[i]){ // if prime
for(int j=i*i;j<=N;j+=i){
isComposite[j] = true;
}
}
}

// Calculate the GCD of 2 no.s using recursive euclidean algorithm

  private static long gcd(int a, int b) {
if(a<b){
// swap numbers
a = a^b;
b = b^a;
a = a^b;
}
if(b == 0)
return a;
return gcd(b,a%b);
}

private static long lcm(int a, int b) {
return a*b/gcd(a,b);
}

EQUATIONS

Solution:
1/x + 1/y = 1/N!
=> x = y*N!/(y-N!)

Say y = N!+Z,
=> x = (N!+Z)*N! / Z = N!^2 / Z + N!.
For 'x' to be integer, 'Z' can take values equal to the no. of divisors of N!^2.

No .of divisors is calculated in the following manner: http://technocratme.blogspot.in/2012/07/divisor-counting.html

import java.util.Scanner;

public class EQUATIONS {

public static int getPowerOfPrimeInNFact(int N,int prime){
int pow = N/prime;
int tmp = 0;
while(pow>0){
tmp +=pow;
pow = pow/prime;
}
return tmp;
}
public static void main(String args[]) throws Exception {
Scanner in = new Scanner((System.in));
//System.out.println(getPowerOfPrimeInNFact(18,3));
int N = in.nextInt();
boolean isComposite[] = new boolean[1000001];
int [] powPrimes = new int[1000001];
// calculate all primes in first 1 million
for(int i=2;i<=1000;i++){
if(!isComposite[i]){ // if prime
for(int j=i*i;j<=1000000;j+=i){
isComposite[j] = true;
}
}
}
long no_div = 1;
for(int i=2;i<=N;i++){
if(!isComposite[i]){ // if prime
//System.out.println(i);
// Find powers of all primes
powPrimes[i] = getPowerOfPrimeInNFact(N,i);
// find the continual mod of the tot. no. of divisors of N!*N!
no_div = ((2*powPrimes[i]+1)*no_div)%1000007;
}
}
System.out.println(no_div);
}
}

Daemon vs Non Daemon thread in Java

 A Thread can be made a daemon, which makes it run in the background. The latter also affects VM termination behavior: the VM does not terminate automatically as long as there are non-daemon threads running.

A daemon Thread only runs as long as there are non-daemon Threads running. When the last non-daemon Thread ends, the whole program ends no matter if it had daemon Threads still running or not; i.e. A running daemon thread can be terminated by the VM, however a running non-daemon thread can not be terminated by the VM.

An example:

Imagine a Java application. It starts off with just one thread, the "main" thread which runs the main method. This is a regular (non-daemon) thread. Now imagine again that the program starts another thread which sits in a loop doing something. If the new thread is a regular (non-daemon) thread, it will prevent the program from finishing when "main" ends, and keep going forever!

Now, this isn't always what is required. Sometimes you want to end this "background" processing when the program finishes. To do this, you can mark threads as daemon threads. Daemon threads don't prevent the program from ending, but stop when the main thread, stops:

1. Thread hello = new HelloThread();  
2. hello.setDaemon(true);  

A classic example of a daemon thread is the garbage collector thread found in many Java Virtual Machines. It needs to run continuously while any other threads are running, but should not prevent the program from exiting. When the program exits, there is no more need for a garbage collector.

http://www.coderanch.com/t/230947/threads/java/Daemon-threads-non-daemon-Threads

Making a jar runnable

This is based on using the MANIFEST.MF file inside the jar, which points to the 'Main class' of the jar and setting the class path too.

http://www.crazysquirrel.com/computing/java/basics/runnable-jar.jspx

Java Shutdown Hooks

 A shut down hook is simply a Thread that is registered with the JVM and run just before the JVM shuts down.


Example code taken from the below mentioned link:




package example;public class ShutdownHook {

  /**
   * @param args
   */
  public static void main(String[] args) {
    Hook hook = new Hook();
    System.out.println( "Running Main Application..." );
    Runtime.getRuntime().addShutdownHook( hook );
    System.out.println( "Exiting." );
  }

  
  private static class Hook extends Thread {
    public void run() {
      System.out.println( "Running Clean Up..." );
    }
  }
}


http://www.crazysquirrel.com/computing/java/basics/java-shutdown-hooks.jspx

http://stackoverflow.com/questions/2921945/useful-example-of-a-shutdown-hook-in-java

Java Heap dumps and Thread dumps

THREAD DUMP
To take the thread dump of the running java process with process id = PID, use: "kill -3 PID".


The thread dump is written to the system out of the VM on which you executed the kill -3. If you are redirecting the console output of the JVM to a file, the thread dump will be in that file. If the JVM is running in an open console, then the thread dump will be displayed in its console.


You could alternatively use jstack (Included with JDK) to take a thread dump and write the output wherever you want

jstack PID > outfile

HEAP DUMP


You can use jdk utility 'jmap' to take the heap dump.


And use the jdk tool 'jhat' to analyse java heaps.


http://www.startux.de/java/45-java-heap-dump

Divisor counting

Count the number of divisors of a number given its prime factors in the form:

If a number n look like this:

n = a^p * b^q * c^r * d^s * e^t * f^u ... ,

where a,b, c and so on are its prime factors

then the number of divisors of n = (p+1)*(q+1)*(r+1)*...

This is because we can choose any number of a's from 0 to p, which gives us (p+1) choices, and so on.

http://mathforum.org/library/drmath/view/55741.html

String Similarity - Z function

For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2, while the similarity of strings "aaa" and "aaab" is 3.

Calculate the sum of similarities of a string S with each of it's suffixes.

Solution:

The solution is based on calculating the Z function of the string, where Z(i) is the maximum overlap length of the string S[0..] and S[i..].

Algorithm

Given a string S of length n, the Z Algorithm produces an array Z where Z[i] is the length of the longest substring starting from S[i]which is also a prefix of S, i.e. the maximum k such that S[j] = S[i + j] for all 0 ≤ j < k. Note that Z[i] = 0 means that S[0] ≠ S[i]. For easier terminology, we will refer to substrings which are also a prefix as prefix-substrings.

The algorithm relies on a single, crucial invariant. As we iterate over the letters in the string (index i from 1 to n - 1), we maintain an interval [L, R] which is the interval with maximum R such that 1 ≤ L ≤ i ≤ R and S[L...R] is a prefix-substring (if no such interval exists, just let L = R =  - 1). For i = 1, we can simply compute L and R by comparing S[0...] to S[1...]. Moreover, we also get Z[1] during this.

Now suppose we have the correct interval [L, R] for i - 1 and all of the Z values up to i - 1. We will compute Z[i] and the new [L, R]by the following steps:

• If i > R, then there does not exist a prefix-substring of S that starts before i and ends at or after i. If such a substring existed, [L, R]would have been the interval for that substring rather than its current value. Thus we "reset" and compute a new [L, R] by comparing S[0...] to S[i...] and get Z[i] at the same time (Z[i] = R - L + 1).
• Otherwise, i ≤ R, so the current [L, R] extends at least to i. Let k = i - L. We know that Z[i] ≥ min(Z[k], R - i + 1) becauseS[i...] matches S[k...] for at least R - i + 1 characters (they are in the [L, R] interval which we know to be a prefix-substring). Now we have a few more cases to consider.
• If Z[k] < R - i + 1, then there is no longer prefix-substring starting at S[i] (or else Z[k] would be larger), meaning Z[i] = Z[k] and[L, R] stays the same. The latter is true because [L, R] only changes if there is a prefix-substring starting at S[i] that extends beyond R, which we know is not the case here.
• If Z[k] ≥ R - i + 1, then it is possible for S[i...] to match S[0...] for more than R - i + 1 characters (i.e. past position R). Thus we need to update [L, R] by setting L = i and matching from S[R + 1] forward to obtain the new R. Again, we get Z[i] during this.

The process computes all of the Z values in a single pass over the string, so we're done. Correctness is inherent in the algorithm and is pretty intuitively clear.

Analysis

We claim that the algorithm runs in O(n) time, and the argument is straightforward. We never compare characters at positions less thanR, and every time we match a character R increases by one, so there are at most n comparisons there. Lastly, we can only mismatch once for each i (it causes R to stop increasing), so that's another at most n comparisons, giving O(n) total.

Code

Simple and short. Note that the optimization L = R = i is used when S[0] ≠ S[i] (it doesn't affect the algorithm since at the next iterationi > R regardless).

int L = 0, R = 0;
for (int i = 1; i < n; i++) {
  if (i > R) {
    L = R = i;
    while (R < n && s[R-L] == s[R]) R++;
    z[i] = R-L; R--;
  } else {
    int k = i-L;
    if (z[k] < R-i+1) z[i] = z[k];
    else {
      L = i;
      while (R < n && s[R-L] == s[R]) R++;
      z[i] = R-L; R--;
    }
  }
}

Application

One application of the Z Algorithm is for the standard string matching problem of finding matches for a pattern T of length m in a string Sof length n. We can do this in O(n + m) time by using the Z Algorithm on the string T Φ S (that is, concatenating T, Φ, and S) where Φis a character that matches nothing. The indices i with Z[i] = m correspond to matches of T in S.

Lastly, to solve Problem B of Beta Round 93, we simply compute Z for the given string S, then iterate from i to n - 1. If Z[i] = n - i then we know the suffix from S[i] is a prefix, and if the largest Z value we've seen so far is at least n - i, then we know some string inside also matches that prefix. That gives the result.

int maxz = 0, res = 0;
for (int i = 1; i < n; i++) {
  if (z[i] == n-i && maxz >= n-i) { res = n-i; break; }
  maxz = max(maxz, z[i]);
}

http://codeforces.com/blog/entry/3107

Merge Two Balanced Binary Search Trees

Solution:
Get the sorted values of both BSTs in O(m) + O(n), by doing in-order traversal of each BST.
Merge the two sorted arrays in O(m+n).
Create a balanced BST from sorted array in O(m+n).

http://www.geeksforgeeks.org/archives/18611