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 = summation 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 !!

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!!!

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.......

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...

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!

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

Problem #1

Little penguin Polo adores strings. But most of all he adores strings of length n.

One day he wanted to find a string that meets the following conditions:

1. The string consists of n lowercase English letters (that is, the string's length equals n), exactly k of these letters are distinct.
2. No two neighbouring letters of a string coincide; that is, if we represent a string as s = s₁s₂... s_n, then the following inequality holds, s_i ≠ s_i + 1(1 ≤ i < n).
3. Among all strings that meet points 1 and 2, the required string is lexicographically smallest.

Help him find such string or state that such string doesn't exist.

String x = x₁x₂... x_p is lexicographically less than string y = y₁y₂... y_q, if either p < q and x₁ = y₁, x₂ = y₂, ... , x_p = y_p, or there is such number r (r < p, r < q), that x₁ = y₁, x₂ = y₂, ... , x_r = y_r and x_r + 1 < y_r + 1. The characters of the strings are compared by their ASCII codes.

Input

A single line contains two positive integers n and k (1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 26) — the string's length and the number of distinct letters.

Output

In a single line print the required string. If there isn't such string, print "-1" (without the quotes).

Sample test(s)

input

7 4

output

ababacd

input

4 7

output

-1

Solution

Solution for the above problem can be downloaded from here

Sum Of Subset (Using PowerSet)

for those who don't know sum of subset problem just google it.

But allow me to explain what is power set 

e.g. let X be an set, X = { 1,2,3}
then power set will contain = 2^n subset of set X, where n is no. of elements in set X
so our power set will contain total 8 subset of set X
power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
notice that the 1st set is a null set because a null set is a subset of every set.

Now consider sum of subset problem 
let X be an array which contains input from user let X = {1,2,3}
then power set = { , {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} }
let m = 3

then the output of sum of subset problem is { {3},{1,2} }

if you are reading from beginning than now you must have a fair idea about what we are going to do, if you didn't understand than chill, the concept will be very clear in 5 minutes from now.

once we have computed the power set, we will take each individual set from the power set, if the power set contains only 1 element than we will compare that element with m if that element is equal to m than we will print that set as  1 of the solution, but if set contain multiple elements in it than we will add them all and compare the sum with m if it is equal than we will print the set. that's it!

Program:

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;


 //@author Naved Momin navedmomin10@gmail.com;

public class SumOfSubsets {


    public ArrayList powerSet(int a[]){
        ArrayList pw = new ArrayList();
        
        pw.add(" ");
        for (int i = 1; i <= a.length; i++) {
            ArrayList tmp = new ArrayList();
            
            for (String e : pw) {
                if(e.equals(" "))
                    tmp.add(""+a[i-1]);
                else
                    tmp.add(e+ " " + a[i-1]);
            }
            pw.addAll(tmp);
        }
       
        return pw;
    }
    int m ;
   
    
    public void navedsSOS( ArrayList p ){
        int sum = 0;
        System.out.println( "output: ");
        for (String string : p) {
            
                String[] split = string.split(" ");
                
                if(split.length > 1){
                    for (String no : split) {
                    sum += Integer.parseInt(no); 
                    }
                    if( sum == m){
                        if(!set.contains(string)){
                            set.add(string);
                            System.out.println( string );
                           
                        }
                    }
                    sum = 0;
                }else if( split.length == 1){
                    int k = Integer.parseInt(string);
                    if( k == m ){
                        if(!set.contains(string)){
                            System.out.println( " " + k );
                            set.add(string);
                        }
                    }

                }
            
        }
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        SumOfSubsets s = new SumOfSubsets();
        s.init();
    }
    int n ;
    int arr[];
    Scanner s = new Scanner(System.in);
    Set set = new LinkedHashSet();
    private void init() {
        System.out.println( "enter n ");
        n = s.nextInt();
        System.out.println( "enter m ");
        m = s.nextInt();
        arr = new int[n];
        System.out.println( "enter elemets ");
        
        
        
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
                    
            //set.add(arr[i]);
        }
  
        ArrayList powerSet = powerSet(arr);
        navedsSOS(powerSet);
    }
}

outout:

Finding Nth Largest Term In Unsorted Array

Given a task of finding nth largest term in an unsorted array by obeying following rules ...

Rules

