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:

Round Robin In Java

for those who don't know Round Robin algorithm

Program

import java.util.Scanner;

 
 //@author Naved Momin naved.spartans.rocks75@gmail.com/navedmomin10@gmail.com
 
public class SimpleRR {

    int [] temp;
    int commBT, k, tq;
    int[][] d;
    int btcache;

    
    void getData( ){
        Scanner s = new Scanner(System.in);
        System.out.println( "enter no. of process");
        int pcount = s.nextInt();
        d = new int[pcount][2];

        temp = new int[pcount];
        System.out.println( "enter BT");
        for (int i = 0; i < pcount; i++) {
            d[i][0] = i;

            int m = s.nextInt();
            d[i][1] = m;

            commBT += m;
        }
        System.out.println( "enter TQ ");
        tq = s.nextInt();
        start();
        display( );
        
    }
    void start( ){
        for (int i = 0; i < d.length; i++) {
            int bt  = d[i][1];
            if( bt > 0){
                if( bt <= tq){
                    temp[i] = btcache+bt;
                    btcache = temp[i];
                    k += bt;
                    bt -= bt;
                     
                }
                else{
                    temp[i] = btcache+tq;
                    btcache = temp[i];
                    bt -= tq;
                    k += tq;
                }
                
                d[i][1] = bt;
               
                
            }
        }
        if( k!= commBT)
            start();
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        SimpleRR r = new SimpleRR();
        r.getData();
    }

    private void display() {
        float val = 0;
        int c = 1;
        for (int i : temp) {
            System.out.println( "BT for process " + c + " is " + i );
            val += i;
            c++;
        }
        System.out.println( "avg BT = " + val/temp.length);
    }
}

The above code finds & prints turn-around time & average turn around time for the given data.

Output

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

Correct Implementation of Insertion Sort

Given a task of implementing insertion sort, many people end up with following code 

    
void insertionSort(int a[]){
 for (int i = 0; i < a.length; i++) {
                
                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }
                    
                }
 }
}

Although the code works as expected & sorts the given data in O(n^2) time, but this is the wrong implementation of insertion sort.

Do You Know Why ?

The reason is best case time complexity of insertion sort is O(n) but this code has O(n^2), in short no matter what sequence of data you through at this code it will take O(n^2) time i.e best, avg. & worst case time complexity of this code is O(n^2).

Note: If you have clear your "Analysis of Algorithms & Design" paper you will understand what is written above.

If you have understand the above statements than you can fix the wrong implementation on your own, the above implementation can be corrected by just adding one statement which i left it for you as an exercise.

In case you are in hurry you can adopt My way to write insertion sort

Correct Implementation 

    
 int[] insertionSort(int [] a ){
        for (int j = 1; j < a.length; j++) {
            int i = j-1;
            while ( ( i >= 0 ) && a[i] > a[i+1] ) {                
                int k = a[i];
                a[i] = a[i+1];
                a[i+1] = k;
                i -= 1;
            }
        }
        return a;
    }

The best case time complexity(i.e when array elements are already in ascending order) of this code is O(n) & worst case time complexity is O(n^2), which proves that this code is correct implementation of Insertion Sort.

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.

Java Matrix Multiplication (JMM)

Often in many areas of programming people require a tool which can simplify there n*n matrix multiplication problem in reasonable amount of time.

This can usually be done with 3 tight for loop and special care for handling dimension errors(which i assumes most of you knows) to do this i have a designed a special class and added it to my Utilities framework 1.1.2

Lets quickly take 1 example for 2*2 matrix multiplication using Utilities-1.1.2

  

class MatrixMultiplication
{
public static void main(String[] str) throws DimensionError{
        double[][] a = { {1.2,2.25}, {25.0,28.2} };
        double[][] b = { {1.2,2.25}, {25.0,25.2} };
        double[][] multiplyMatrix = new Math().multiplyMatrix(a, b);
        for (double[] ds : multiplyMatrix) {
            for (double d : ds) {
                System.out.print( d + " ");
            }
            System.out.println();
        }
    }
}
}

Output

So, now you know how simple is matrix multiplication.

Dimension Errors

A special care has been taken to indicate that matrix multiplication is not possible and this is indicated using DimensionError Exception

consider the following example

