Friday, 27 December 2013

The Mean, Median & Mode Revisited

Problem:


Given a 2 sorted array find mean, median & mode

Solution:


1) Two Sorted arrays can be merged in O(n) time.
2) Calculating mean is simple i.e.
        a) calculate k = summission of mergedarray[i]
        b) do k/mergearray.length
        c) display k as mean value
3) Calculating Median
        a) In case total no of element is ODD, int m = mergedarray.length/2, then display m as median value
        b) In case total no of element is EVEN, int m = mergedarray.length/2,
            int val = (mergedarray[m]+mergedarray[--m])/2
            display val as median
4) Calculating Mode is simple i.e.
     -- find number which  occurs max number of times.

Code:

     
import java.util.ArrayList;


public class MyDS {

 int[] no,count;
 int ptr = 0;
 public MyDS(int n) {
  no = new int[n];
  count = new int[n];
 }
 
 public void add(int val, int occ) {
  no[ptr] = val;
  count[ptr] = occ;
  ptr++;
 }
 
 public ArrayList getModeValue() {
  int max = 0,z=0;
  ArrayList k = new ArrayList();
  for (int i = 0; i < count.length; i++) {
   if( count[i] > max) {
    max = count[i];
    z = i;
   }
  }
  k.add(no[z] + " " + max);
  for (int i = 0; i < count.length; i++) {
   if( count[i] == max && z != i ) {
    if(!k.contains(no[i] + " " + max))
    k.add(no[i] + " " + max);
   }
  }
  return k;
 }
 
 

}



import java.util.ArrayList;

public class Merge2SortedArray {

 int arr1[],arr2[],farr[];
 int ptr1,ptr2,fptr;
 
 void init(int[] a, int[] b ) {
  arr1 = a;
  arr2 = b;
  farr = new int[arr1.length+arr2.length];
  merge();
 }
 
 private void merge() {
  // TODO Auto-generated method stub
  /**
   * while-loop to tackle merging of sorted arrays of unequal length
   * for-loop is ok for merging equal length sorted array.
   * 
   */
  while (ptr1 <= arr1.length || ptr2 <= arr2.length) {
   if(arr1[ptr1] < arr2[ptr2]) {
    farr[fptr] = arr1[ptr1];
    fptr++;
    ptr1++;
   }else if( arr2[ptr2] < arr1[ptr1] ) {
    farr[fptr] = arr2[ptr2];
    fptr++;
    ptr2++;
   }else {
    farr[fptr] = arr1[ptr1];
    fptr++;
    farr[fptr] = arr1[ptr1];
    fptr++;
    ptr1++;
    ptr2++;
   }
   if(ptr1 >= arr1.length) {
    copyArr2();
    break;
   }else if( ptr2 >= arr2.length) {
    copyArr1();
    break;
   }
  }

  median();
  mean();
  MyDS ds = new MyDS(farr.length);
  
  for (int i = 0; i < c; i++) {
   int occurence = mode(farr[i]);
   ds.add(farr[i],occurence);
  }
  
  displayMode(ds);
 }

 private void displayMode(MyDS ds) {
  // TODO Auto-generated method stub
  ArrayList modeValue = ds.getModeValue();
  System.out.println("And the mode value is ");
  for (String string : modeValue) {
   System.out.println(string);
  }
 }

 private int mode(int k) {
  // TODO Auto-generated method stub
  int z = 0;
  for (int i = 0; i < c; i++) {
   if(farr[i] == k)
    z++;
  }
  return z;
 }

 private void mean() {
  // TODO Auto-generated method stub
  int sum =0;
  for (int i = 0; i < c; i++) {
   sum += farr[i];
  }
  System.out.println("And mean is " + sum/c);
 }
 
 int c = 0;
 private void median() {
  // TODO Auto-generated method stub
  
  for (int k : farr) {
   if(k != 0) {
    System.out.print(k + " ");
    c++;
   }
  }
  
  System.out.println("\n" + "And the median is ");
  
  if((c%2)==0) {
   int med = c/2;
   avgingMideans(med,--med);
  } else
   System.out.println(farr[((c+1)/2)-1]);
 }