1. You cannot sort an array
2. You cannot use a single library function (No API calls are allowed)
3. A separate copy of array should not be created

This can be easily implemented using a stack where we will start filling the stack with the smallest element, such that at the end we will get largest term at the top.

Algorithm:

1. accept array elements
2. determine the minimum element from the array
3. insert it into the stack
4. repeat step 2 & 3 until stack contains all elements of array
5. accept nth position from the user, say x
6. return the element which is stored at the x position
7. display the result
8. stop

Psuedo code for finding minimum element in an array

imin <-- 0;

        for ( i <-- 0; i < arr.length; i++) {

            imin <-- i;

            for (j <-- 0; j < arr.length; j++) {

                if( a[j] < a[imin] ){

                    imin <-- j;

                }

            }

        }

where " imin " stores index of the minimum element.

Code

package Kthlargestterm;

import java.util.Scanner;

 //@author Naved Momin(navedmomin10@gmail.com)
 
public class KthLargestTerm {

    static int[] a;
    static Scanner s = new Scanner(System.in);
    static int counter = 0;
    static StackUsingLL stack = new StackUsingLL();
    
    public KthLargestTerm(int size) {
        a = new int[size];
    }
    
    int getMin( ){
        int imin = 0;
        for (int i = 0; i < a.length; i++) {
            imin = i;
            for (int j = 0; j < a.length; j++) {
                if( a[j] < a[imin] ){
                    imin = j;
                }
            }
        }
        int k = a[imin];
        a[imin] = Integer.MAX_VALUE;
        return k;
    }
    
     
     static void getData( ){
        System.out.println( "enter size "); 
        int n = s.nextInt();
        KthLargestTerm kth = new KthLargestTerm(n);
        System.out.println( "enter data ");
        for (int i = 0; i < n; i++) {
            a[i] = s.nextInt();
        }
        
        int min = kth.getMin();
         int c = 0;
        while ( min != Integer.MAX_VALUE && c < n ) {             
            if(!stack.contains(min))
                stack.insert(min); 
            
            min = kth.getMin();
            c++;
         }
        
        System.out.println( "enter nTh position to view nth largest term ");
        int m = s.nextInt();
         while (m != -1) {     
             if( m >= 0 ) {
                    int item = stack.getItem(m);
                    String str =  (m == 1) ? "st" 
                            : (m==2) ? "nd" 
                            : (m == 3 ) ? "rd"
                            : "th";
                    
                    System.out.println( m + str +  " largest term is " + item );
                }
             System.out.println( "press -1 to exit or press any key to continue...");
             m = s.nextInt();
             if( m != -1 ){
                System.out.println( "enter nTh position to view nth largest term ");
                m = s.nextInt();
                
             }
         }
        
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        getData();
    
    }
}   




class Node{
    int data;
    Node next;
}

public class StackUsingLL {
 
    Node top ;
    static int insertAccount = 1;
    
    public boolean isempty( ){
       if( top == null ){
           return true;
       }else
           return false;
    }
    
    public void insert( int x ){
        Node newrec  = new Node();
        newrec.data = x;
        newrec.next = null;
        
        if( top == null ){
            top = newrec;
        }else{
        newrec.next = top;
        top = newrec;
        }

      insertAccount++;
    }
    
    public int delete( ){
        if( isempty() ){
            System.out.println( "stack empty" );
        return -1;
        }
        else{
            int x = top.data;
            top = top.next;
            return x;
        }
    }
    
    public boolean hasNext( ){
        
        if( top != null ){
            return true;
        }
        else{
            return false;
        }
    }
    
    public boolean contains( int min ){
        boolean val = false;
        Node p = top;
        while ( p != null ) {            
            if( stackTop( ) == min ){
                val = true;
                break;
            }
            else
                val = false;
            p = p.next;
        }
        return val;
    }
    
   public int getItem( int index ){
        if( index <= insertAccount ){
            int i = 1;
            int d = -1;
            Node p = top;
            while (p != null) {            
                if( index == i ){
                    d = p.data;
                    break;
                }
                i++;
                p = p.next;
            }
            return d;
        }else{
            System.err.println( "index was out of range ...");
            return -1;
        }
    }
    
    public int stackTop(){
        return top.data;
    }
    
