Count no of String occurences in single pass

package com.prac;

import java.util.*;

public class CountStringOccurences 
{
public static void main(String[] args) {

String[] str = {"A","B","C","A","A","B","B","B","B","B","C","A","D","E","E","F","D","D"};

Map<String, Integer> hm = new HashMap<String, Integer>();

int cnt=1;

for(String ans : str)
{
if(hm.containsKey(ans))  //check if the key is already present
{
 cnt=hm.get(ans); // if present then fetch its count and increment it
 cnt++;
}
else
{
   cnt=1; //else set count to 1
}

     hm.put(ans, cnt);  // add the data in map
}


System.out.println("hm="+hm);
}
}


Output:
hm={D=3, E=2, F=1, A=4, B=6, C=2}

Find first non-repeating character in String

Following code finds the first non-repeating character in just one pass :)


public class NonRepeating{

public static char firstNonRepeatingChar(String word)
{
Set<Character> repeating = new HashSet<Character>();
List<Character> nonRepeating = new ArrayList<Character>();

for (int i = 0; i < word.length(); i++)
{
char letter = word.charAt(i);
if (repeating.contains(letter))
{
continue;
}

if (nonRepeating.contains(letter))
{
nonRepeating.remove((Character) letter);
        repeating.add(letter);
}
else
{
nonRepeating.add(letter);
}
}

if(nonRepeating.size()!=0)
 return nonRepeating.get(0);
else
  return '\0';
}


public static void main(String[] args)
{
char ans = firstNonRepeatingChar("hrishikesh");

System.out.println("ans="+ans);
}
}

Fibonacci Series

Fibonacci Series = 0 1 1 2 3 5 8 13 21 34.

Basically we have to add the previous and current number to get the next number.


Java Code->
public class Fibonacci
{
    static int[] fibonacci(int n)
    {
     //Declare an array to store Fibonacci numbers
     int f[] = new int[n+1];
     int i;
   
     //0th and 1st number of the series are 0 and 1
     f[0] = 0;
     f[1] = 1;
   
     for (i = 2; i <= n; i++)
     {
    //Add the previous 2 numbers in the series and store it
        f[i] = f[i-1] + f[i-2];
     }
   
      return f; //Return the array back to main method.
    }

 
   public static void main(String[] args)
   {
     int n = 9;
     int[] ans = fibonacci(n);
 
     for (int i = 0; i <= n; i++)
     {
        System.out.print(ans[i]+" "); //Print the array.
     }
   }

}

Pair Programming

In Pair Programming two programmers work together on the same computer.

One person writes the code while the other reviews it. They also switch their roles frequently.

Both have to maintain a running commentary, basically they have to "program out loud".

Multiple configuration files

Hibernate is designed to be used with a large set of databases. The details of those databases are configured in an XML file called hibernate.cfg.xml.

If we wish to use multiple databases in our application then we have to maintain separate configuration files.


Example: Application uses Oracle and Derby database.

Here we have to maintain 2 configuration files, lets say we name it oracleconfig.cfg.xml and derbyconfig.cfg.xml.

To access them we need to create separate session Factories ->

1) SessionFactory sessionFactory1 = new  Configuration().configure("oracleconfig.cfg.xml").buildSessionFactory();

2) SessionFactory sessionFactory2 = new Configuration().configure("derbyconfig.cfg.xml").buildSessionFactory();

Space Complexity

Usually the term Space Complexity is misused for Auxiliary Space.

Following are the correct definitions of Auxiliary Space and Space Complexity.

Auxiliary Space is the temporary space used by an algorithm.

Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size.

Space complexity includes both Auxiliary space and space used by input.

Example:
While comparing sorting algorithms on the basis of space, Auxiliary Space would be a better choice than Space Complexity.

Analysis of Loops - Calculating Time Complexity

1) O(1): Time complexity of a function is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function.

swap() function or loop or recursion that runs a constant number of timeshas O(1) time complexity.

Example:

for (int i = 1; i <= c; i++) {  // Here c is a constant   
        // some expressions
 }


2) O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount.

Example:

for (int i = 1; i <= n; i += c) {   // Here c is a constant  
        // some expressions
}


3) O(n2) : Time complexity of nested loops is equal to the number of times the innermost statement is executed. Selection sort and Insertion Sort have O(n2)  time complexity.

Example:

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some expressions
       }
 }



4) O(Logn): Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount. Binary Search has O(Logn) time complexity.

for (int i = 1; i <=n; i *= c) {
       // some expressions
}



5) O(LogLogn): Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.
 
for (int i = 2; i <=n; i = pow(i, c)) {  // Here c is a constant greater than 1   
       // some O(1) expressions
}
 

How to combine time complexities of consecutive loops?
When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.

for (int i = 1; i <=m; i += c) {  
        // some expressions
}

for (int i = 1; i <=n; i += c) {
        // some expressions
}

Time complexity of above code is O(m) + O(n) which is O(m+n)
If m == n, the time complexity becomes O(2n) which is O(n).  


How to calculate time complexity when there are many if, else statements inside loops?
Worst case time complexity is the most useful among best, average and worst. Therefore we need to consider worst case.

We evaluate the situation when values in if-else conditions cause maximum number of statements to be executed.

For example consider the linear search function where we consider the case when element is present at the end or not present at all.

When the code is too complex to consider all if-else cases, we can get an upper bound by ignoring if else and other complex control statements.

Asymptotic Notations - Theta , Big O and Omega

Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis.

The following 3 asymptotic notations are mostly used to represent time complexity of algorithms.


1) Θ Notation: The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior.

A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants.

