Naïve String Matching Algorithm

It employs a Brute Force technique to identify the presence of a pattern in the given text.

It is not efficient algorithm because it takes the time complexity of the algorithm to check for a substring is O((m-n)n) where m is the length of the text and n is the length of the pattern (substring) to be searched.

There is no preprocessing is required for this algorithm, unlike KMP algorithm.

Preprocessing time: 0 (no preprocessing)

Matching time: O((n-m)m).

Pseudo Code:

NaiveStringMatcher(text, pattern)

tLen ← length [text]

pLen ← length [pattern]

for i ← 0 to tLen - pLen do

     mCount = 0;

for j ← 0 to pLen do

    if text[i] != pattern[j+i]

        break;

    mCount++;

     if(mCount == pLen)

           return Valid match found at position: + i!!

Implementation:

public class NaiveStringMatch {

      public static void main(String[] args) {

            String text = "I love to work on the algorithms!";

            String pattern = "the algorithms";

            naiveStringMatcher(text, pattern);

      }

      /**

       * Implementation of Naive String matching algorithm.

       * @param text

       * @param pattern

       */

      private static void naiveStringMatcher(String text, String pattern) {

            char[] txtArr = text.toCharArray();

            char[] patArr = pattern.toCharArray();

            int tLen = txtArr.length;

            int pLen = patArr.length;

            for (int i = 0; i < tLen - pLen; i++) {

               int charMatchCount = 0;

               for (int j = 0; j < pLen; j++) {

                    /**

                     * If pattern mismatch, break next searching point.

                     **/

                     if (patArr[j] != txtArr[i + j]) {

                          break;

                     }

                     charMatchCount++;

               }

               if (charMatchCount == pLen) {

                     print("String found at "+(i+1)+" position!!");

                     break;

               }

            }

      }

      private static void print(String string) {

            System.out.println(string);

      }

}

Output:

String found at 19 position!!

volatile is not always enough?

Even if the volatile keyword guarantees that all reads of a volatile variable are read directly from main memory, and all writes to a volatile variable are written directly to main memory, there are still situations where it is not enough to declare a variable volatile.

In fact, multiple threads could even be writing to a shared volatile variable, and still have the correct value stored in main memory, if the new value written to the variable does not depend on its previous value. In other words, if a thread writing a value to the shared volatile variable does not first need to read its value to figure out its next value.

As soon as a thread needs to first read the value of a volatile variable, and based on that value generate a new value for the shared volatile variable, a volatile variable is no longer enough to guarantee correct visibility. The short time gap in between the reading of the volatile variable and the writing of its new value creates a race condition where multiple threads might read the same value of the volatile variable, generate a new value for the variable, and when writing the value back to main memory - overwrite each other's values.

The situation where multiple threads are incrementing the same counter is exactly such a situation where a volatile variable is not enough.

Explain with an example:

Imagine if Thread 1 reads a shared counter variable with the value 0 into its CPU cache, increment it to 1 and not write the changed value back into main memory. Thread 2 could then read the same counter variable from main memory where the value of the variable is still 0, into its own CPU cache. Thread 2 could then also increment the counter to 1, and also not write it back to main memory.

                   

Thread 1 and Thread 2 are now practically out of sync. The real value of the shared counter variable should have been 2, but each of the threads has the value 1 for the variable in their CPU caches, and in main memory, the value is still 0. Even if the threads eventually write their value for the shared counter variable back to main memory, the value will be wrong.

When is volatile enough?

As I have mentioned earlier, if two threads are both reading and writing to a shared variable, then using the volatile keyword for that is not enough. You need to use a synchronized in that case to guarantee that the reading and writing of the variable is atomic. Reading or writing a volatile variable does not block threads reading or writing. For this to happen you must use the synchronized keyword around critical sections.

As an alternative to a synchronized block, we can use one of the many atomic data types found in the java.util.concurrent package (=AtomicLong, AtomicReference or one of the others).

In case only one thread reads and writes the value of a volatile variable and other threads only read the variable, then the reading threads are guaranteed to see the latest value written to the volatile variable. Without making the variable volatile, this would not be guaranteed.

The volatile keyword is guaranteed to work on 32 bit and 64 variables.

Java Serialization with Aggregation (HAS-A Relationship)

If a class has a reference to another class, all the references must be Serializable otherwise serialization process will not be performed. In such case, NotSerializableException is thrown at runtime.

Address.java

class Address { 

     String hNo,city,state; 

     public Address(String hNo, String city) { 

           this.hNo=hNo; 

           this.city=city; 

     } 

}

Employee.java

import java.io.Serializable; 

public class Employee implements Serializable { 

     int id; 

     String name; 

     Address address;//HAS-A 