 private void avgingMideans(int c2, int c3) {
  // TODO Auto-generated method stub
  int k = (farr[c2]+farr[c3])/2;
  System.out.println(k);
 }

 private void copyArr1() {
  // TODO Auto-generated method stub
  for (int i = ptr1; i < arr1.length; i++) {
   farr[fptr] = arr1[i];
   fptr++;
  }
 }

 private void copyArr2() {
  // TODO Auto-generated method stub
  for (int i = ptr2; i < arr2.length; i++) {
   farr[fptr] = arr2[i];
   fptr++;
  }
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int[] a = {6,6};
  int[] b = {2,4};
  new Merge2SortedArray().init(a  ,b);
 }
}
GOOD LUCK!  Merry Christmas & Happy New Year !!

Sunday, 22 December 2013

Break The Integer

Problem:


Given an integer n, break it in smallest non-repeating subsets.

Eg 1: 5
1 1 1 1 1
2 1 1 1
3 1 1
4 1
5

Eg 2: 10
1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1
4 1 1 1 1 1 1
5 1 1 1 1 1
6 1 1 1 1
7 1 1 1
8 1 1
2 2 2 2 2
3 3 3 1
4 4 2
5 5
6 4
7 3
8 2
9 1
10


Time Complexity (for main logic):


n + n + n + n (for 4 loops)
i.e. 4n
i.e. O(n)

O(n) extra space.

Code:



public class SplitTheInteger {

 private int userInput;
 int[] temp;

 void start( int no ) {
  
  userInput = no;
  temp = new int[userInput];
  
  for (int i = 0; i < userInput; i++) {
   temp[i] = 1;
  }
  
  int len = userInput-1;
  
  /**
   * its working for userinput 5
   * 1 1  1  1  1
   * 2 1  1  1 -1
   * 3 1  1 -1 -1
   * 
   * 4 1 -1 -1 -1 //this is taken care by for
                 *  
                 * loop below while loop so to avoid redundancy i have 
   * made 'no-1'
   * 
   * 5
   */
  while (temp[0] != no-1 ) {
   algo();
   temp[0]++;
   temp[len] = -1;
   len--;
   
  }
  
  for (int i = 2; i <= userInput; i++) {
   /**
    * Suppose i = 3
    * UserInput = 10
    * 10/3 = 3
    * so print 3 three times and call done which will select 
    * such a number that will sum up UserInput i.e. 10
    */
   int m = userInput/i;
   int count = 0;
   while ( count != m ) {
    System.out.print( i + " ");
    count++;
   }
   if(i*count != userInput)
    done(count*i);
   System.out.println();
  }
  

  
 }
 
 
 private void algo() {
  // TODO Auto-generated method stub
  int z = temp[0];
  for (int k : temp) {
   if( k != -1)
    System.out.print(k + " ");
  }
  System.out.println();
  
    
 }


 private void done(int i) {
  // TODO Auto-generated method stub
  for (int j = 1; j <= userInput; j++) {
   if(j+i == userInput) {
    System.out.print(  j );
    break;
   }
   
  }
 }


 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new SplitTheInteger().start(10);
  
 }

}


Good Luck! & Happy Coding!!!

Friday, 20 December 2013

Turing Machine

Problem:

Design a TM to perform addition of 2 integers.

Background:

I am using TM with one way infinite tape

Time Complexity (for compute function):

O(m) where m is no1+no2
no1 is 1st operand for addition & no2 is second

Code:



import java.util.Scanner;

public class Adder {

 int head,sum;
 char[] tape;
 
 void init( ) {
  //one way infinite tape 
  tape = new char[37677];
  for (int i = 0; i < tape.length; i++) {
   tape[i] = 'B';
  }
  Scanner s = new Scanner(System.in);
  System.out.println("enter no1");
  int no1 = s.nextInt();
  System.out.println("enter no2");
  int no2 = s.nextInt();
  int p = 0;
  for (int i = 0; i < no1; i++,p++) {
   tape[i] = '0';
   
  }
  tape[p] = '1';
  p++;
  for (int i = 0; i < no2; i++,p++) { 
   tape[p] = '0';
  }
  compute();
 }
 private void compute() {
  // TODO Auto-generated method stub
  for (int i = 0; i < tape.length; i++) {
   if(tape[i] == '1') {
    tape[i] = '0';
   }
   if(tape[i] == 'B')
    reverse(i);
  }
 }
 
