Friday 29 July 2016

plusout

Goto Problem

Given a string and a non-empty word string, return a version of the original String where all chars have been replaced by pluses ("+"), except for appearances of the word string which are preserved unchanged.

plusOut("12xy34", "xy") → "++xy++"
plusOut("12xy34", "1") → "1+++++"
plusOut("12xy34xyabcxy", "xy") → "++xy++xy+++xy"

public String plusOut(String str, String word)
 {
    String res="";
    int i=0;
    while(i<str.length())
    {
       if(str.substring(i).startsWith(word))
       {
           res=res+word;
           i=i+word.length();
       }
       else 
       {
          res=res+"+";i++;
       }
    }
    return res;
 }

Wednesday 27 July 2016

The HelloWorldThread

Multithreading is one of the most powerful features of Java. Also it is the hottest topic in the Java Interviews at some experience level or even for freshers.This is a must know topic for every Java Developer.In every thread related Java interview, the basic understanding of threads will be tested by asking the wait(),notify() and notifyAll() methods. In the following post, you will get a basic idea about them, followed by some basic interview questions related to them.
The Object class in Java has three final methods that allow threads to communicate about the locked status of a resource. These are :

wait() :It tells the calling thread to give up the lock and go to sleep until some other thread enters the same monitor and calls notify() or notifyAll(). It also has a parameterized version wait(long timeout) which can be used to to pass the amount of time the particular thread should wait before it kicks off again even if the notify() is not called.This method must be called from the synchronized block.If the current thread is interrupted while waiting, it will throw the InterruptedException

notify() : It will wake up a single thread on the monitor associated with the synchronized object. If multiple threads are waiting to acquire the lock, only one of them will be notified.However, the awakened thread will still not be able to execute until and unless the lock is released by this thread.

notifyAll() : Almost similar to notify() in many prospects.It will wake up all the threads that are waiting on the monitor associated with the synchronized object.However, if the awakened threads will try to get the lock on the object, only one thread will be given the lock and the rest of them will again go in the waiting state.The awakened threads will complete their execution in the usual manner.

One common characteristic among the three is that they will throw IllegalMonitorStateException if the current thread is not the owner of this object's monitor.

FAQs

Q. What happens to the lock when the wait method is called?
A. It releases the lock on the monitor.
Q. What is the difference between notify() and notifyAll()?
A. notify() wakes up only one of the threads waiting due to the monitor lock whereas notifyAll() wakes up all the threads.
Q. Can we some how control which thread to wake using notify()?
A. No,this can not be controlled.
Q. Why are these methods in Object class and not in Thread class?
A.Because these methods are used for locking which can be performed on objects and not threads. Apart from threads, these methods are the only way to communicate between the two objects.

Implementation of these methods

Write a Program that will start two threads. One thread will be used to print "Hello" and the other thread should print "World". This should be printed 5 times.

This problem can be treated as a classic Producer-Consumer problem. The HelloPrinter can be considered as Producer and the WorldPrinter can be considered as consumer.Both will take turns to do their job in a synchronized environment.

import java.util.concurrent.TimeUnit;

public class HelloWorldThread
{
 private int helloCount=0;
 private int worldCount=0;
 public final int totalCount=5;// 
 
 public static void main(String[] args) {

  HelloWorldThread hwt = new HelloWorldThread();
  //Sharing same object between threads
  Thread ht = new Thread(new HelloPrinter(hwt));
  Thread wt = new Thread(new WorldPrinter(hwt));

  ht.start();
  wt.start();
  
 }

 public int getHelloCount() {
  return helloCount;
 }

 public void setHelloCount(int helloCount) {
  this.helloCount = helloCount;
 }

 public int getWorldCount() {
  return worldCount;
 }

 public void setWorldCount(int worldCount) {
  this.worldCount = worldCount;
 }

}


class HelloPrinter implements Runnable
{

 HelloWorldThread hwt=null;