    public void display( ){
        if( isempty() )
            System.out.println( "stack empty");
        else{
            Node p = top;
            while (p != null) {
                System.out.println( p.data + " ");
                p = p.next;
            }
        }
    }
    
}

Output

In case you want *.jar file then download it from here

Swapping Using 2 Variables

Some of mine friends asked me a question, the Question was

Agreed that we can swap two numbers using some math, but how can we swap two chars & string without using 3rd variable ?

This blog post will answer the question, the method i have used is preety simple & straight forward
We will do following swapping

• Number Swapping
• Chars Swapping 
• Strings Swapping

To begin with lets quickly see the codes

• Number Swapping

 void swappingNumbers( int a, int b ){

        System.out.println( "input value  a = " + a + "  b = " + b );
        a = a+b;
        b = a-b;
        a = a-b;
        System.out.println( "swapped values a = " + a + " " + " b = " + b );
    }

The above code swaps two ( signed & unsigned ) numbers without using any 3rd variable

• Chars Swapping 

 void swappingChars(char a, char b ){
        System.out.println( "input value  a = " + a + "  b = " + b );
        int p = (int)a ,q = (int)b;
        p =  ( ( (int) p ) + ((int)q) ) ;
        q = ( ( (int) p ) - ((int)q) ) ;
        p = ( ( (int) p ) - ((int)q) ) ;
        System.out.println( "swapped values p = " +  ( (char)p) + " q = " + ((char)q) );
    }

The above code swaps 2 chars without using 3rd variable. Here using two variable i.e p & q we have swap the chars

• String Swapping

 
void swappingStrings(String str1, String str2){
        System.out.println( "input value  str1 = " + str1 + "  str2  = " + str2 );
        str2 = str1 + " " + str2;
        String[] split = str2.split(" ");
        str1 = split[1];
        str2 = split[0];
        System.out.println( "swapped values = str1 = " + str1 + " str2 = " + str2);
    }

The above code swaps 2 Strings without using 3rd variable.

Output

Hope this helps.

Huffman-Encoding In Action

Curiosity regarding huffman-decoding process, force me to make one working huffman-encoding/decoding app.

What is Huffman-Encoding In Action ?

Huffman-Encoding In Action is a small GUI program which allows you to visualize how huffman encoding decoding works.

The actual work is done in a class that encapsulates all the functionality, so it should be easy to set up another GUI for it.

For those who don't know what is Huffman Coding read this 

How It Works 

Let q be the priority doubly linked list

l be the list

class Node
{
    Node left, right;
    char data;
    int freq;
    char lEW = ' ';
    char rEW = ' ';
    boolean isRoot = false;
}

Above code is a structure of a node

/**
     * start of the algorithm
     * characters are read'ed 1 by 1 and count is determined using variable count 
     * and a newrec of type node is created which has a data as = char and freq = count for eg:
     * x is the char which appears 3 times then newrec.data = x and newrec.freq = 3 and finally it is inserted 
     * into Sorted DLL and l contains the char x so that when x appear next we could identify that its freq is already
     * determined
     * the same process is repeated for all the char in the string or txt.
     * @param txt 
     */
    public void start( String txt ){
        ogtxt = txt;
        char[] toCharArray = txt.toCharArray();
        for (char x : toCharArray) {
            int count = 0;
            
            
            if( !(l.contains( String.valueOf( x ) ) ) ){
                for (char k : toCharArray) {
                    if( k == x )
                        count++;
                }
                Node newrec = new Node();
                newrec.freq = count;
                newrec.data = x;
                newrec.left = newrec.right = null;
                q.insert(newrec);
                l.add(String.valueOf( x ));
            }
           
        }

        makeSingleTree( );//a recursive function which makes single huffman tree. base case = when there will be only one record in our sorted doubly linked list.
        root = q.delete();// that single tree is now assigned to root
        root.isRoot = true;
         if(root.left != null & root.right != null){
            assignWeights( root );// assigns 0 to every left edge and 1 to every right edge
            traverse(root);//this will traverse and determine the huffman code for each letter or char.
        }else{
            onlyOneNode = true;
        }
        displayHuffmanCode();// this function will display the unique huffman code for each char.
       
    }

So, there you go, now you have basic idea about how the entire process works, the code is well formed in several different methods and is pretty easy to understand as well.

Speed

