Java Multi Threading : Wait/ Notify/ NotifyAll

Lets say bunch of Readers wants to read updated Value of certain Resource, which is going to be updated by Writer. Then how Reader knows that Resource Fields have been updated by Writer.

Therefore to Synchronize such cases between Readers and Writers on common resource, three final methods of Object class have been used.

1. wait()
2. notify()
3. notifyAll()

Wait : Readers wants to read updated value of resource, they register with resource object i.e when update happens on same object and when Writer notify it, readers will try to acquire lock on resource and read the updated resource.

• Wait only being invoked when Reader have Lock Object, here in our case it is resource.
• Once wait method is called, Reader releases the Lock Object.
•  Now Only for the same registered Object(resource) Reader will get notification signals.
• If Reader invokes wait on Object, which is different from Object Writer used for sending notification, Reader will never gets the notification signal.
• Once Reader(s) are notified, now Reader(s) will try to content for the Lock(one of them gets the lock) read the updated value of resource. Similarly other Readers also gets turn to acquire lock and read the updated value.
• Once Reader read the updated value, perform there Business Logic and come out from Synchronized Block, Reader will release the lock so that other Readers can acquire it. 

Notify: Writer enters the Synchronized Block, after acquiring lock performs his Business Logic, 

update the resource Object, once resource Object is updated it will notify the waiting threads(Readers) whom are waiting on same Lock.

• Notify signals only one waiting Thread, which is decided by underlying Java Thread Manager
• Once Writer signals notify(), then it doesn't means Reader rushed immediately to read the updates values. Firstly writer must release the Lock, which it will do once it comes out of Synchronized block.Once Lock is being released and waiting threads are notified, then [In case of notify()] notified Thread will acquire the Lock[Released by Writer] and then enter the Synchronized Block and completes from where he left[i.e statements after wait()].

Notify-All: In notifyAll, all threads who are registered with resource lock, will get the notifications.

• Once notifyAll() is triggered, all threads waiting on same lock will get the signal and are ready in contention to acquire the lock.
• Once Writer finishes its Job and release the Lock, Any one Reader will acquire the lock[which Thread, again decided by underlying Java Thread Manager Implementation].
• Once the Reader gets the Lock, it will enter in Synchronized Block, where he left[i.e after wait() method] performs it tasks and on completing the Synchronized Block releases the Lock. 
• Now Other remaining Threads will try to acquire the Lock, anyone of them will get it, enters synchronized block, completes its task and then release the Lock.
• This process will keep on till all Registered Readers complete there Job.

   ----------------------------------------------------------------------------------------------------------------

Now we will see the Code for it. Also we will discuss the Code also. :

Basic Overview Of code : It consists of Three classes 

1. Resource Class : On which Lock will be acquired and wait() and notify(), notifyAll() will be invoked.
2. ReaderTask : Implements Runnable interface, implies readers jobs, wants to read updated Value of resource object.
3. WriterTask : Implements Runnable interface, implies writer jobs, will update the resource object and notify registered waiting threads.
4. Demo Class: which will create Let say 3 Readers and 1 Writer Thread, Bind Respective Tasks to them and start the threads.

-----------------------------------------------------------------------------------------------------------

Resource.java

   public class Resource {

  private String mesg;

  

          public void setMesg(String mesg){

 this.mesg =mesg;

  }

  public String getMesg(){

 return this.mesg;

  }

    }

------------------------------------------------------------------------------------------------

WaitThreadTask.java