 private void reverse(int i) {
  // TODO Auto-generated method stub
  --i;
  tape[i] = 'B';
  for (int j = 0; j < tape.length; j++) {
   if(tape[j] != 'B')
    sum++;
  }
  System.out.println("sum is = " + sum);
  System.exit(0);
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new Adder().init();
 }

}

Cut The Rope


Problem:


Given a integer n, find all the subsets of n such that product obtained is maximum.

Eg 1: n = 10 {3 ,3 ,4} gives us 36 (highest product)
Eg 2: n = 20 {3 ,2 ,3 ,4 ,5 ,3} gives us 1080 (highest product)

Background:


At first glance i saw this problem as a inverted sum of subset problem, where we have given subsets as well as sum, but it is inverted because here we have just sum (n here) no subsets , we have to find all the subsets as a part of the solution.

After finding 1st subset store it somewhere, find next, now compare 1st and 2nd subsets product,
if 2nd subset-product > 1st subset-product
   store 2nd subset-product in some variable
repeat it until loops are exhausted.

Instead of solving it recursively i tried to solve it with tight for loops and a while loop.

Time Complexity:

O(n^2) and additional O(n) extra space.

Code:

import java.util.ArrayList;

public class CutTheRope {

 private int val;
 private int highval;
 private int m;
 /**
  * @param n
  */
 void start( int n ) {
  
  for (int i = 2; i < n-1; i++) {
   ArrayList myList = new ArrayList();
   myList.add(i);
   boolean isTrue = false;
   while (!isTrue) {
    
    
    for (int j = 2; j < n-1; j++) {
     int k = 0;
     for (Integer integer : myList) {
      k += integer.intValue();
     }
     //k+j+1 should not be equal to n ...
                                        //bcoz we r not staring loop from 1 its from 2
     if(k+j <= n && (k+j+1) != n)
      myList.add(j);
     if(k+j==n) {
      isTrue = true;
      break;
     }
    }
   }
   for (Integer integer : myList) {
    val = mult(integer.intValue());
    //System.out.print(integer + " ,");
   }
   //System.out.println();
   
   if (m >= 1) {
    if (highval < val)
     highval = val;
   }else {
   m++;
   highval = val;
   }
   k = -1;
  }
  if(highval != 0)
 System.out.println(highval);
   else
 System.out.println(n);
 }
 
 int k =-1;
 private int mult(int intValue) {
  // TODO Auto-generated method stub
  if(k == -1) {
   k = intValue;
  }
  else
  {
   k *= intValue;
  }
  return k;
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new CutTheRope().start(22);
 }

}
Try it!
Good Luck.......

Saturday, 28 September 2013

Premature optimization is an root of all evil

This post is for them who is obsessed with performance of there Java application

most people complaint that Java is slow, but after years of experience in Java i can say that Java itself is not slow, poorly written applications are slow. 

Things you should do when you code any application in Java

Java is mostly used as a Server side technology, but if you are making a Desktop application or providing a client application for you web application then you must consider the following suggestions

1. Always run you Swing GUI on EDT(Event Dispatching Thread) and perform your heavy task such as copying a long file or loading a heavy file in a editor using SwingWorker.

WHY SO ?

If you fully understand the Swing Rendering then you should not ask this question

In case if you don't then 
painting of Swing components must happen on the EDT. By calling synchronous paint methods, your code is implying that it is on the correct thread so that the right things will happen at the right time. If the calling code is not on that correct thread, the results could be undefined.


2. prefer Task & ExecutorService over Threads

ExecutorService manage Threads on your behalf it has capabilities to restrict number of threads to be ever created For e.g: if you have a production Server which is heavily loaded all times then this method will help you much because it will only create Threads you mentions which will provide room for others to run there own task and life will be more easier ....