import math.DimensionError;
import math.Math;
public class MatrixMultiplication {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] str) {
        double[][] a = { {1.2,2.25,2}, {25.0,28.2,2}, {25.2, 14.25,2} };
        double[][] b = { {1.2,2.25}, {25.0,25.2} };
 try{
        double[][] multiplyMatrix = new Math().multiplyMatrix(a, b);
        for (double[] ds : multiplyMatrix) {
            for (double d : ds) {
                System.out.print( d + " ");
            }
            System.out.println();
        }
 }catch(DimensionError ex){
  System.out.println(ex.getErrorMessage());
 }
    }
}

Output

Speed

Worst case time complexity is O(n^3)


Download

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.

Movie Scheduling Problem

Last night one of mine coding friend thrown a problem on me, & he called it as movie scheduling problem, He wanted me to develop a algo & code for this.

The Problem

Let x be a super-star
Let n be a Producer

n Producers wanted to cast x in there upcoming movie, and for that they are offering the same amount to x but the start & end date interval of each movie making process is different for eg. 1 movie require 10 months to complete whereas other require 1.5 yrs, now the algo. has to decide which movie x will do such that x will make the highest profit.

The criteria for job acceptance is clear: 

x want to make as much money as possible. Because each of these films pays the same fee

per film, this implies x seek the largest possible set of jobs (intervals) such that
no two of them conflict with each other.


I come up with 3 Algo's lets go through it one by one ...

ALGO 1: Earliest Job 1st

Suppose x don't have any work so he will select a movie which ever comes first
but this algo will not make the highest profit bcoz if actor select the 1st movie and the 2nd to 5th movie offers are such that the total time period require to complete all 4 movies is equal to time require to complete 1st movie.
So here the total loss is of 4 movies...


ALGO 2: Smallest Job 1st

This algo is better than the previous one bcoz it will give decent solution.

ALGO 3: Earliest Completion Date

This algo. gives optimal solutions for most of the possible inputs ...

I have coded the solution for Algo 3 whose output looks like ...

The Output
--------------------------------------------------------------------------------------------------------------
The output is a 4 dimension array where
0th column gives movie name
1st column gives start date
2nd column indicates end date
3rd column indicates status P or F , such that P indicate, the no. of movies has to be accepted by x to earn the maxm profit.

Download 

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.

Non Restroing Division

/*

 * 4 bit Non Restoring Division implementation

 */


package addandshiftalgo;



import java.util.Scanner;



/**

 *

 * @author Naved Momin

 */

public class NonRestoringDivision {



    int m , q, c, ac;

    String  acStr = "0000", qstr, mstr, cStr, acc, twoscompliment;

  

    private  void read() {

        Scanner s = new Scanner(System.in);

        System.out.println( "enter m " ) ;

        int read = s.nextInt();

        m =  read;

        System.out.println( "enter q " ) ;

        read = s.nextInt();

        q =  read;

        twoscompliment();

    }

  

    void twoscompliment( ){

        twoscompliment = Integer.toBinaryString( - m ).substring(27, 32);

    }

  

    void startALgo( ){

        read();

      

        for (int i = 0; i < 4; i++) {



            qstr = Integer.toBinaryString(q);

          

            mkQOf4Bit();

            char charAt0 = qstr.charAt(0);

            acStr = Integer.toBinaryString(ac);

            acStr = ( acStr + String.valueOf(charAt0) ).substring(1);

            ac = Integer.parseInt(acStr,2);

            qstr = Integer.toBinaryString(q);

            mkQOf4Bit();

            qstr = qstr.substring(1);

            q = Integer.parseInt(qstr, 2);

            q <<= 1;

            qstr = Integer.toBinaryString(q);

            mkQOf4Bit();

          

            if( c == 1){

                ac = ac + m;

                acStr = Integer.toBinaryString(ac);

                 if( acStr.length() > 5){

                    acStr = acStr.substring(1);

                }

                charAt0 = acStr.charAt(0);

                c = Integer.parseInt(String.valueOf(charAt0), 2);

                if( c == 0 ){

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "1";

                    q = Integer.parseInt(qstr, 2);

                }else if( c == 1){

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "0";

                    q = Integer.parseInt(qstr, 2);

              

                }

              

                acStr = acStr.substring(1);

              

              

            }else{

                int twoscomp = Integer.parseInt(twoscompliment, 2);

                ac = ac + twoscomp;

                acStr = Integer.toBinaryString(ac);

                if( acStr.length() > 5){

                    acStr = acStr.substring(1);

                }

                      

                charAt0 = acStr.charAt(0);

                c = Integer.parseInt(String.valueOf(charAt0), 2);

                if( c == 1){

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "0";

                    q = Integer.parseInt(qstr, 2);

                }else if( c == 0 ){

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "1";

                    q = Integer.parseInt(qstr, 2);

                }

              



                acStr = acStr.substring(1);

              

              

            }

          

          

        }

        ac = Integer.parseInt(acStr, 2);

        if( c == 1){

            String  acc = Integer.toBinaryString(c) + acStr;

            int accInt = Integer.parseInt(acc, 2);

            ac = accInt + m;

            acStr = Integer.toBinaryString(ac);

            if( acStr.length() > 5 ){

                acStr = acStr.substring(1);

            }

            ac = Integer.parseInt(acStr, 2);

        }

      

      

        System.out.println( "ac = " + ac + " q = " + q );

      

    }

  