Example:
3n3 + 6n2 + 6000 = Θ(n3)

Dropping lower order terms is always fine because there will always be a n0 after which Θ(n3) beats Θn2) irrespective of the constants involved.



2) Big O Notation: The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.

Example: Consider the case of Insertion Sort.

It takes linear time in best case and quadratic time in worst case. We can safely say that the time complexity of Insertion sort is O(n^2).

If we use Θ notation to represent time complexity of Insertion sort, we have to use two statements for best and worst cases:
1. Worst case time complexity = Θ(n^2).
2. Best case time complexity = Θ(n).

The Big O notation is useful when we only have upper bound on time complexity of an algorithm. Many times we easily find an upper bound by simply looking at the algorithm.



3) Ω Notation: Just as Big O notation provides an asymptotic upper bound on a function, Ω notation provides an asymptotic lower bound.

Ω Notation can be useful when we have lower bound on time complexity of an algorithm.

The best case performance of an algorithm is generally not useful, the Omega notation is the least used notation among all three.

Example: Consider the case of Insertion Sort.

The time complexity of Insertion Sort can be written as Ω(n), but it is not a very useful information about insertion sort, as we are generally interested in worst case and sometimes in average case.

Worst, Average and Best Case in Algorithms

Lets take an example of Linear Search and analyze it using Asymptotic analysis.

We can have three cases to analyze an algorithm:
1) Worst Case
2) Average Case
3) Best Case


Worst Case Analysis (Usually Done)
In this, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched is not present in the array. When the element is not present, search() functions compares it with all the elements of array one by one.

Therefore, the worst case time complexity of linear search would be Θ(n).


Average Case Analysis (Sometimes done) 
In this, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of element not being present in the array).

So we sum all the cases and divide the sum by (n+1).


Best Case Analysis (Bogus) 
In this, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when the element is present at the first location.

So time complexity in the best case would be Θ(1)

Analysis of Algorithms - Asymptotic Analysis

Algorithm: An algorithm is step by step instructions to solve a given problem.


Why performance analysis?
There are many important things that should be taken care of, like user friendliness, modularity, security, maintainability, etc. Why to worry about performance?

Evaluation of an algorithm is required to find the most optimized solution for solving a given problem.

For example:
While travelling from Place A to Place B one needs to select the best mode of transport (Flight, Train , Bus etc) based upon the budget and urgency.


Given two algorithms for a task, how to find which one is better?
One way is – implement both the algorithms and run the two programs on your computer for different inputs and see which one takes less time. There are many problems with this approach.
1) It might be possible that for some inputs, first algorithm performs better than the second  and vice versa.
2) Also for some inputs, first algorithm might perform better on one machine and the second works better on other machine for some other inputs.


Asymptotic Analysis is the big idea that handles above issues in analyzing algorithms. In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (we don’t measure the actual running time). We calculate, how does the time (or space) taken by an algorithm increase with the input size.

For example: Searching a given item in a sorted array. 
There are 2 ways - Linear and Binary search.

To understand how Asymptotic Analysis solves the above mentioned problems in analyzing algorithms, let us say we run the Linear Search on a fast computer and Binary Search on a slow computer. For small values of input array size, the fast computer may take less time. But, after certain value of input array size, the Binary Search will definitely start taking less time compared to the Linear Search even though the Binary Search is being run on a slow machine.

The reason is the order of growth of Binary Search is logarithmic while that of Linear Search is linear. So the machine dependent constants can always be ignored after certain values of input size.


Does Asymptotic Analysis always work?
Asymptotic Analysis is not perfect, but that’s the best way available for analyzing algorithms.

Internal working of HashSet

Set is a collection that contains no duplicate elements. So, it can contain at most one null.
HashSet implements Set interface in java. It is not synchronized and is not thread safe.

Example: Showing HashSet does not allow duplicate elements.

public class Test {
   public static void main(String[] args) throws IOException {
        HashSet hashSet = new HashSet();
        hashSet.add(20);
        hashSet.add("Test");
        hashSet.add("XYZ");
        hashSet.add(20);
        hashSet.add("Test");
        System.out.println("Set = "+hashSet);
   }
}


Output:
Set = [20, Test, XYZ]


Internal Working:
Internally when the duplicate elements are passed to the HashSet, the add(e) method in HashSet returns false when the element exists, else it returns true.

When we have a look at the HashSet.java in java API, we can see the following code:

public class HashSet extends AbstractSet implements Set, Cloneable, java.io.Serializable
{
    private transient HashMap<E,Object> map; 

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    /**
    * Some code
    */
}

Set achieves the uniqueness in its elements through HashMap. In HashMap, each key is unique. So, when an object of HashSet is created, it will create an object of HashMap.

When an element is passed to Set, it is added as a key in the HashMap in the add(Element e) method. Now, a value needs to be associated to the key. Java uses a Dummy value (new Object) which is called PRESENT in HashSet.

In HashMap, the put(Key k,Value V) method returns null, if the key is unique and the key gets added to the map. It returns old value of the key, if the key is duplicated.

public V put(K key, V value) {
/* Some code */
}

In add(e) method, the return value of map.put(key,value) method is checked with null value.

public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

If map.put(key,value) returns null, then map.put(e, PRESENT)==null will return true and element gets added to the HashSet.

If map.put(key,value) returns the old value of the key, then map.put(e, PRESENT)==null will return false and element wont be added to the HashSet.

remove() method also works in the same way.

public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
}

As you know HashSet uses same values for all keys, it is really important to override equals() and hashCode() for any object you are going to store in HashSet thus making the object Immutable.