 public HelloPrinter(HelloWorldThread hwt) 
 {
  this.hwt=hwt;
 }
 @Override
 public void run() {
  try
  {
   synchronized (hwt) //Critical Section begins
   {
    int helloCount=0;
    while(hwt.getHelloCount() < hwt.totalCount)
    {
     if(hwt.getHelloCount()>hwt.getWorldCount())
     {
      hwt.wait();
     }
     helloCount++;
     System.out.print("Hello ");
     TimeUnit.MILLISECONDS.sleep(200);
     hwt.setHelloCount(helloCount);//Updating the count
     hwt.notify();
    }
   }
  }
  catch(InterruptedException e)
  {
   e.printStackTrace();
  }
 }
}

class WorldPrinter implements Runnable
{

 HelloWorldThread hwt=null;

 public WorldPrinter(HelloWorldThread hwt) 
 {
  this.hwt=hwt;
 }
 @Override
 public void run() {
  try
  {
   synchronized (hwt) //Critical Section begins
   {
    int worldCount=0;
    while(hwt.getWorldCount() < hwt.totalCount)
    {
     if(hwt.getHelloCount()==hwt.getWorldCount())
     {
      hwt.wait();
     }
     worldCount++;
     System.out.println("World!!");
     TimeUnit.SECONDS.sleep(1);
     hwt.setWorldCount(worldCount);//Updating the count
     hwt.notify();
    }
   }
  }
  catch(InterruptedException e)
  {
   e.printStackTrace();
  }
 }
}


Monday 25 July 2016

withoutString

Goto Problem

Given two strings, base and remove, return a version of the base string where all instances of the remove string have been removed (not case sensitive). You may assume that the remove string is length 1 or more. Remove only non-overlapping instances, so with "xxx" removing "xx" leaves "x".

withoutString("Hello there", "llo") → "He there"
withoutString("Hello there", "e") → "Hllo thr"
withoutString("Hello there", "x") → "Hello there"

public String withoutString(String base, String remove)
 {
      String res="";
      int i=0;
      while(i<=(base.length()-remove.length()))
       {
           if(base.substring(i,i+remove.length()).equalsIgnoreCase(remove))
           {
               i=i+remove.length();
               continue;
           }
            res=res+base.charAt(i);
            i++;
        }
        res=res+base.substring(i);
        return res;
  }

Sunday 24 July 2016

Forever Singleton

What is Singleton? or What are singleton classes? or What is Singleton Design Pattern. These are one of the most common interview questions asked in Java as some experience level.There are various methods by which one can implement singleton class depending upon the requirement. The implementation is fairly simple yet a lot of complexity is involved while working with singleton classes, specially in multi-threaded environment.Following are some of the common ways of making a class singleton.

Eager Initialization


public class EagerInitialization
{
        private static volatile EagerInitialization singleInstance = new EagerInitialization();

        // private constructor
        private EagerInitialization()
       {
        }

        public static EagerInitialization getInstance()
    {
                return singleInstance;
        }
}

This is the most simple way of creating a singleton class.The singleInstance of class is a static variable and will be initialized only once, as soon as the class is loaded in to the memory.Notice the private constructor of the class, which will prevent any other class from making the object. The only way to get the object of the EagerInitialization class is to call the public getInstance() method of the class.
 Despite the simplicity of this method, it is not preferred. The major pitfall of this method is that Instance is created irrespective of it is requirement at runtime. Now, there might be a possibility that this heavy instance might go unused throughout the application. If you can sleep on that, then this is the best approach.

Lazy Initialization


public final class LazyInitializationSingleton
{
        private static volatile LazyInitializationSingleton lazyInstance = null;

      // private constructor
     private LazyInitializationSingleton()
     {
     }
     public static LazyInitializationSingleton getInstance()
    {
       if (lazyInstance == null)
          {
             synchronized (LazyInitializationSingleton.class)
             {
                 lazyInstance = new LazyInitializationSingleton();
              }
            }
            return lazyInstance;
      }
 }

There are 3 take aways from this.