    void mkQOf4Bit( ){

        if( qstr.length() <= 4 ){

                int formula = 4 - qstr.length();

                for (int j = 0; j < formula; j++) {

                    qstr = "0" + qstr;

                }

            }

    }

  

    public static void main(String[] args) {

        // TODO code application logic here

       new NonRestoringDivision().startALgo();

    }

}

Implementation Of Restoring Algorithm

Implementation Of Restoring Algorithm on 4 Bit Numbers

package addandshiftalgo;

import java.util.Scanner;

/**

 *

 * @author Naved Momin<naved.spartans.rocks75@gmail.com>

 */

public class RestoringDivision {

    int m , q, c, ac;

    String  acStr = "0", qstr, mstr, cStr, acc, twoscompliment;

    

    private  void read() {

        Scanner s = new Scanner(System.in);

        System.out.println( "enter m " ) ;

        int read = s.nextInt();

        m =  read;

        System.out.println( "enter q " ) ;

        read = s.nextInt();

        q =  read;

        twoscompliment();

    }

    

    void twoscompliment( ){

        twoscompliment = Integer.toBinaryString( - m ).substring(27, 32);

    }

    

    void startALgo( ){

        read();

        

        for (int i = 0; i < 4; i++) {

            qstr = Integer.toBinaryString(q);

            

            mkQOf4Bit();

            char charAt0 = qstr.charAt(0);

            acStr = Integer.toBinaryString(ac);

            acStr = acStr + String.valueOf(charAt0);

            ac = Integer.parseInt(acStr,2);

            q <<= 1;

            qstr = Integer.toBinaryString(q);

            if( qstr.length() > 4){

                qstr = qstr.substring(1);

            }else{

                q = Integer.parseInt(qstr, 2);

            }

            

            int n = Integer.parseInt(twoscompliment, 2) ;

            n = n + ac;

            String bString = Integer.toBinaryString(n);

            acStr = bString.substring(1);

            ac = Integer.parseInt(acStr, 2);

            cStr = String.valueOf( acStr.charAt(0) ) ;

            c = Integer.parseInt(cStr,2);

            

            if( c == 1){

                qstr = Integer.toBinaryString(q);

                mkQOf4Bit();

                

                if( qstr.length() > 4 )

                    qstr = qstr.substring(1);

                

                

                

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "0";

                    //qstr = qstr.substring(1);

                    q = Integer.parseInt(qstr,2);

                    String sum = Integer.toBinaryString(c) + Integer.toBinaryString(ac);

                    int s = Integer.parseInt(sum, 2);

                    s = s + m;

                    sum = Integer.toBinaryString(s);

                    ac = Integer.parseInt(sum.substring(1),2);

                    c = 0;

                

            }else{

                qstr = Integer.toBinaryString(q);

                mkQOf4Bit();

                

                if( qstr.length() > 4 )

                    qstr = qstr.substring(1);

                

                

               

                    String substring = qstr.substring(0, 3);

                    qstr = substring + "1";

                    q = Integer.parseInt(qstr,2);

               

                

            }

            

        }

        

        System.out.println( "ac = " + ac + " q = " + q );

        

    }

    

    void mkQOf4Bit( ){

        if( qstr.length() <= 4 ){

                int formula = 4 - qstr.length();

                for (int j = 0; j < formula; j++) {

                    qstr = "0" + qstr;

                }

            }

    }

    

    public static void main(String[] args) {

        // TODO code application logic here

        new RestoringDivision().startALgo();

    }

}

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();