Explaining every thing about concurrency framework is beyond the scope of this post

3. Prefer for each loop over traditional for loop
Although many compilers perform loop fusion techniques to improve performance of for loop it is also necessary to minimize the scope of variable using this technique

// No longer the preferred idiom to iterate
//over an array!
for (int i = 0; i < a.length; i++) {
doSomething(a[i]);
}


These idioms are better than while loops, but they aren’t perfect. The
iterator and the index variables are both just clutter. Furthermore, they represent
opportunities for error. The iterator and the index variable occur three times in
each loop, which gives you two chances to get them wrong. If you do, there is no
guarantee that the compiler will catch the problem.
The for-each loop, introduced in release 1.5, gets rid of the clutter and the
opportunity for error by hiding the iterator or index variable completely. The
resulting idiom applies equally to collections and arrays:


// The preferred idiom for iterating over 
//collections and arrays
for (Element e : elements) {
doSomething(e);
}


When you see the colon (:), read it as “in.” Thus, the loop above reads as “for
each element e in elements.” Note that there is no performance penalty for using
the for-each loop, even for arrays. In fact, it may offer a slight performance advantage
over an ordinary for loop in some circumstances, as it computes the limit of
the array index only once.

There are more things but i m running out of time ....!! Ta Ta...

Friday, 27 September 2013

Can You Find Longest Palindrome??

Placements            Placements            Placements!!!

This period of time I.e from September to I guess April is a golden period for all final year engineering students as many companies come to respective colleges paying different amount of salary “k” where k ranges between 2.50 <= k <= 7 lac/annum (at-least in my college).


Today as usual I was heading to my college in 8:24 CST train, in my compartment there were 2 students both were dumb, dumb because one of them was telling to other that “I couldn’t be able to write code for prime number during 1 to 1 PI (Personal Interview)” shit and still this people call themselves computer science majors ...duhh!!!



So I thought why not to write a series of blogs which will showcase some of the challenging problems in CS ranging from simplest to most challenging one's...HOPE THIS WILL HELP!



#1 Longest Palindrome


Problem statement:- Given a string “S”  find longest possible substring “Si” such that
0 <=s<=n
Where n is length of string S and s is length of String Si.


public class LongestSubstring {

    void start( ){
       String s = new Scanner(System.in).nextLine();
       palindrome(s);
   }
  
    public static void main(String[] args) {
       
        new LongestSubstring().start();
    }

    char[][] c;
    int uptr = 0,lptr = 1;
    private void palindrome(String s) {
        char[] str = s.toCharArray();
        c = new char[2][str.length];
        System.arraycopy(str, 0, c[lptr], 0, str.length);
        int j = str.length-1;
        for (int I = 0; I <= j; I++,j--) {
            if( str[I] == str[j] )
                c[uptr][I] = c[uptr][j] = '1';
            
        }
        int res = 0;
        for (int I = 0; I < c[0].length; I++) {
            if( c[uptr][I] == '1'){
                System.out.print(c[lptr][I]);
                res++;
            }
         }
        System.out.println();
        System.out.println("len of largest palindrome = " + res);
    }
}


OUTPUT:



#1 abgaffdgba
Longest palindrome – abgffgba



Stay hungry stay foolish!

Friday, 9 August 2013

Mod2 Division

 Hi there, its been a while i have not posted any thing just busy with my strong & hectic college schedule, today i m posting one of my work called

MOD2 DIVISION.


There is a reason to code this small library which performs mod2 division :
And the reason is , when implementing CRC in software we need to perform mod2 division.

for those who don't know what is CRC?.

How to use this Library ?


Modulo2Div modulo2Div = new Modulo2Div();
modulo2Div.setDividend("1111101");
modulo2Div.setDivisor("10001");
modulo2Div.mod2Div();
System.out.println( "QUo = " + modulo2Div.getQue() + " Rem = " + modulo2Div.getRem());


Note: inorder to use this library you must set this mod2lib.jar in your classpath.

Download