Friday, 28 April 2017

String interning

String interning using intern() method

Java by default doesn't put all String object into String pool, instead, we have the flexibility to store any arbitrary String object in String pool explicitly.

java.lang.String.intern() method used to put String object to String pool.

String creation using String literal notation of Java is automatically called intern() method to put that object into String pool, provided it was not present in the pool already.

But in the case of new, interning doesn't happen automatically, until you call intern() method on that object.


Double quoted literal is known as String literal and the cache which stored these String instances are known as String pool.

    String a = "StringLiteral";
    String b = "StringLiteral";
    System.out.println(a == b);  // True
    String c = new String("StringHeap");
    String d = new String("StringHeap");
    System.out.println(c == d); // False a different reference!

    String e = "JDK";
    String f = new String("JDK").intern();
    System.out.println(e == f); //True :String moved to constant pool!


Points to remember:

String pool was located in the permgen area of heap up-to Java 1.6, but in Java 1.7 updates it’s moved to main heap area.

Earlier since it was in PermGen space, it was always a risk to create too many String object (java.lang.OutOfMemory: permgen space), because it’s a very limited space, default size 64 MB and used to store class metadata e.g. .class files.

Now because String pool is moved to a much larger memory space, it's much safer.

By the way, don't misuse memory here, always try to minimize temporary String object e.g. "a", "b" and then "ab". So don't forget to use StringBuffer and StringBuilder for string concatenation; it will reduce the number of temporary Object in String pool.

Compare two String object using equals() method and never compare them using == operator, because we never know which one is coming from the pool and which one is created using new() operator.


Perm space

Perm space is used to keep information for loaded classes and few other advanced features like String Pool, which usually get created by String.intern() methods.

PermGen Space speeds up our String equality searching.

As your application (number of classes) will grow this space shall get filled quickly, since the garbage collection on this Space is not much effective to clean up as required, you quickly get Out of Memory: perm gen space error. After then, no application shall run on that machine effectively even after having a huge empty JVM.

Thursday, 27 April 2017

Design a stack that supports getMinimum() in O(1) time

Problem statement:
Find the minimum element in a stack in O(1) time complexity and O(n) space complexity

Solution:
Maintain another stack and keep pushing the minimum element on the stack as in when found.
Before each push on stack 1, just check if the current element is less than the top element of the second stack if yes then push it on to stack 2.

While popping an element from stack1 check if the top of stack2 is same as the element in that case pop both the elements so that next minimum would show up on stack 2 for next min operation.

Inserts an element e1 to Stack.
push(int e1)
1) push e1 to the stack 1.
2) compare e1 with the top element(=e2) of the stack 2 (the auxiliary stack).
   a) If e1<e2, then push e1 to the auxiliary stack.
   b) If e1>e2, then push e2 to the auxiliary stack.

Removes an element from Stack and return the removed element.
int pop()
1) pop the top element from the auxiliary stack.
2) pop the top element from the actual stack and return it.

The step 1 is necessary to make sure that the auxiliary stack is also updated for future operations.

Returns the minimum element from Stack.
int getMinimum()
1) Return the top element of the auxiliary stack.

This would ensure that we pop out the minimum element in O(1) time.

Wednesday, 26 April 2017

Deadlock and Deadlock prevention

Deadlock occurs because:

Mutual exclusion: There is a resource which can be accessed only by one thread at any point in time.

Resource holding: While having locked one resource, the thread tries to acquire another lock on some other exclusive resource.

No preemption: there is any mechanism, which frees the resource if one thread holds the lock for a specific period of time.

Circular wait: During runtime a constellation occurs in which two (or more) threads are each waiting on the other thread to free a resource that it has locked.

Prevent deadlocks:

In order to prevent deadlocks one (or more) of the requirements for a deadlock has to be eliminated:

Mutual exclusion: In some situation it is possible to prevent mutual exclusion by using optimistic locking.

Resource holding: A thread may release all its exclusive locks, when it does not succeed in obtaining all exclusive locks.

No preemption: Using a time-out for an exclusive lock frees the lock after a given amount of time.

Circular wait: When all exclusive locks are obtained by all threads in the same sequence, no circular wait occurs.

Tuesday, 25 April 2017

Create Deadlock between two threads in Java

Deadlock describes a situation where two or more threads are blocked forever, waiting for each other.

Deadlock occurs because:

Mutual exclusion - Two processes cannot simultaneously control the same resource or be in their critical section.

Hold and Wait - processes currently holding resources can request new resources.

No preemption - Once a process holds a resource, it cannot be taken away by another process or the kernel.

Circular wait - Each process is waiting to obtain a resource which is held by another process.

Deadlocks in Java:
Deadlocks can occur in Java when the synchronized keyword causes the executing thread to block while waiting to get the lock, associated with the specified object. Since the thread might already hold locks associated with other objects, two threads could each be waiting for the other to release a lock. In such case, they will end up waiting forever.


Deadlock Example in java
 class Thread1 implements Runnable {
     public Object obj1;
     public Object obj2;
     public Thread1(Object obj1, Object obj2) {
           this.obj1 = obj1;
           this.obj2 = obj2;
     }

     public void run() {
           while(true) {
                synchronized (obj1) {
                     System.out.println("Thread1 : obj1");
                     synchronized (obj2) {
                           System.out.println("Thread1 : obj2");
                     }
                }
           }
     }
}

class Thread2 implements Runnable {
     public Object obj1;
     public Object obj2;
     public Thread2(Object obj1, Object obj2) {
           this.obj1 = obj1;
           this.obj2 = obj2;
     }
     public void run() {
           while(true) {
                synchronized (obj2) {
                     System.out.println("Thread2 : obj2");
                     synchronized (obj1) {
                           System.out.println("Thread2 : obj1");
                     }
                }
           }
     }
}

public class DeadLock {
     public static void main(String args[]) throws InterruptedException {
           Object obj1 = new Object();
           Object obj2 = new Object();

           Thread2 runn2 = new Thread2(obj1, obj2);
           Thread1 runn1 = new Thread1(obj1, obj2);

           Thread thrd2 = new Thread(runn2);
           Thread thrd1 = new Thread(runn1);

           thrd1.start();
           thrd2.start();

           while(!thrd2.isAlive() || !thrd1.isAlive()) {
                System.out.println("No deadlock found");
           }

     }
}

Saturday, 22 April 2017

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!!
Related Posts Plugin for WordPress, Blogger...