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

Recovery Mode without grub

 1)After start booting : Ctrl + Alt + F1 --> Recovery Mode
 2)To reboot from terminal : sudo reboot

Tomcat - java.lang.OutOfMemoryError: PermGen space problem

When i run tomcat, sometimes i got JVM out of memory. This is due to insufficient tomcat memory allocated.

Solution
Steps :
1)Open catalina.sh in specific tomcat. tomcat/bin/catalina.sh
2)add in JAVA_OPTS value: -server -Xms512m -Xmx1024m -XX:NewSize=256m -XX:MaxNewSize=256m -XX:PermSize=256m -XX:MaxPermSize=256m -XX:+DisableExplicitGC
3)Restart tomcat again

For more you can refer Here