Looping ArrayList

Here are the three ways to loop through the ArrayList.

import java.util.*;
import java.lang.*;

class Rextester
{ 
    public static void main(String args[])
    {
        List<Integer> list = new ArrayList<Integer>();
        list.add(10);
        list.add(20);
       
        for(int i=0;i<list.size();i++)
        {
            System.out.println(list.get(i));
        }
       
        for(Integer num : list)
        {
            System.out.println(num);
        }
       
        Iterator<Integer> it = list.iterator();
        while(it.hasNext())
        {
            System.out.println(it.next());
        }
    }
}

ArrayList Vs Vector

1) Synchronization: ArrayList is non-synchronized which means multiple threads can work on ArrayList at the same time. For e.g. if one thread is performing an add operation on ArrayList, there can be an another thread performing remove operation on ArrayList at the same time in a multithreaded environment
while Vector is synchronized. This means if one thread is working on Vector, no other thread can get a hold of it. Unlike ArrayList, only one thread can perform an operation on vector at a time.
2) Resize: Both ArrayList and Vector can grow and shrink dynamically to maintain the optimal use of storage, however the way they resized is different. ArrayList grow by half of its size when resized while Vector doubles the size of itself by default when grows.
3) Performance: ArrayList gives better performance as it is non-synchronized. Vector operations gives poor performance as they are thread-safe, the thread which works on Vector gets a lock on it which makes other thread wait till the lock is released.
4) fail-fast: First let me explain what is fail-fast: If the collection (ArrayList, vector etc) gets structurally modified by any means, except the add or remove methods of iterator, after creation of iterator then the iterator will throw ConcurrentModificationException. Structural modification refers to the addition or deletion of elements from the collection.
As per the Vector javadoc the Enumeration returned by Vector is not fail-fast. On the other side the iterator and listIterator returned by ArrayList are fail-fast.
5) Who belongs to collection framework really? The vector was not the part of collection framework, it has been included in collections later. It can be considered as Legacy code. There is nothing about Vector which List collection cannot do. Therefore Vector should be avoided. If there is a need of thread-safe operation make ArrayList synchronized as discussed in the next section of this post or use CopyOnWriteArrayList which is a thread-safe variant of ArrayList.
There are few similarities between these classes which are as follows:

1. Both Vector and ArrayList use growable array data structure.
2. The iterator and listIterator returned by these classes (Vector and ArrayList) are fail-fast.
3. They both are ordered collection classes as they maintain the elements insertion order.
4. Vector & ArrayList both allows duplicate and null values.
5. They both grows and shrinks automatically when overflow and deletion happens.

When to use ArrayList and when to use vector?

It totally depends on the requirement. If there is a need to perform “thread-safe” operation the vector is your best bet as it ensures that only one thread access the collection at a time.
Performance: Synchronized operations consumes more time compared to non-synchronized ones so if there is no need for thread safe operation, ArrayList is a better choice as performance will be improved because of the concurrent processes.
How to make ArrayList synchronized?
As I stated above ArrayList methods are non-synchronized but still if there is a need you can make them synchronized like this –

//Use Collecions.synzhonizedList method
List list = Collections.synchronizedList(new ArrayList());
...

//If you wanna use iterator on the synchronized list, use it
//like this. It should be in synchronized block.
synchronized (list) {
  Iterator iterator = list.iterator();
  while (iterator.hasNext())
      ...
      iterator.next();
      ...
}

This content is from : http://beginnersbook.com/2013/12/difference-between-arraylist-and-vector-in-java/ 

ArrayList Vs LinkedList

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).
Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.
2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).
Conclusion: LinkedList element deletion is faster compared to ArrayList.
Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.
3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. Reason is same as explained for remove.
4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes hence the memory consumption is high in LinkedList comparatively.
There are few similarities between these classes which are as follows:

1. Both ArrayList and LinkedList are implementation of List interface.
2. They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
3. Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method.
4. The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException).

When to use LinkedList and when to use ArrayList?