public class WaitThreadTask implements Runnable {

private Resource resource;

public WaitThreadTask(Resource resource){

this.resource = resource;

}

@Override

public void run() {

// TODO Auto-generated method stub

synchronized(resource){

System.out.println("Before Reading Updated Value By : " +Thread.currentThread().getName() );

//We need to Take care to get the updated value, so waiting for writer thread to update value.

try {

//Release resource Lock & wait till any notification from Writer.

resource.wait();

System.out.println("Waiting is Over For : "+ Thread.currentThread().getName());

} catch (InterruptedException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

//Read Updated Value

System.out.println("Updated Value of Resource Mesg :" + resource.getMesg() + " Read By :" +Thread.currentThread().getName());

}

}

}

-----------------------------------------------------------------------------------------------------------------

WriterThreadTask.java

public class WriterThreadTask implements Runnable{

private Resource resource;

public WriterThreadTask(Resource resource){

this.resource = resource;

}

@Override

public void run() {

// TODO Auto-generated method stub

synchronized(resource){

System.out.println("Before Updating Resource By : " + Thread.currentThread().getName());

//Updating resource Object Message

resource.setMesg("Hi How are You !!!");

resource.notify();

//resource.notifyAll();

//Once Writer Comes Out from Synch Block, Readers will Content to read the values.

System.out.println("Task Done By Writer Thread.");

}

}

}

----------------------------------------------------------------------------------------------------------------------

ThreadDemo.java

public class ThreadDemo {

public static void main(String args[]){

//Create Single Resource Object, which can act as Lock on Writer and Readers.

Resource lock = new Resource();

//Three Readers and One Writer runnable Tasks.

Runnable taskR1 = new WaitThreadTask(lock);

Runnable taskR2 = new WaitThreadTask(lock);

Runnable taskR3 = new WaitThreadTask(lock);

Runnable taskW1 = new WriterThreadTask(lock);

Thread t1 = new Thread(taskR1, "Reader1");

Thread t2 = new Thread(taskR2, "Reader2");

Thread t3 = new Thread(taskR3, "Reader3");

Thread t4 = new Thread(taskW1, "Writer1");

t1.start();

t2.start();

t3.start();

/*try{

Thread.sleep(5000);

} catch(InterruptedException e){

e.printStackTrace();

}*/

t4.start();

}

}

---------------------------------------------------------------------------------------------------------------------

Code Observations :

1. Both notify()/notifyAll() and wait() : works only on the Lock Objects they already acquire. For example : Synchornized(ObjectA) {......// ... // ObjectB.wait() or ObjectB.notify() or ObjectB.notifyAll() ...} then It will throw IllegalMonitorStateException. Therefore care must be taken that lock must be acquired before calling any of above three methods with same lock.Even If you simply write notify() or wait() or notifyAll(), then still it will throw IllegalMonitorStateException because [It suggest lock must be acquired on this Object, again which is not the case].
2. Reader will only able to receive signals on which same notification is send. If wait is happening on Object which is different from Object on which notification is being send, then Readers will never get the notification and hence they will wait forever.
3. Readers which are registered before Writer able to send the notification, Only those readers will get it. Because if Writer sends notification first, before reader registered to Object, they will not receive the signals as Signals are already being missed : Missed Signals 
4. Reader and Writer should acquire Lock on same Object and should invoke wait/notification signals on same Object. If the above code is modified as, instead of using resource for locks and wait and notify, If we use this. What will happen ? Well .. All readers will wait forever, Because readers registered with different Objects of WaitThreadTask and writer notify on WriterThreadTask. Therefore none of the Reader will receive notification signals, as they registered to receive signals on respective WaitThreadTask Object and not on WriterThreadTask Object.

       

NoClassDefinationFound Explained !!

The above Exception occurs when the intended class is not found in the Class Path.
At Compile Time Class : Class was generated from Java Compiler, But Somehow
at Run Time the Dependent Class is not found.

Lets go through one Simple Example :

public class ClassA{
    public static void main(String args[]){
         //Some gibberish Code...
         String text = ClassB.getString();
         System.out.println("Text is :" + text);
    }
}

public class ClassB{

  public static String getString(){
         return "Testing Some Exception";
     }
}


Now Lets assume that the above two Java Source Code are placed in some Folder let say "NoClassDefinationFoundExceptionDemo"

Now open a shell(Assuming Java is already being setup correctly)
1)Go to Folder "NoClassDefinationFoundExceptionDemo"
2)Compile Java Source Files
     javac ClassB
     javac ClassA
3)Both Files are Compiled Sucessfully and generated Class files in the same Folder
   as ClassA.class and ClassB.class
4)Now Since we are overiding ClassPath to current working directory
    therefore we execute the following command
    java -cp . ClassA
    and It worked Successfully and you will see the Output in the screen
5)Now Lets say, You removed  ClassB.class file from Present Directory.
   and now you execute the command again.
   java -cp . ClassA
  Now it will greet you with NoClassDefFoundException. as ClassB which is a dependency
  for ClassA is not found in the classpath(i.e present working directory).