On my Desktop with with 2.8GHZ. Huffman-Encoder requires just a couple of ms to generate huffman code.

Download

you can download Huffman-Encoding In Action's latest version from here

Miscellaneous 

When given input such as OOOOOOO the encoder will show output Only1Node O 7.

InOrder Traversal Of BST (Iterative Solution)

One best question in my sem-III DSF paper was 

Iterative Solution For Inorder Traversal

I was not prepare for it, but i was knowing the recursive way of traversing the BST tree so i applied  the same concept and find out a algo in 25 minutes sadly in 5 minutes or even less i couldn't complete that question and my ma'am snatch the paper, coz the time was 5:30 pm duhh!!

And after examz i came home and implemented that algo and it was 100% perfect solution for iterative way of Tree traversal , today i m gonna show that to you .......

The thing you must note, in the Stack implementation is that it does not store the data it store the refrence i.e a Node which inturn contains the data.

package datastructurepractice.BST;

/**
 *
 * @author Naved Momin
 */
class StackNode
{
    Node data;
    StackNode next;
}

public class StackForBST {
    StackNode top;
    
    public void push( Node x ){
        if( x != null )
        {
            StackNode newrec = new StackNode();
            newrec.data = x;
            newrec.next = null;
            if( top == null)
                top = newrec;
            else
            {
                newrec.next = top;
                top = newrec;
            }
        }

    }
    
    public void display( ){
        System.out.println( "stack display");
        if( isempty() )
            System.out.println(" empty stack ....");
        StackNode n = top;
        while( n != null){
            Node r = n.data;
            System.out.print (r.data + " ");
            n = n.next;
        }
    }
    
    boolean isempty( ){
        if( top == null)
           return true;
        else
            return false;
    }
    
    Node stacktop( ){
        if( top != null )
        return top.data;
        else
            return null;
    }
            
    
    
    public Node pop( ){
        if( !isempty() ){
            Node x = top.data;
            top = top.next;
            return x;
        }else{
            System.out.println( "stack out of data");
            System.exit(0);
            return null;
        }
    }
    
}


package datastructurepractice.BST;

import java.util.Calendar;
import java.util.Scanner;

/**
 *
 * @author Naved Momin
 */

class Node{
    int data;
    boolean lV = false, rV = false;
    Node left, right;
}
public class BST {
    Node root;
    private long start;
    private long end;
    
    public void travInorder( ){
        inorder(root);
    }
    
    public void insert( int x ){
        Node newrec = new Node();
        newrec.data = x;
        newrec.left = null;
        newrec.right = null;
        if( root == null){
            root = newrec;
        }
        else{
            Node a, b;
            a = b = root;
            while( a != null ){
                b = a;
                if( x < a.data ){
                    a = a.left;
                }else{
                    a = a.right;
                }
            }
            if( x <= b.data ){
                b.left = newrec;
            }else{
                b.right = newrec;
            }
        }
        

    }
    
    public void displayInorder( ){
        System.out.println( "inorder recurssive ");
        long start1 = Calendar.getInstance().getTimeInMillis();
        inorder(root);
        long end1 = Calendar.getInstance().getTimeInMillis();
        System.out.println( "total time taken (Recursive)" + (end1 - start1 ) + " ms");
        
        
        System.out.println( "inorder iterative ");
        start = Calendar.getInstance().getTimeInMillis();
        inOrderIterative(root);
        
        
    }
    
    public void delete( ){
        System.out.println( "enter value ot be deleted");
        int v = new Scanner(System.in).nextInt();
        
        Node a, b ;
        a = b = root;
        while( a != null && a.data != v){
            b = a;
            if( v < a.data )
                a = a.left;
            else
                a = a.right;
        }
        if( a == null )
            System.out.println( "i could not find the value");
        else{
            if( a.left != null && a.right == null){
                if( root == a){
                    root = a.left;
                }else{
                    if( a == b.left){
                        b.left = a.left;
                    }else{
                        b.right = a.left;
                    }
                }
            }
            else if( a.right != null && a.left == null ){
                if( root == a){
                    root = a.right;
                }else if( b.right == a){
                    b.right = a.right;
                }else{
                    b.left = a.right;
                }
            }else if( a.right == null && a.left == null){
                if( root == a){
                    root = null;
                }else if( b.right == a){
                    b.right = null;
                }else{
                    b.left = null;
                }
            }else if( a.right != null && a.left != null){
                Node c = a.right;
                while (c.left != null) {
                    c = c.left;   
                }
                c.left = a.left;
                if( a == root){
                    root = a.right;
                }else {
                    if( b.left == a)
                        b.left = a.right;
                    else
                        b.right = a.right;
                    
                }
                
            }
            System.out.println( "deleted node = " + v) ;
        }
    }
    
    
    