1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.
2) Search (get method) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

Got this information from : http://beginnersbook.com/2013/12/difference-between-arraylist-and-linkedlist-in-java/

Interface Vs Abstract Class

Abstract class Interface 1) Abstract class can have abstract and non-abstract methods. Interface can have only abstract methods. 2) Abstract class doesn't support multiple inheritance. Interface supports multiple inheritance. 3) Abstract class can have final, non-final, static and non-static variables. Interface has only static and final variables. 4) Abstract class can have static methods, main method and constructor. Interface can't have static methods, main method or constructor. 5) Abstract class can provide the implementation of interface. Interface can't provide the implementation of abstract class. 6) The abstract keyword is used to declare abstract class. The interface keyword is used to declare interface. 7) Example: public class Shape{ public abstract void draw(); } Example: public interface Drawable{ void draw(); }

Comparable Vs Comparator

Comparable :

 Comparable is implemented by a class in order to be able to comparing object of itself with some other objects. The class itself must implement the interface in order to be able to compare its instance(s). The method required for implementation is compareTo().

Comparator:

In some situations, you may not want to change a class and make it comparable. In such cases, Comparator can be used if you want to compare objects based on certain attributes/fields. For example, 2 persons can be compared based on `height` or `age` etc. (this can not be done using comparable.)
The method required to implement is compare(). Now let's use another way to compare those TV by size. One common use of Comparator is sorting. Both Collections and Arrays classes provide a sort method which use a Comparator.

In brief, a class that implements Comparable will be comparable, which means it instances can be compared with each other.
A class that implements Comparator will be used in mainly two situations: 1) It can be passed to a sort method, such as Collections.sort() or Arrays.sort(), to allow precise control over the sort order and 2) It can also be used to control the order of certain data structures, such as sorted sets (e.g. TreeSet) or sorted maps (e.g., TreeMap).

Example :

class Dog implements Comparator<Dog>, Comparable<Dog>{
   private String name;
   private int age;
   Dog(){
   }

   Dog(String n, int a){
      name = n;
      age = a;
   }

   public String getDogName(){
      return name;
   }

   public int getDogAge(){
      return age;
   }

   // Overriding the compareTo method
   public int compareTo(Dog d){
      return (this.name).compareTo(d.name);
   }

   // Overriding the compare method to sort the age 
   public int compare(Dog d, Dog d1){
      return d.age - d1.age;
   }
}

public class Example{

   public static void main(String args[]){
      // Takes a list o Dog objects
      List<Dog> list = new ArrayList<Dog>();

      list.add(new Dog("Shaggy",3));
      list.add(new Dog("Lacy",2));
      list.add(new Dog("Roger",10));
      list.add(new Dog("Tommy",4));
      list.add(new Dog("Tammy",1));
      Collections.sort(list);// Sorts the array list

      for(Dog a: list)//printing the sorted list of names
         System.out.print(a.getDogName() + ", ");

      // Sorts the array list using comparator
      Collections.sort(list, new Dog());
      System.out.println(" ");
      for(Dog a: list)//printing the sorted list of ages
         System.out.print(a.getDogName() +"  : "+
   a.getDogAge() + ", ");
   }
}

Parameter	Comparable	Comparator
Sorting logic	Sorting logic must be in same class whose objects are being sorted. Hence this is called natural ordering of objects	Sorting logic is in separate class. Hence we can write different sorting based on different attributes of objects to be sorted. E.g. Sorting using id,name etc.
Implementation	Class whose objects to be sorted must implement this interface.e.g Country class needs to implement comparable to collection of country object by id	Class whose objects to be sorted do not need to implement this interface.Some other class can implement this interface. E.g.-CountrySortByIdComparator class can implement Comparator interface to sort collection of country object by id
Sorting method	int compareTo(Object o1) This method compares this object with o1 object and returns  a integer.Its value has following meaning 1. positive – this object is greater than o1 2. zero – this object equals to o1 3. negative – this object is less than o1	int compare(Object o1,Object o2) This method compares o1 and o2 objects. and returns  a integer.Its value has following meaning. 1. positive – o1 is greater than o2 2. zero – o1 equals to o2 3. negative – o1 is less than o1
Calling method	Collections.sort(List) Here objects will be sorted on the basis of CompareTo method	Collections.sort(List, Comparator) Here objects will be sorted on the basis of Compare method in Comparator
Package	Java.lang.Comparable	Java.util.Comparator

 More info at : Click Here

 