Test Pyramid

From the Testing Pyramid Notes :
1)Unit Tests : It should be the building blocks of the tests. Any method, which is doing something non trivial should be the included as a part of unit Test.These tests should be in the same platform where development is done. Developers should take care of writing these tests, as they know what they have developed.
2)UI Tests : UI tests involves lots of setup and execution. Now what happens is let say I have created one Simple Calculator application, and If i test my Sum functionality from UI, it involves lots of Happenings like we will be testing : whether input parameters are properly shown, Button is clicked , output is shown as desired etc.Now here the problem is very simple : We are coupling Service Testing (Sum functionality) with UI, which is really time consuming, plus UI automation is handling multiple responsibilities, apart from UI[presentation testing] we are also testing services {which is really bad}.Plus it will consume whole lot Of effort and Time, because each time input fields are populated then invoke the Service and then check for desired Output. Instead Of it, Just remove Service Testing from UI automation, In service check for all cases where service can work or broke,
 and then For UI just write Automation for Presentation part, to test whether UI is pretty good as per desired and your functionality is working end to end.
3)Service Tests: Where you will tests for services which you are exposing to UI or End Users.

Number Game :

Unit Tests: Since Unit tests are showing whether your code is working in Bits and Pieces.Any method, Class, Module which you find is important and Holding some non Trivial Business Logic, should be the part Of Unit Tests.These Tests should be maximum in Number, because it penetrates all your non important functionality.Quantity of Unit Tests will be much higher since you are covering almost all your Code.So candidates for Unit Testing are much High.
Service Tests : These are the API's or we can say services provided to End User so that they can consume it, Now Candidates for Service Testing are all services which you are exposing to End User to Use Them. So we can say these are not very high but intermediate in number.
UI Tests : Since UI keeps on changing so writing Tests for displays in UI is not much useful and could be Time Consuming, Instead of it UI Testing are good at Testing Navigation Flow and some important Presentation part, So this is the least bothered stuff to Test.


Thats why we have pyramid like structure :
1)On Top is UI[Low Priority, Less Useful, Keeps on Changing no need to put too much effort on That]
2)Then Service Layer [Medium Priority or important priority, since it projects your Business Flow, Again needs to tested thoroughly]
3)Unit Tests[Most important, needs to test your code in Bits and Pieces, plus bugs or any issue can be caught very early, Developers are mostly responsible to write it, to test their own Code].

Introduction To Generics

The main Idea behind Generics is to pass Type parameter along with Implementation Itself.
Ex:
   method(Integer x){
//...
   }
   this method only accepts Integer param.
 
   Now let say If we need to create Our Method Generic enough that users of method can pass types also.
   Something like :
   method(T x){
   //...
   }
   Now here T depends on User type.
   Let say :
   User #1
       Integer x = new Integer(5);
  method(x);
User #2
String y = new String("abc");
method(y);

So our method is generic enough to consume any Input Argument Type.
    We will discuss this appraoch more .
    The Other approach is for method to have Object type input parameter.
    method(Object x){
     //...
    }
Now this approach is good to certain extend.
Observations :
a)Since all non primitive types are subclass to Object, so client with non-primitive types can easily use method.
 Integer x = new Integer(5);
 method(x);

 String y = new String("abc");
 method(y);

 Both these will work like a charm.
b)Problem arises when storing elements in collection of any Type just like List<Object>
      Let say we have method :
      methodList(){
   List strList = new ArrayList();
strList.add("abc");
strList.add("def");
//Lets assume list has two elements.
Iterator iter = list.iterator();
while (iter.hasNext()) {
String str = (String)iter.next(); //We need to explicitly Downcast, Since List will return Object element.
System.out.println(str);
}
//Now we need to add one more element, which is Integer.
Integer ints = new Integer(5);
strList.add(ints);
//If we do
String str = (String) strList.get(2);
//This will throw ClassCastException : which means element is getting casted to incompatible Type and throw ClassCastException at RunTime.
}
    So, Upcasting is Implicit, Because all non Primitive types are Subclasses Of Object.which can be done easily.
    But in case of Downcasting, Programmer needs to take care of when to Downcast and Correct Type to Downcast.
