String compression

 public class Compress {  
      public static void compressStr(String str){  
           if(str == null || str.length() < 2){  
                return;  
           }  
           if(countCompression(str) >= str.length()){  
                System.out.println("Should not compress");  
                return;  
           }  
           char[] a = str.toCharArray();  
           int src = 1;  
           int dst = 0;  
           int count = 1;  
           while(src < a.length){  
                if(a[src-1] == a[src]){  
                     count++;  
                }else{  
                     System.out.println("The prev val is "+a[src-1]+" and next val is "+a[src]);  
                     a[dst++] = a[src-1];  
                     a[dst++] = (char) (count + '0');  
                     count = 1;  
                }  
                src++;  
           }  
           System.out.println("The src val is "+src+" and next val is "+count);  
           String compStr = new String(a, 0, dst);  
           compStr = compStr + str.charAt(a.length-1) + count;  
           System.out.println("The compressed str is "+compStr);  
      }  
      public static int countCompression(String str){  
           char[] a = str.toCharArray();  
           int src = 1;  
           int count = 1;  
           int size = 0;  
           while(src < a.length){  
                if(a[src-1] == a[src]){  
                     count++;  
                }else{  
                     size += 1 + String.valueOf(count).length();  
                     count = 1;  
                }  
                src++;  
           }  
           size += 1 + String.valueOf(count).length();  
           System.out.println("The compressed size is "+size);  
           return size;  
      }  
      public static void main(String args[]){  
           compressStr("aabbccccccc");  
      }  
 }  

This is to remove dups from a sorted int or char[]

 public class RemoveDups {  
      public static void removeDups(int[] a){  
           if(a == null || a.length < 2){  
                return;  
           }  
           int count = 1; //init to 1 to take care of last matching character  
           for(int i = 1; i < a.length; i++){  
                if(a[i-1] == a[i]){  
                     count++;  
                     if(count > a.length/2){  
                          System.out.println("The val "+a[i]);  
                          return;  
                     }  
                }else{  
                     count = 1;  
                }  
           }  
      }  
      public static void removeDupsStr(String str){  
           if(str == null || str.length() < 2){  
                return;  
           }  
           char a[] = str.toCharArray();  
           int src = 1;  
           int dst = 1;  
           while(src < a.length){  
                if(a[src-1] == a[src]){  
                     src++;  
                }else{  
                     a[dst] = a[src];  
                     dst++;  
                }  
           }  
           System.out.println("The str is "+new String(a,0,dst));  
      }  
      public static void removeDupsStringInN(String str){  
           if(str == null || str.length() < 2){  
                return;  
           }  
           char[] a= str.toCharArray();  
           boolean[] flag = new boolean[256];  
           for(int i = 0; i < flag.length; i++){  
                flag[i] = false;  
           }  
           int src = 0;  
           int dst = 0;  
           while(src < a.length){  
                if(!flag[a[src]]){  
                     a[dst] = a[src];  
                     dst++;  
                     flag[a[src]] = true;  
                }  
                src++;  
           }  
           System.out.println("The str is "+new String(a,0,dst));  
      }  
      public static void main(String args[]){  
           int a[] = { 1,1,1,1,3,3,3,3,3};  
           removeDups(a);  
           removeDupsStr("aaijsy");  
           removeDupsStringInN("sayaji");  
      }  
 }  

Longest Common Subsequence

 public class LCSequence {  
      public String lcs(String a, String b) {  
           int[][] lengths = new int[a.length()+1][b.length()+1];  
           // row 0 and column 0 are initialized to 0 already  
           for (int i = 0; i < a.length(); i++)  
                for (int j = 0; j < b.length(); j++)  
                     if (a.charAt(i) == b.charAt(j))  
                          lengths[i+1][j+1] = lengths[i][j] + 1;  
                     else  
                          lengths[i+1][j+1] =  
                          Math.max(lengths[i+1][j], lengths[i][j+1]);  
           // read the substring out from the matrix  
           StringBuffer sb = new StringBuffer();  
           for (int x = a.length(), y = b.length();  
                     x != 0 && y != 0; ) {  
                if (lengths[x][y] == lengths[x-1][y])  
                     x--;  
                else if (lengths[x][y] == lengths[x][y-1])  
                     y--;  
                else {  
                     if(a.charAt(x-1) == b.charAt(y-1)){  
                          sb.append(a.charAt(x-1));  
                          x--;  
                          y--;  
                     }  
                }  
           }  
           System.out.println("The DP table is: ");   
           for (int i=0; i<lengths.length; i++) {   
                for (int j=0; j<lengths[i].length; j++) {   
                     System.out.print(" " + lengths[i][j]);   
                }   
                System.out.println("");   
           }   
           return sb.reverse().toString();  
      }  
      public static void main(String args[]){   
           LCSequence m = new LCSequence();   
           System.out.println("The LCS is "+m.lcs("12","1122"));   
      }   
 }  

Why is string immutable in Java

1) Performance (string pooling)
2) thread safety ( we can pass around strings between threads and not worry about anyone changing it)
3) Security
http://geekexplains.blogspot.com/2009/11/why-string-has-been-made-immutable-in.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+GeekExplains+%28Geek+Explains%29

DataBase basics

1) Whenever an aggregate function is used with other field in query, a GROUP BY clause is required
     select name, avg(price) from products GROUP BY name

      if the aggregate function is used by itself then GROUP BY is not required
     select name from products

2) Select * from tables that are joined will give columns from both tables

3) Invalid use of aggregate function

SELECT *
  FROM DEPARTMENTS WHERE BUDGET > AVG(BUDGET)

Correct use is

SELECT *
  FROM DEPARTMENTS WHERE BUDGET > (SELECT AVG(BUDGET) FROM DEPARTMENTS)


1)Heap
2)Mergesort
3)quicksort
4)b tree
5)external sort
6)BFS
7)DFS
8)Hashing - file storage