Java Fail-Fast Vs Fail Safe

Here is a very good explanation on Fail-Fast Vs Fail Safe:  Click Here

Knapsack problem

Given n object with each with some weight and associated value. Find out the maximum value of knapsack if multiple objects with same weight are allowed.

Ex: Value = { 60,100,200}
      Weight = {10,20,30}


The idea is to start with the smallest weight and find out the total value of the knapsack for that and then continue with the next weight and consider the maximum value of either current object by adding the previous object value and the weight.



int _tmain(int argc, _TCHAR* argv[])
{
    int v[]={60,100,200};
    int w[]={15,20,30};

    int key = 50;

    int n;
   
    std::cout<<"Enter sum value :\n";
    std::cin>>n;
    int *sum;
    sum= new int[50];

    sum[0]=0; //base, coins to make a sum of zero.
    for(int i = w[0];i<=50;i++)
    {
        sum[i] = 0;
        for(int j=1;j<=3 ;j++)
        {
           
            if(w[j-1]<=i)
            {
                // Consider the case when you add two units and the value is more than the current unit   weight.
                sum[i] = v[j-1] + sum[i-w[j-1]] > v[j] ? v[j-1] + sum[i-w[j-1]] : v[j];
               
            }
        }
    }
    std::cout<<" Total value of kanpsack of weight "<< n << " is :"<<sum[n-1]<<std::endl;
}

Derive only from a particular class

Here is the sample code that throws compile time error message if you try to derive from the non-drivable class.

// DerivedFromParticularClass.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <assert.h>
#include <iostream>
using namespace std;
class Cloneable
{
};
class DerivedFromCloneable:public Cloneable
{
};
class NotDerivedFromCloneable
{
};

template <typename D,typename B>
class IsDervivedFrom {
public:
    //method:1
    class No {};
    class Yes { No arr[3]; };
    static Yes test(B*){ }
    static No test(...) {}
    ///
    static void Constraints(D* pd)
    {
        B* pb = pd;
    }
    IsDervivedFrom()
    {

        cout<<sizeof(test(static_cast<D*>(0)));
        void (*p)(D*) = Constraints;
    }
    enum { Is= sizeof(test( static_cast<D*>(0) )) == sizeof(Yes)  };
};
template <typename T >
class Sample :public IsDervivedFrom <T,Cloneable>
{

};


int _tmain(int argc, _TCHAR* argv[])
{
    Sample <DerivedFromCloneable> p_obj;
    Sample <NotDerivedFromCloneable> f_obj;   //ERROR
    IsDervivedFrom<DerivedFromCloneable,Cloneable> Y;
   
   
    assert(Y.Is);

    return 0;
}

Size Of Array Using Templates

Here is the sample program that help us compute the size of the array.

Arpproach 1:

template<typename T, int size>

size_t asz(T (&)[size]) { return size; }

int _tmain(int argc, _TCHAR* argv[])

{

int a[12], b[20];

const int sz1 = asz(a);

const int sz2 = asz(b);

return 0;

}

How is this working?

int asz(T (&)[size]) { return size; }

The parameter to asz function is the un-named reference parameter of size elements.

When asz(a) is called, basically we are passing the type as int which maps to template parameter 'T' and array is mapped to the un-named reference parameter with size elements as compiler internally pass the size to the method. That's why when we return we get the exact size of the array.

We can simple find out the size of the array using sizeof(arr)/sizeof(type). but it wont work in most of the cases where arr is not of pointer type.