3)We can use instance Of while doing downcast, but again its a too much to do that.
 Maintaining each type and its associated if-else condition is too much to do.
    4)Generics helps us to avoid such problems :
      ==> Developer don't need to do the BookKeeping of Downcast, whenever he is retrieving elements from some Global Structure like List, method(Object ) etc.
          Casting problems are traced at Compile Time and not at RunTime, Thanks to Generics from Java5 and above.
      ==>Generics are mainly used to Use Collections easily, without Type Errors etc. Since Collections are used to store ant Type of Elements, and Generics are
    there to provide Type Safety Stuff.
      ==>With Generics you can write Generic Code and User Of your Code provide Specific Type.
         Ex:
            <T> void printList(List<T> list){
for(T ele : list){
System.out.println(ele);
}
}

Now user Of printList, will use it like
List<Integer> ints  = new ArrayList<Integer>();
ints.add(1);ints.add(2);ints.add(3);

Now user Of printList, will use it like
List<String> ints  = new ArrayList<String>();
ints.add("abc");ints.add("xyz");ints.add("def");

So in both cases, we as don't need to handle different Types separately.
and our printList code is generic enough, not to get changed with different Types List from Consumer.

  

Lowest Common Ancestor in Binary Tree(not necessary to be BST)..

Bottom Up Approach:


Explanation :

We traverse the tree only once .. and find out the LCA.Intuition is : 1)First of all we need to traverse the whole tree.Hence any traversing techniue needs to be implemented.[here we are using postorder, because we needs to make decesion based on values calculated.]
    So we added :
        LCA(root.left,p,q);
        LCA(root.right,p,q);
    Now we need certain Inits: if root == null : return null;
            if(root is any of p or q) : return root.
                It means we have reached one of our target node.

2)Decision Block : Since we are returning from bottom to top, after calculations...
    So three cases arises :
        -->Either we found one of our node
        -->Not found one of our node.
        -->Found both nodes
        If we don't find one of our node then  return null;
        But if we found one of our node ... then we need to return that node to its parent.   
        If we found both nodes (then return its root)..Since we are coming from bottom to top, so the first node found having both nodes is our result.


So our code have :

    --> Inits
    --> Traverse Block
    --> Decesion Block. [Why we have written decesion block in last place? Beacuse to make decisions you need to know the values of left subtree and right subtree.]


Ex:

    Let say we have a tree :

        a
        /\                    Let p = f; and q = o       
        b c
        /\ /\
        d e f g
          /\  /
          m n o


For simplicity :
    Lets take a simple tree
        a
        /\
        b c

and p = b, q = c; 
 How our algo proceeds : at A: then goto left subtree and return null||p||q, right subtree and return null||p||q.
    b is returned from leftsubtree and c from right subtree, and root of that will be our LCA


another Example :
        a
        /\            p = d and q = c
        b c
        /\
        d e

    AT A : leftSubtree --> B. then again left subtree... -->D ..return D.
        Now at B... Right sub tree -->At E ...returns null ... since other node is not found.
        So at B value is D.
        Now go to A right subtree .. -->C: return C
        So we have A left Subtree returns D and right subtree returns C..
            SO intuitevely this is the first node, which have p i left subtree and q in right subtree or vice versa.
                          So this is the LCA.

another example :

        a
        /\
        b c                p = m, q= f
        /\ /\
        e f g h
        /\
        m n
   

  We start at A: left subtree -->B -->E -->M since we got M --> so return value to E's left subtree
        E(leftSubtree) = M;
        Now we go to right subtree of E: we found no f ..
        E(right subtree) = null;
        Now non null value is returned to B left subtree value..
        SO B(left subtree) = M.
        Now we calculate B (right subtree)-->We have found 'F'
        So B (right subtree value) = F.
        Hence we return B as LCA   



another example:
        if in previous figure : p=m, q=b
        i.e one node is parent(direct/indirect) of other node ...

        Again as usual, we start at A --> left subtree -->B, now since B is found we return B
            So A(left subtree) = B;[We skipped traversing B childrens]
        Now go to A right subtree -- > we traverse through C and its children an we are unbale to find 'M'--> so it returns null
            So A(right subtree) = M;
        We go to decesion block where we found that non null value should be returned.Hence LCA = B.which is correct.