    boolean isempty( ){
        if( root == null)
            return true;
        else
            return false;
    }
    
    public void inOrderIterative( Node root ){
        StackForBST s = new StackForBST();
        s.push(root);
        
        while (true) {            
            Node r = s.stacktop();
           
            while( r.lV && r.rV ){
                s.pop();
                r = s.stacktop();
                
                if( r == null ){
                    end = Calendar.getInstance().getTimeInMillis();
                    System.out.println( "total time taken (Iterative)" + (end - start ) + " ms");
                    System.exit(0);//when stack becomes empty
                }
                    
            }
            
            
            
            if( !r.lV){
                while( r.left != null){
                    r.lV = true;
                    r = r.left;
                    s.push(r);
                }
            }
            r.lV = true;
            System.out.print(r.data + " ");
            
            if( r.lV == true && r.rV == false && r.right != null){
                r.rV = true;
                r = r.right;
                s.push(r);
            }else{
                r.rV = true;
            }
        
       }
        
        
    }
    
    
    
    public void inorder( Node root  ){
       
        if( root != null ){
            inorder(root.left);
            System.out.print( root.data + " ");
            inorder(root.right);
        }
        
    }
    public static void main(String[] args) {
        // TODO code application logic here
    }

}

//Output

run:
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
11111
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
22222
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
333333
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
444444
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
666666
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
555555
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
5656
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
4545
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
2323
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
1212
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
8989
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
45457
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
23235
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
454545
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232345
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
232356
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
12214
enter 1 for insert 2 for delete 3 for display 4 for exits 
122
exits command executed
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
3
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
444
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
55
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
32
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
1
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
2
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
3
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
4
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
5
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
6
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
7
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
8
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
9
enter 1 for insert 2 for delete 3 for display 4 for exits 
1
enter no
10
enter 1 for insert 2 for delete 3 for display 4 for exits 
3
inorder recurssive 
1 2 3 3 4 5 6 7 8 9 10 32 55 444 1212 2323 4545 5656 8989 11111 12214 22222 23235 45457 232356 232356 333333 444444 454545 555555 666666 
total time taken (Recursive)3 ms

inorder iterative 
1 2 3 3 4 5 6 7 8 9 10 32 55 444 1212 2323 4545 5656 8989 11111 12214 22222 23235 45457 232356 232356 333333 444444 454545 555555 666666 
total time taken (Iterative)13 ms

From this it looks like recursive approach is faster than iterative approach.......Hence we have proved that recursion is not always slow, there are some problems which are best solved(In terms of performance & simplicity) by "RECURSION".

Trace the code to get the algo. and slight modification will give you preorder & postorder....GL.

Top 10 Tricks To Fool Your Java Professor

Trick #2

This week's trick will teach you how to find loopholes in existing programs for this you need to have deep understanding about how the underlying code works and how the Platform on which the code is running works.

Let me explain you this with an help of an example:-

Let us consider the simple and very basic example, our challenge is to write code which will tell us whether the given number is odd or not, so lets give a name to this program

ODD OR NOT

when given this challenge most people write this code:

If one can catch the flaw in this code then h/she is a Java Expert

public class OddOrNot
{
 static boolean isOdd(int no){
  return (no % 2) == 1;
 }
 public static void main(String[] arge){
  System.out.println(isOdd(7));
 }
}

Sadly if you are not the one, then i suggest you to read further

There are 2 flaw's in this code 

1. Performance penalty (Mod operations are always less preferable)
2. Code fails as soon as you pass a negative odd number 

Now you know the flaw, then you should be keen to know what best solution can be written for this type of challenges, stay connected....

why code fails ?

This is because, the java's truncating integer division operator[JLS 15.17.2], it implies that when the remainder operation returns a non zero result, it has the same sign as its left operand.  