     public Student(int id, String name) { 

           this.id = id; 

           this.name = name; 

     } 

} 

Since Address is not Serializable, we are getting NotSerializableException while serializing the instance of Employee class.

How to fix the Serialization in the case of Association?

Using the transient keyword:

In case the class refers to non-serializable objects and these objects should not be serialized, then, you can declare these objects as transient. Once a field of a class is declared as transient, then, it is ignored by the serializable runtime.

Using the static keyword:

In serialization, static variables are not serialized, so during deserialization, static variable value will load the class.

Make it a Serializable object:

All the objects within an object must be Serializable.

What is Thread Pool in Java and why we need it?

Java Thread pool represents a group of worker threads that are waiting for the job and reuse many times. Thread pool creates Thread and manages them. Instead of creating Thread and discarding them once task is done, thread-pool reuses threadsin form of worker thread.

In case of thread pool, a group of fixed size threads are created i.e. it also limits number of clients based upon how many thread per JVM is allowed, which is obviously a limited number. A thread from the thread pool is pulled out and assigned a job by the service provider. After completion of the job, thread is contained in the thread pool again.

Advantage of Java Thread Pool

Better performance, it saves time because there is no need to create new thread. The thread pool is one of essential facility any multi-threaded server side Java application requires. One example of using thread pool is creating a web server, which processes client request.

If only one thread is used to process client request, than it subsequently limit how many client can access server concurrently. In order to support large number of clients, you may decide to use one thread per request paradigm, in which each request is processed by separate Thread, but this require Thread to be created, when request arrived.  Since creation of Thread is time consuming process, it delays request processing.

Since Thread are usually created and pooled when application starts, your server can immediately start request processing, which can further improve server’s response time.

Real time usage

It is used in Servlet and JSP where container creates a thread pool to process the request.

Thread pools help us to better manage threads and decoupling task submission from execution. Thread pool and Executor framework introduced in Java 5 is an excellent thread pool provided by library.

Oracle queries for the rownum, rank to find the nth highest salary

Find the 2nd highest data in SQL:

SELECT MAX(balance) FROM mtx_wallet_balances WHERE balance NOT IN (SELECT MAX(balance) FROM mtx_wallet_balances )

SELECT MAX(balance) FROM mtx_wallet_balances WHERE balance <> (SELECT MAX(balance) FROM mtx_wallet_balances)

Find the nth highest data in Oracle using rownum:

select * from ( select mwb.*, row_number() over (order by balance DESC) rownumb from mtx_wallet_balances mwb ) where rownumb = 105;

Find the nth highest data in Oracle using RANK:

SELECT * FROM (SELECT balance, RANK () OVER (ORDER BY balance DESC) ranking FROM mtx_wallet_balances) WHERE ranking = 105;

Singleton using enum : Enforce the singleton property with a private constructor or an enum type

A singleton is simply a classthat is instantiated exactly once.

Before release 1.5, there were two ways to implement singletons. Both are based on keeping the constructor private and exporting a public static member to provide access to the sole instance.

In one approach, the member is a final field:

//   Singleton with public final field

public classSingleton {

     public static finalSingleton INSTANCE = new Singleton();

     private Singleton() { ... }

}

The private constructor is called only once, to initialize the public static final field Singleton.INSTANCE. Singleton instance will exist once the Singleton class is initialized—no more, no less. However a privileged client can invoke the private constructor using Reflection by AccessibleObject.setAccessiblemethod.

//Singleton with static factory

public classSingleton {

     private static finalSingleton INSTANCE = new Singleton();

     privateSingleton() { ... }

     public static Singleton getInstance() { return INSTANCE; }

}

To make a singleton class that is implemented using either of the previous approaches serializable, it is not sufficient merely to add implements Serializable to its declaration.

Each time a serialized instance is deserialized, a new instance will be created. To maintain the singleton guarantee, you have to declare all instance fields transient and provide a readResolve method.

//readResolve method to preserve singleton property

privateObject readResolve() {

     // Return the one true Singleton and let the garbage collector

     // take care of the Singleton impersonator.

     returnINSTANCE;

}

Singleton using enum:

As of release 1.5, there is a third approach to implementing singletons. This approach is functionally equivalent to the public field approach, except that it is more concise, provides the serialization machinery for free, and provides guarantee against multiple instantiation, even in the face of sophisticated serialization or reflection attacks.

Enum is thread-safe which helps us to avoid double checking(=less code for better results).

While this approach has yet to be widely adopted, a single-element enum type is the best way to implement a singleton.

public enumSingleton {

     INSTANCE;

     public voiddoStuff(){

           System.out.println("Singleton using Enum");

     }

}

And this can be called from clients:

public static voidmain(String[] args) {

     Singleton.INSTANCE.doStuff();

}