1. It solved the problem of Eager Initialization, it the object will be created only when it is required for the first time
2.The lazyInstance of the class is made volatile so as to avoid any caching related issues.
3. The object creation is done inside the synchronized block.
In this, on first invocation the object will be created and the same object will be returned in subsequent invocations.Although at first, this method seems to solve all the problems but it has its own drawback in multi-threaded environment.
Suppose there are two Threads, T1 and T2, and both check for the null condition at the same time. Since the lazyInstance will be null for both, they both will assume that object needs to be created and will enter the synchronized block sequentially and will create the object.

DoubleCheckSingleton


public class DoubleCheckSingleton
{
  private static volatile DoubleCheckSingleton instance = null;

  // private constructor
  private DoubleCheckSingleton()
  {
  }

  public static DoubleCheckSingleton getInstance()
  {
    if (instance == null)
      {
      synchronized (DoubleCheckSingleton.class)
    {
        // Double check
        if (instance == null)
        {
          instance = new DoubleCheckSingleton();
        }
      }
    }
    return instance;
  }
}

This is the correct implementation of singleton class.Re checking the instance for null inside the synchronized block makes this class thread safe singleton.

Bill pugh solution

This is my personal favorite method of making a class singleton.It uses the concept of static block initialization with the advantage of Lazy Initialization.

public class BillPughSingleton
{
// private constructor
 private BillPughSingleton()
  {
  }
  private static class LazyHolder
  {
    private static final BillPughSingleton INSTANCE = new BillPughSingleton();
  }

  public static BillPughSingleton getInstance()
  {
    return LazyHolder.INSTANCE;
  }
}

As you can see, the static inner class will be loaded on the first invocation of getInstance method. And on subsequent invocations, the same object will be returned from the static inner class.

Using Enum


We use enum to create a single object of the class. Enum, as written in java docs, provide implicit support for thread safety and only one instance is guaranteed. This is also a good way to have singleton with minimum effort.

public enum EnumSingleton
{
  INSTANCE;
 
}

Now, based on your requirement you can choose which implementation of Singleton suits the purpose.



countCode

Return the number of times that the string "code" appears anywhere in the given string, except we'll accept any letter for the 'd', so "cope" and "cooe" count.

countCode("aaacodebbb") → 1
countCode("codexxcode") → 2
countCode("cozexxcope") → 2

public int countCode(String str)
{
   int count =0;
    for(int i=0;i<str.length()-3;i++)
   {
      if(str.charAt(i)=='c' && str.charAt(i+1)=='o' && str.charAt(i+3)=='e')
      count++;
   }
  return count;
 }

Friday 22 July 2016

endOther

Goto Problem
Given two strings, return true if either of the strings appears at the very end of the other string, ignoring upper/lower case differences (in other words, the computation should not be "case sensitive"). Note: str.toLowerCase() returns the lowercase version of a string.

endOther("Hiabc", "abc") → true
endOther("AbC", "HiaBc") → true
endOther("abc", "abXabc") → true

public boolean endOther(String a, String b)
{
   String al=a.toLowerCase(),bl=b.toLowerCase();
   return(al.endsWith(bl) || bl.endsWith(al));
}

Tuesday 19 July 2016

xyBalance

Home

Goto Problem

We'll say that a String is xy-balanced if for all the 'x' chars in the string, there exists a 'y' char somewhere later in the string. So "xxy" is balanced, but "xyx" is not. One 'y' can balance multiple 'x's. Return true if the given string is xy-balanced.

xyBalance("aaxbby") → true
xyBalance("aaxbb") → false
xyBalance("yaaxbb") → false
public boolean xyBalance(String str)
{
 int i=0;
 boolean res=true;
 while(i<str.length())
 {
 if(str.charAt(i)=='x')
 {
  for(int j=i;j<str.length();j++)
  {
      if(str.charAt(j)=='y')
     {
        res=true;
        break;
      }
    else
         res=false;
  }
   }
 i++;
  }
 return res;
 }