Time Complexity: Since this algo requires only traversing of tree, So complexity is O(n).
Space Complexity : If tree is balanced then Logn recursive calls and needs to store those on stack.But in worst case it is O(n).




Final Code :

    return : node type
    arguments : root,p,q
    So signature of method : public node LCA(node root, node p, node q)


    Code:

        public node LCA(node root, node p, node q){

        //Inits :
            if(root == null || p == null || q == null)
                return null;
            else if(root == p)
                return p;
            else if(root == q)
                return q;
            else{
                //Traversals
                node L = LCA(root.left,p,q);
                node R = LCA(root.right,p,q)'
                //Decision Code
                if(L != null && R != null)
                    return root; //First node from bottom whose Left and right subtree contains p and q.
                else if(L != null && R== null)
                    return L;
                else if(L == null && R != null)
                    return R;
                else
                    return null;
            }
               
        }
                   
           

Why Suffix Tree and not Prefix Tree.

To find a pattern we need to find sub string in a text.Since Tries can also find sub string, but there is a catch since they find the sub strings with well defined start and end delimiter.
For ex : Suppose I need to search for a word in a text "bull". Then Trie can do it in O(m) time. But let say we need to find pattern such as "l bid be" now it is a sub-string, but it doesn't have a well defined delimiters starting and ending.
So Basically tries doesn't solve our problem for pattern search.It can find string with well defined boundaries, but not sub string with delimiters.Now this has obvious applications in finding some patterns in Human Gnome.
Like :
"ADCNDJCDNCD CNDJCNDNCDXXCAVDA CDNJCDNCD HBADSCD"
Now if I need to find  "CDNCD HBA" then tries can't do this. Since they stores words and not sub strings.
                                  
Therefore we need some other data structures which can do this.

Firstly our requirement is :
a)We need searching like Tries, means searching of sub string should be done in time proportional to the length of the pattern.
b)Instead of storing individual words in a Trie, we can store either Prefixes or Suffixes of the text(not of the words). Since by this way we can catch the patterns (i.e sub strings) other than individual words.

Now why prefixes or suffixes ?
Since to find sub strings, we must require to search in prefixes or suffixes of text. What it really means is ?
First lets look at Sub string definition.
We can define sub string in two ways:
 -->A prefix of some suffix.
 -->A suffix of some prefix.

For ex :
I have some Text as :
 "abcde h"
 Firstly we must find its prefixes :
  "a"
  "ab"
 "abc"
"abcd"
"abcde"
"abcde h"
Now to find a sub string/pattern let say : "de h"
This sub string must be a suffix of some prefix.
Here in our example it is suffix of last prefix.

Similarly for our other definition of sub string :
We calculate suffixes :
 "h"
" h"
"e h"
"de h"
"cde h"
"bcde h"
"abcde h"
Now to find substring "cde ". It must be  prefix of some suffix.
Here in our case it is prefix of suffix "cde h"

So from this we mean : if we store prefixes or suffixes of the text. We can easily search for a sub string (even without delimiters).

So our next step is :
Create a Trie of prefixes or suffixes of text.

Now our next question is Does Trie of prefixes really do our job?

Logically it seems that we don't require Trie of prefixes.
Since our main concern is the starting delimiter of the sub string.Because if we create a prefix tree, from where we should start our search for pattern.Since our Trie of prefixes always starts with prefixes.Now in order to find intermediate sub string like "cde h", we are not able start the Trie traversal from root of the Trie.
  There are two ways to deal with this problem :
 -->Either create a prefix tree and make some techniques to start traversal from bottom-up.Now this seems to be inappropriate , with some complex traversing from bottom to top,while also to make our Data structure to remain as Trie.
-->Or create a Trie of suffixes.
    Now this will solve our problem, because we will get our starting point from the top of the Trie and match till our sub string length.

So in short we will create a Trie , storing suffixes of entire Text(not individual words).

Shell and Linear Algebra blogs

Some links which are useful to explore for beginners.

Bash Scripting : AboutLinux
Awk One Liner : here
Linear Algebra :here
Unix One Liner :here
Node.js :here