csTechie

ArrayList
Pros
1. Find nth element in O(1)
2. Adding an element to end is O(1)
Cons
1. Deletion/Insertion at an arbitrary point in O(n)
2. Insertion to a sorted array is O(n)

Linked List
Pros
1. Insertion/Deletion is easy
2. For highly dynamic lists
Cons
1. Find nth element is O(n)

Most processor architectures, including IA32 and Sparc, have implemented a compare-and-swap (CAS) instruction.CAS(A,B) means “I think V should have the value A; if it does, put B there, otherwise don’t change it but tell me I was wrong.”. When multiple threads attempt to update the same variable simultaneously using CAS, one wins and updates the variable’s value, and the rest lose.

public class SimulatedCompareAndSwap {
    private int V;

    public synchronized int get() {
        return V;
    }

    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = V;
        if (oldValue == expectedValue)
            V = newValue;
        return oldValue;
    }

    public synchronized boolean compareAndSet(int expectedValue,
                                              int newValue) {
        return (expectedValue == compareAndSwap(expectedValue, newValue));
    }
}

A non-blocking counter can be implemented using CAS as below

public class NonBlockingCounter {
    private SimulatedCompareAndSwap value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        } while (v != value.compareAndSwap(v, v + 1));
        return v + 1;
    }
}

CAS-based counters significantly outperform lock-based counters if there is even a small amount of contention, and often even if there is no contention.
This used by the atomic variable classes (AtomicXxx in java.util.concurrent. atomic) to provide an efficient CAS operation on numeric and reference types; these atomic variable classes are used, directly or indirectly, to implement most of the classes in java.util.concurrent.

Implementation in AtomicInteger for incrementAndGet is as follows

    public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
    }

Source: http://www.amazon.com/dp/0321349601

  public static void findMinMax(int[]a)
  {
     int min = 99999;
     int max = -99999;
     int comp =0;
     for (int i = 0; i < a.length; i+=2)
     {
         int lmax,lmin;
         if(i+1==a.length)
         {
            lmax = a[i];
            lmin=a[i];
         }else{

           if(a[i] > a[i+1])
           {
              lmax=a[i];
              lmin=a[i+1];
           }else
           {
              lmax=a[i+1];
              lmin=a[i];
           }
         }
         if(max < lmax)max=lmax;
         if(min > lmin)min=lmin;

     }
     System.out.println("Max="+max+" Min="+min);

  }

public class QuickSort
{

  public static void swap(int[]a ,int i,int j)
  {
    int tmp = a[i];
    a[i]=a[j];
    a[j]=tmp;
  }

 // This logic will never give the location of the pivot element after the partition
  public static int partitionQuickSort(int[] a,int start,int end,int pivot)
  {
    int lo=start;
    int hi=end;
    int pivotVal = a[pivot];
    while(lo < = hi)
    {
      while(a[lo] < pivotVal)lo++;
      while(a[hi] > pivotVal)hi--;
      if(lo < = hi) {swap(a,lo,hi);
          lo++;
          hi--;
        }
    }
    return lo;
  }

  public static void quickSort(int[] inp,int start,int end)
  {
    if(start>=end)return;
    int mid = (start+end)/2;
    int loc = partitionQuickSort(inp,start,end,mid);
    if(loc-1 > start)    quickSort(inp,start,loc-1);
    if(end > loc)quickSort(inp,loc,end);
  }

    public static void printArray(int[] a)
  {
    for (int i = 0; i < a.length; i++)
    {
      System.out.print(a[i]+" ");
    }
    System.out.println();
  }

  /**
   *
   * @param args
   */
  public static void main(String[] args)
  {
    QuickSort quickSort = new QuickSort();
    int []inp = new int[]{9,8,5,6,2,2,2,2,3,4,7};
    quickSort(inp,0,inp.length-1);
    printArray(inp);
  }
}

  public static void  mirror(Node root)
  {
     if(root==null)return;
     Node left = root.left;
     mirror(root.left);
     mirror(root.right);
     root.left = root.right;
     root.right = left;
  }

  public static int getNthFibonacci(int n)
  {
    if(n==1)return 0;
    if(n==2)return 1;
    int a=0;
    int b=1;
    for (int i = 0; i < n-2 ; i++)
    {
       b = a+b;
       a = b -a;
      // System.out.println(b);
    }
    return b;
  }

class Activity implements Comparable
  {
    int start;
    int finish;

    public Activity(int x,int y)
    {
      start=x;
      finish=y;
    }

    public String toString()
    {
      return "[["+this.start+"-"+this.finish+"]]";
    }

    public int compareTo(Object obj)
    {
      Activity a = (Activity) obj;
      return this.finish - a.finish;
    }

  }

 public static ArrayList schedule(Activity [] list)
  {
    Arrays.sort(list);
    printActivityList(list);
    System.out.println();
    ArrayList ret = new ArrayList();
    ret.add(list[0]);
    int currentFinishTime = list[0].finish;
    for (int i = 1; i < list.length ; i++)
    {
       if(list[i].start > currentFinishTime)
       {
         //Add activity j to ret
         ret.add(list[i]);
         currentFinishTime = list[i].finish;
       }
    }
    return ret;
  }

   public static void printSpirally(int[][] a) {
        int N = a[0].length;
        for (int i = N - 1, j = 0; i > 0; i--, j++) {
            for (int k = j; k < i; k++)System.out.println(a[j][k]);
            for (int k = j; k < i; k++)System.out.println(a[k][i]);
            for (int k = i; k > j; k--)System.out.println(a[i][k]);
            for (int k = i; k > j; k--)System.out.println(a[k][j]);
        }
        int middle = (N / 2);
        if ((N % 2) == 1) {
            System.out.println(a[middle][middle]);
        }
    }

    public static boolean isVowel(char inp) {
        char c = Character.toUpperCase(inp);

        if ((c == 'A') || (c == 'E') || (c == 'I') || (c == 'O') || (c == 'U')) {
            return true;
        }

        return false;
    }

    public static void reverseVowels(char[] a) {
        int start = 0;
        int end = a.length - 1;

        while (start < end) {
            while ((start < a.length) && !isVowel(a[start])) {
                start++;
            }

            while ((end > 0) && !isVowel(a[end])) {
                end--;
            }

            if ((start > = end) || (start == a.length) || (end == -1)) {
                return;
            }

            //swap start and end;
            char t = a[start];
            a[start] = a[end];
            a[end] = t;
            start++;
            end--;
        }
    }

Print all nodes level by level

   public static void printlevelByLevel(Node root)
   {
      Node current = root;
      Queue q = new Queue();
      q.add(root);
      while(!q.isEmpty())
      {
        Node c =(Node) q.remove();
        System.out.print(c.val+",");
        if(c.left!=null)q.add(c.left);
        if(c.right!=null)q.add(c.right);
      }
   }

Print all nodes level by level and priting also when each level finishes

      public static void printlevelByLevel2Queues(Node root)
   {
      Node current = root;
      Queue q[] = new Queue[]{new Queue(),new Queue()};
      int currentQ=0;
      q[currentQ].add(root);
      while(!q[currentQ].isEmpty() || !q[1-currentQ].isEmpty() )
      {
        if(q[currentQ].isEmpty())
        {
          System.out.println("One level Finished... Switching queue...");
          currentQ = 1- currentQ;
        }
        Node c =(Node) q[currentQ].remove();
        System.out.print(c.val+",");
        if(c.left!=null)q[1-currentQ].add(c.left);
        if(c.right!=null)q[1-currentQ].add(c.right);
      }
   }