So now you know the hidden flaw of the above written code, yes it return -1 as soon as you enter any negative odd number.

So, What is the best way to solve this challenge?

USE Bit-Wise-And (&), If you can use bit-wise-and (&) instead of mod (%) operation then always prefer bit-wise-and (&) operation, to increase performance of your application.

public class OddOrNot
{
  static boolean isOdd( int no ){
   return ( no & 1 ) == 1;
  }
  public static void main( String[] arge ){
   System.out.println( isOdd( -7 ) );
  }
}

Working

 If you convert any odd decimal number to its binary equivalent than you will get answer as pattern xxx1 i.e. any odd number ends with 1 and any even number ends with 0 so when we do 1 & 1 = 1 and when we do 0 & 1 = 0

This time you have learned another technique to impress your Boss, friends, professor etc.

Wait for the next trick #3

happy coding

Understanding java.io.StreamCorruptedException: invalid type code: AC

We can transport Objects in Java in two ways

1. Using Serialization 
2. Using RMI ( Remote Method Invocation ) 

last night i was using 1st approach to transport Objects from my server to client, while doing so my code throws 

java.io.StreamCorruptedException: invalid type code: AC

Lets see first what Javadoc has to say about this 

StreamCorruptedException :-  Thrown when control information that was read from an object stream violates internal consistency checks.

 Do you understand any thing ???

No ???

Then, continue reading ...

 So lets look at this exception closely 

This exception (java.io.StreamCorruptedException: invalid type code: AC) only occurs when any one use's a new ObjectOutputStream to write to an existing ObjectInputStream that you have already used a prior ObjectOutputStream to write to. These streams have headers which are written and read by the respective constructors, so if you start another ObjectOutputStream you will write a new header, which starts with - guess what? - 0xAC, and the existing ObjectInputStream isn't expecting another header at this point so it barfs.

So now I guess you have enough understanding about this Exception and next time you will not commit this mistake, and hence this will escape you from wasting enormous amount of time figuring out why this exception is thrown

So the bottom line is

1. Always use only one ObjectOutputStream & corresponding ObjectInputStream through out the life of Socket
2. If you are writing data over Socket using ObjectOutputStream then read that data only using  ObjectInputStream otherwise Exception could be thrown
3. If you want to forget about what you have written then do 

   objectOutputStream.reset();
   

Top 10 Tricks To Fool Your Java Professor

Trick #1

1. Is your java professor always yells at you ? 
2. Does he/she always tells you that you don't know anything about Java ?

If the answer is yes then this post is for you

Its Payback time

Next time when you meet your professor in viva or in general ask him/her a simple question 

Q. can you show me a simple program which print a NUMBER 0123 ?

if your professor is smart enough he/she will write this code 

System.out.println(123);

and gives you a explanation about why he/she has not written 0 (zero) 

if your professor in dumb (which 80% are) will end up with this code

System.out.println(0123);

So, when he will execute this code he will get output as 83

CONFUSED ???

This is because if any number is padded with initial 0 then that number is treated as Octal in Java so when you execute above code the JVM will convert the Octal to Decimal and print 83 on stdout.

So when you will explain this to your professor without the help of Google then he will be impressed :)

The problem is that most people just learn the syntax of a language and not its capability, learning syntax is very easy any moron can learn it within a month or so but learning capability takes almost years of expertise.

Wait for the next trick #2
till that time
stay hungry stay foolish

IO-Utilities

Whenever I take any new project, I always require my Utilities library which provides me following features:

1. Copying my library from dependency to  C Drive or  user's home directory in windows or *nix systems
2. Compressing/Decompressing any Images or files for uploading or transferring it over network
3. Getting extension of any file name in faster way

All this features can be achieved using just one library, and using this library is dam easy...even you can attach a listener to listen the processing i.e.

• Name, count, size, compression level, copying from & copying to path of the file which library is processing ..

To attach a listener use this code

import fileutilslibrary.CopyEvent;
import fileutilslibrary.FileUtils;
import fileutilslibrary.Listener;
import fileutilslibrary.ZipEvent;
import java.io.File;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author Naved Momin<naved.spartans.rocks75@gmail.com>
 */
public class Demo2 implements Listener{

