Next Greater Element

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

Amazing solution in the link below, based on a stack for O(n) time. I just loved it :P

Reading:http://www.geeksforgeeks.org/archives/8405

How to find the longest palindrome in a string in linear time

Solution:

Probably finding the LCS (longest common sub-sequence) between the string and its reverse.

anand tech blog ??

Microsoft Interview- Two elements of BST are swapped by mistake. You have to restore the tree without changing its structure.

Two elements of BST are swapped by mistake. You have to restore the tree without changing its structure.

Solution:

// incomplete solution

Node fixSwappedBST ( Node r, int min, int max, Node toFix){

// r - root node, r.val >= min && r.val <= max  and toFix is the node which needs to be fixed and was at a wrong   place in the left subtree of the common ancestor (of the swapped nodes)

 if(r==null) return null;
 if(r.val<min || r.val > max){ // wrong node, so fix it
   if(toFix != null) { // swap the nodes  
    int tmp = toFix.val; toFix.val=r.val; r.val=tmp;
   }
   else{ toFix = r; }
   fixSwappedBST(r.left, min..
 }
else{
  fixSwappedBST(r.left,  min, r.val,toFix);
  fixSwappedBST(r.right,r.val, max,toFix);
 }
}


Another approach:

Do a Pre-order traversal of the BST. It would be wrong at two places, identify those two positions in the Pre-order traversal. Identify the first element of the pair where it is out of order and the last element of the pair where it is again out of order.

In the next traversal, swap these two nodes. Would this work ??
Solution: http://www.geeksforgeeks.org/archives/23616
Reference: http://www.geeksforgeeks.org/archives/23088

Given a linked list containing 0s,1s or 2s. Sort it.

Given a linked list containing 0s,1s or 2s. Sort it.

Solution:
Maintain three different linked lists each having its own start pointer (LL0, LL1, LL2)  and keep adding the elements to the respective lists.
After the traversal you have three linkedlists (LL0, LL1 and LL2), now just join LL1 to the end of LL0 and LL2 to the end of LL1.

Another approach:
Keep three counters (c0,c1 and c2) and in the end reset the linked list elements as per the counters.

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

Recursive function to check a string for palindrome

boolean isPalindrome(String s){

  if(s.length()<=1) return true;

  if(s.charAt(0) == s.charAt(s.length()-1)) return isPalindrome(s.substring(1,s.length()-2));
  else return false;

}

Handling concurrency in a Web application

Reading: http://stackoverflow.com/questions/7455726/handling-the-concurrent-request-while-persisting-in-oracle-database

To handle concurrency in a web site a common practice it to have a column on each record that allows you to check it has not been updated since you got it. Either last update date or a sequential version number (auto incremented by a trigger).

Typically you will read the data (plus the concurrency column)

SELECT seat,etc,version_no
FROM t1
WHERE column = a_value

Then when the user eventually gets round to booking the seat the update will work unless there has been an update.

(the version number or update date will change after every update)

BEGIN
    UPDATE t1
    SET seatTaken = true
    WHERE seatid = .....
    AND version_no = p_version
    RETURNING version_no INTO p_version;
EXCEPTION WHEN NOT_FOUND THEN
    --Generate a custom exception 
    --concurrency viloation the record has been updated alreadyEND;

the trigger to auto update the version number would look a little like this

CREATE OR REPLACE TRIGGER t1_version
AFTER INSERT OR UPDATE ON t1
FOR EACH ROWBEGIN
    IF :new.version_no IS NULL THEN
       :new.version_no  := 0;
    ELSE
       :new.version_no  := :old.version_no  + 1;
    END IF;
END;

How to design a good API

From  a talk by Joshua Bloch: http://www.youtube.com/watch?v=aAb7hSCtvGw
Slides: http://lcsd05.cs.tamu.edu/slides/keynote.pdf

• API design is very similar to Language and language feature design.
• Easy to evolve, hard to misuse
• Gather requirements with healthy degree of skepticism. Define use cases from the requirements. Often it is easier and more rewarding to solve a more general form of problem than solving a specific problem so keep your mind open.
• Keep the initial spec of the API short/1 page. And discuss with as many people and then flesh it out as confidence builds.
• Write to the API (means write clients using API interface) as you design the API, this is very important as it allows you to explore the use cases API is being designed to solve.
• API should do ONE thing good.

Reading: http://www.artima.com/intv/blochP.html

State Design Pattern

Read the chapter on State design patterns from Head First Design Patterns book.

They explain the GumBallMachine, which can be in different states and needs to perform each action in a different way depending on the current state.

To start with they declare the action() methods in the GumBallMachine class only and in each action method they use if-else ladder to check the current state and take action based on the current state. And show how this type of state machine coding makes the action methods cluttered.

And in the next approach they make a State interface which has list of common action methods. And then there are concrete state classes for each state, which implement this interface and perform the actions() depending on the current state(i.e. the class for the state). This allows you to store the current_state object in the GumBallMachine class and call the state.action() methods inside this class. Depending on the current state the apt methods are called for each action(). This decouples each state from other states and makes adding new states easier.

Find the longest increasing subsequence

Its a DP problem:

Let L[j] be the length of the longest increasing sub sequence including jth array element.
=> L[i] = MAX(L[j]+1) for all (j<i)&&(a[j]<=a[i]).

O(n^2) solution.

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

Maximum size square sub-matrix with all 1s

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

Maximum Product Subarray

Given an array that contains both positive and negative integers, find the product of the maximum product subarray. Expected Time complexity is O(n) and only O(1) extra space can be used.


Solution: 
I. The solution that came to my mind first is to "Use a way similar to Kadane's algorithm for finding the maximum sum of a sub array.", but in this case the when (prd<0) we can't just discard it like we do it fro sum, bcoz a future -ve number might make this the highest product :P.
We would have to keep an integer storing the last_neg_num_prod to store the last -ve product upto a point and then set (prd=1).


public static void main(String[] args) {
int a[] = {-2, -3, 0, -2, -40};
int max= Integer.MIN_VALUE, last_neg_prod=0, prd= 1;
for(int i=0;i<a.length;i++){
prd = prd * a[i];
out:
if(prd<0){
if(last_neg_prod<0){ // we have an old -ve product, we can combine these to get a higher +ve product then
prd = prd*last_neg_prod;
last_neg_prod = 0;
break out;
}
last_neg_prod = prd;
prd = 1;
}
else if(prd ==0){
last_neg_prod = 0;
prd=1;
}
if(max<prd){
max = prd;
}
}

System.out.println("max prd is:"+max);


}



source: http://www.geeksforgeeks.org/archives/22216

KMP String searching algorithm

KMP is an algorithm to find the occurrence of string 'W' in another string 'S'.

1. Creates a partial match table T. T[i] stores the length of the longest proper suffix of W[0..(i-1)] which is a proper prefix of W.

How T is used in the main KMP algorithm:
At any given time, the algorithm is in a state determined by two integers, m and i, which denote respectively the position within S which is the beginning of a prospective match for W, and the index in W denoting the character currently under consideration.


T indicates where we need to look for the start of a new match in the event that the current one ends in a mismatch. The entries of T are constructed so that if we have a match starting at S[m] that fails when comparing S[m + i] to W[i], then the next possible match will start at index m + i - T[i] in S (that is, T[i] is the amount of "backtracking" we need to do after a mismatch).

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Efficiency_of_the_KMP_algorithm

Generate the list of ugly numbers

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

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

Co-joined Linked lists

You have two linked lists: A and B. A and B are co-joined at some node 'c'.

(A)--------
           (c) |------- (common part of both linked lists)
(B)--------

Find the the node (c) at which both the linked lists meet / collide.

Solution:

1. Traverse both the lists and find their lengths 'a' and 'b' respectively.
2. calculate the difference between both lengths: d = |a-b|
3. Make two pointers PA and PB for each list.
4. Move the pointer of the longer list 'd' steps.
5. Then move both the pointers simultaneously until both the pointers become equal, which happens at the node 'c'.

Find similarity between two arrays

There are two arrays.

int arr1[5] = { 3, 5, 2, 5, 2}
int arr2[5] = { 2, 3, 5, 5, 2}

The arrays will be called similar if they contain same number of elements equally.

Write the pseudo code to check this ?

I was not allowed to use sorting and hashtable.

Solution:

I.
Pick a random number from the array and partition it using the quick sort partition function.

Then partition the second array using the same number. O(n) time.

Now recursively, do this until the counts on either side mis-matches.

II.
Make two min heaps in O(n) time.
Extract the mins from both and compare till either both heaps are empty or there is a mismatch.

Reference: http://www.careercup.com/question?id=11685824

Using GDB to debug in linux

To debug a process: "./a.out arg1 arg2", run:

$ gdb ./a.out
(gdb) run arg1 arg2


Reading: http://cs.baylor.edu/~donahoo/tools/gdb/tutorial.html

Understanding the I/O redirection in linux

STDIN is FD 0, while STDOUT is FD 1, and STDERR is FD 2.

To redirect the errors to the output stream use this: 2>&1

Here '&' tells that it is a FD(file descriptor) and not an ordinary file named '1'.

There are lots of redirection symbols that you can use, and here are some of them:

< file	means open a file for reading and associate with STDIN.
<< token	Means use the current input stream as STDIN for the program until token is seen. We will ignore this one until we get to scripting.
> file	means open a file for writing and truncate it and associate it with STDOUT.
>> file	means open a file for writing and seek to the end and associate it with STDOUT. This is how you append to a file using a redirect.
n>&m	means redirect FD n to the same places as FD m. Eg, 2>&1 means send STDERR to the same place that STDOUT is going to.

Reading: http://www.linuxsa.org.au/tips/io-redirection.html

Find if number is a power of two, and returns it power

Solution:

'a' is power of two iff:  (a & (a-1) == 0).


To calculate the highest power 'a',

• iteratively shift the bits of a number to right
• increment a counter each time you shift right
• repeat above 2 steps until number > 0.
• 'counter' gives the value if the highest power.
• No. of loops = 32 ( width of the number)

Better solution:

To find more optimally one can make a lookup table, of say size 4, which stores the power of 2/(number of set bits) and then run the loop 32/4 = 8 times. 

Optimal Solution:

To optimize this even further we can use divide and conquer, at each step find the half of the 32 bit number which contains the set bit. And do this recursively. We need just 5 (= log 32) iterations in this method.

Reading: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog