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.

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.

import java.util.Stack;

class MyStack {

     Stack<Integer> stack1;

     Stack<Integer> stack2;

     /** MyStack constructor. */

     private MyStack() {

           this.stack1 = new Stack<Integer>();

           this.stack2 = new Stack<Integer>();

     }

     /** Return the instance of the stack. */

     public static MyStack getMyStackInstance() {

           return new MyStack();

     }

    

     /** Insert the element into the stack. */

     public int insert(int number) {

           int result = stack1.push(number);

           if(stack2.isEmpty() || stack2.peek()>number) {

                stack2.push(number);

           } else {

                int peek = stack2.peek();

                stack2.push(peek);

           }

           return result;

     }

     /** Delete the Top from the stack. */

     public boolean delete() {

           boolean result = false;

           if(!stack1.isEmpty()) {

                stack1.pop();

                stack2.pop();

           }

           return result;

     }

     /** Return the minimum element in the stack. */

     public int getMinimum() {

           int result = -1;

           if(!stack2.isEmpty()) {

                result = stack2.peek();

           }

           return result;

     }

}

public class StackOperations {

     /** Driver method. */

     public static void main(String[] args) {

           MyStack myStack = MyStack.getMyStackInstance();

           int number = 10;          

           myStack.insert(number);

           int min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

          

           number = 8;

           myStack.insert(number);

           min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

          

           number = 7;         

           myStack.insert(number);

           min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

          

           number = 14;        

           myStack.insert(number);

           min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

          

           number = 6;         

           myStack.insert(number);

           min = myStack.getMinimum();

           System.out.println("Minimum : "+min);

           myStack.delete();

           min = myStack.getMinimum();

           System.out.println("Minimumag after delete : "+min);

          

           myStack.delete();

           min = myStack.getMinimum();

           System.out.println("Minimumag after delete : "+min);

          

          

           myStack.delete();

           min = myStack.getMinimum();

           System.out.println("Minimumag after delete : "+min);

     }

} 

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

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.