    void start( ) throws IOException{
        FileUtils.getInstance().addListener(this);
     
        FileUtils.zipMyFolder(new File("C:\\Users\\Admin\\Desktop\\imgToVideo/RemoteDesktop"),
                  new File("C:/Users/Admin/Desktop/HMS Latest/RDnew.zip"),9);
                 

     
    }
    public static void main(String[] args) {
 
        try {
            // TODO code application logic here
            new Demo2().start();
        } catch (IOException ex) {
            Logger.getLogger(Demo2.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    @Override
    public void copyListener(CopyEvent e) {
        //notification about copying event
    }

    @Override
    public void zipListener(ZipEvent e) {
        //notification about zip event
        System.out.println( "name " +e.getZipingFileName() +  "\n" + "size " + e.getZipingFileSize() + "\n" +
        " count " + e.getFileCount( ) + "\n" +
        "level  " + e.getCompressionLevel() );
    }
}

Various Methods:-

Copy a Directory

FileUtils.copyDirectory(src, dest);

Copy a File

FileUtils.copyFile(src, dest);

Zip Directory 

FileUtils.zipMyFolder(src, dest);

Zip Directory With Custom Compression Level

FileUtils.zipMyFolder(src, dest, compressionLevel);

Note: Compression level must be between 0-9, by default 0 is used

Zip File

FileUtils.zipMyFile(src, dest);

Zip File With Custom Compression Level

FileUtils.zipMyFile(src, dest, compressionLevel);

Note: Compression level must be between 0-9, by default 0 is used

UnZip File

FileUtils.doUnZip(src, dest);

Get File Extension (10x faster)

FileUtils.getExtension(path);

Reverse a String

FileUtils.reverse(str);

Get File Name 

FileUtils.getName(pathToFile);

Note: The library is written in pure Java code except the Wallpaper class which throws NotSupportedOSException if OS is not supported by the library for more information see Javadoc included in the download package.

This library is totally compatible with various 3rd party zip utilities like winrar, which means you can zip your files programmatically and still use winrar for unzip'ing the file or vice-versa is also possible. 

For any bug or suggestions mail me at naved.spartans.rocks75@gmail.com

This Library is License under GNU General Public License

Download latest builds

Take Away ( Free Of Cost )

This week on take away i m giving away a software which i had sole'd to 4 peoples, 1 last year and 3 this year as a final year project (diploma),  The software performs following functions

1. Encrypt any of your .png or .jpg files with AES (  Advanced Encryption Standard  )

Last year when i sole'd this project that guy asked me a smart question 

What if there is a spyware running on my computer which is capturing all my input or keystroke's ?

 So to solve this problem i have added a layer called second factor of authentication which is

SOMETHING YOU HAVE

now the software can defeat any keylogger's (remember keylogger's have types)

1. The ones which only capture your keystokes
2. another one is a bit advance and apart form capturing keystroke's they also capture your screen

So now even though that spyware software has your secret key which you have used to encrypt your image's, he/she will not be able to decrypt it until he/she has your "TOKEN"

TOKEN can be any thing your pen-drive, external hdd, or whatever which you can plug into system and prove that you are the one which actually encrypted the images, unless & until token has not been inserted the software will not perform decryption process.

So i m giving away the simple version of this software which only encrypts and decrypts without defeating keylogger's .

if you want the more advance version of this software then mail me at naved.spartans.rocks75@gmail.com

Always download latest builds

NTSystem VS System.getProperty("user.name")

Yesterday i was reviewing my friends code, In that i found a class called NTSystem my friend was actually using this class because of this method

public String getName(); //This method gets you the current logged in user

I asked him do you think this application will work in Linux and he replied yes of course then i smiled and said try it out he tried and call me this morning and said the application is throwing

ClassNotFoundException 

why so ?

Thing is that Beginners don't understand the working, they just somehow learn (in chalega ..chalega style) or copy the code from internet the things to know is, though Java is machine independent JVM is not .

JVM is exclusive made for each OS. 

Thats why when you use NTSystem class in windows it works like a charm but the code throws an Exception when you run it on some other OS just because the JVM don't know what NTSystem is !

If you had download the JDK for Linux, there you will not find the NTSystem class.

So the bottom line is if you want to get the current logged in user in Java always use 

System.getProperty("user.name");

This Method has 2 benefits

1. Your code will be machine independent
2. You will get the current logged in user