Approach 2:

int size = (&arr)[1] - arr;

arr and &arr  both points to the address of the array. But when we do &arr[1],

it points to the last element of the array where as arr[1] points to first element 

of the array.

Assume arr is of int with 5 elements. If you do address/pointer arithmetic it 

basically jumps by its type(5 int) bytes.

Minimum Number of steps to reach the end in an array

Problem :

We have an array A[ ] where each element A[ i ] specifies the maximum number of jumps we can move forward from that position, we need to  find the
minimum number of jumps to reach the end of the array from the begining .

Solution :
We can solve this problem in multiple approaches. Here i am going to provide solution in greedy and dynamic programming model.

In greedy approach we find the maximum value to maximize the jump. In dynamic programming approach we compute the minimum number of hops required to reach each element and use these values for computing the result.

 Using  Dynamic programming ,this can be solved b y finding the minimum number of steps to reach the n-1 position and then checking for the minimum of {jumps[i],jumps[j]+1} where
j ranges from 0-i and also satisfies the formula i-j <= A[j].

Assume we have a array sequence {1, 2, 1,1,4,6,2,0,8}

Assume we are processing A[2]=1 and we need to find the minimum no of jumps to reach A[4]=4

Now the formula will not be satisfies as to reach A[4] we need to have a value of A[j] which can be used to fill the gap from i to j that (i-j).  So it has to satisfy (i-j)<=A[j].

Jumps[i] = Min { Jumps[i], Jumps[j] + 1}

C++ Code:

#include "stdafx.h"
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
int _tmain(int argc, _TCHAR* argv[])
{
    int a[]={1,2,3,1,1,5,0,8};

    int n;
    int *JP;
    //std::cout<<"Enter sum value :\n";
    //std::cin>>n;
    JP= new int[8];

    JP[0]=0; //base, to jump to position 0.
    for(int i = 1;i<8;i++)
    {
        //Set maximum for a position of i.
        JP[i] = INT_MAX;
        //For each postion, check the no of ways to reach using the previous postion values.
        //And select the lowest in each run.
        int count = 0;
        for(int j=0;j<i ;j++)
        {
          
            if(a[j]>=(i-j))
            {
                count++;
                if(JP[i] >JP[j]+1)
                {
                    JP[i] = JP[j]+1;
                  
                }
            }
          
        }
        std::cout<<" Number of ways to reach position "<< a[i] << " is :"<<count<<" Min hops :"<<JP[i]<<std::endl;
    }
    std::cout<<" Min Number of hops to reach the end of the array is :"<<JP[7]<<std::endl;
}

Java Code :

 public class FindMinimumHops {
   
    public static void main(String args[])
    {
        int [] array = {2,3,1,1,4};
        System.out.println("Minimum number of hops to reach end is:"+findMinHopsUsingGreedy(array));       
        System.out.println("Minimum number of hops to reach end is:"+findMinHopsUsingDP(array));
    }

    private static int findMinHopsUsingGreedy(int[] array) {
        int maxHops = 0;
        int currentIndex = 0;
        int max = 0;
        int location = 0;
        while (currentIndex < array.length) {
            maxHops++;
            max = 0;
            for (int ctr = currentIndex + 1; ctr <= currentIndex
                    + array[currentIndex]; ctr++) {
                if (max < array[ctr]) {
                    max = array[ctr];
                    location = ctr;
                }
            }
            currentIndex += location;
        }
        return maxHops;
    }

    private static int findMinHopsUsingDP(int[] array) {
        int []dp = new int[array.length];
        dp[0] = 0;
        for(int i = 1; i < array.length; i++)
        {
            dp[i] = Integer.MAX_VALUE;
            for(int j= 0; j < i ; j++ )
                if( ( i-j ) <= array[j] )
                    dp[i] = Math.min(dp[i], dp[j]+1);
        }
       
        return dp[array.length - 1];
    }

}

Thanks to Gopal for sharing the Java Code.