What is Program Design by Example - ISBN-10

Writing a program by an engineer starts, just like creating the blueprint of a building by an architect, by design.  Before we get to the design phase, we have to understand and then analyze the problem.

Problem:  Given a book title and its ISBN-10 number, you need to validate if the ISBN number is valid or not.
Starting Out with Java: Early Objects (5th Edition) 5th Edition
ISBN-10: 0133776743

Analysis:  ISBN-10 is a unique number that must be generated based on an algorithm that must ensure its unique value and its validity must be verifiable.  Let's find out how the algorithm works and if there is a reliable source that we can refer to.
I can see that it does have a check digit at the end of the number:
https://www.isbn-international.org/content/standard-book-numbering-turns-50
I can see how it is calculated in ISBN-13, but not in ISBN-10
https://www.isbn-international.org/sites/default/files/ISBN%20Manual%202012%20-corr.pdf
I got it, this looks reliable source
https://www.isbn-information.com/the-10-digit-isbn.html
Let's work out the example in the document to see if I understand it.
Now, let's use the given ISBN and do the calculation by hand on paper so I'll understand how it is done, before I decide on how to write a program.
So, the number is 0133776743
Let's multiply 0*10+1*9+3*8+3*7+7*6+7*5+6*4+7*3+4*2 = 184
184 mod 11 = 8
Thus, 11-8=3 is the correct remainder, so it must be correct.

Design:
start
    input number
    while number length is not 10             //validate length
           input number
    endwhile
    set index=0
    while index < 9 then                           //skip the last digit
           if number[index] is digit then
               total=total+number[index]*(10-index)         //accumulator
           else
                output "Not a digit, bye"                 //validate each digit
                exit program with code 1
           index=index+1
   endwhile
   total=total mod 11
   if total eq 10 then               //show 0 for remainder 10     
       output "The check digit is: "+0
   else
       output "The check digit is: "+11-total
   endif
stop


Code:
import java.util.Scanner;




/** Application to calculate ISBN-10 check digit
 @author Zoltan Szabo
 @version 1.0.0
*/
public class MyISBN10{
public static void main(String args[]){
    Scanner kbd=new Scanner(System.in);
    String isbn;
    int total=0;
    System.out.print("Please, enter an ISBN-10 number: ");
    isbn=kbd.nextLine();
    while(isbn.length()!=10){  //validate input length
        System.out.println("This application can only handle ISBN-10, do not type more than 10 digits.");
        System.out.print("Again: Please, enter an ISBN-10 number: ");
        isbn=kbd.nextLine();
    }
    for(int index=0;index<9;index++){   //process one digit at a time
        if(Character.isDigit(isbn.charAt(index)))  //validate if number was read
           total+=Integer.parseInt(isbn.substring(index,index+1))*(10-index);
         else{
            System.out.print("Not a digit, bye!");
            System.exit(1);
            }
    }
    System.out.print("The check digit is: "+(((total%11)==10)?0:11-(total%11)));
}
}

Test: ( not just valid, but also invalid inputs )

Please, enter an ISBN-10 number: 0133776743
The check digit is: 3
Please, enter an ISBN-10 number: as0133776743
This application can only handle ISBN-10, do not type more than 10 digits.
Again: Please, enter an ISBN-10 number: 01337767aa
Not a digit, bye!

Challenge:  Do the same for ISBN-13

Don't Even Think about a Job Interview without Knowing these Sort Algorithms

Sorting is an essential part of working with data today.  Data access and analysis is much less time consuming if the data itself is sorted first.  Unsorted data is very silent while sorted data can be questioned and fast response is possible.  If you want to find the smallest and largest values from an unsorted data, it might take a very long time ( It might be as bad as O(n^2) ), but asking the same question from a sorted data can be as quick as O(1) since you just have to take the first and last element of the sorted structure.  Yes, it takes time and work to sort the data, but that extra work ahead of time, before the question is asked, is more than worth the effort.  Sorting can be accomplished in many different way with different time complexities.

·        Bubble sort

·        Selection sort

·        Insertion sort

·        Merge sort

·        Quick sort

Performance tests must be performed and studied in order to chose the correct one when the time comes.  It is not the time to test when the job needs to be done.

99
N Time:                                   00:00:00:0002
99
N-quare Time:                         00:00:20:20446
99
BubbleSort based Time:          00:00:26:26496
99
SelectionSort based Time:      00:00:04:4924
99
InsertionSort based Time:       00:00:02:2467
99
MergeSort based Time:          00:00:00:0014
99
QuickSort based Time:          00:00:00:0008

Aiming for your dream job will require you to understand the methodology, code, and operational characteristics or these algorithms.  So, spend lots of time analyzing and studying these algorithms and run the code for performance analysis.  This will be one of your greatest assets and skills that will get you your dream job and will allow you to keep your dream job for a long time.

public class BiggestDifference {
    public static void main(String[] args){
        final int SIZE=10000;
        int myArray[]= new int[SIZE];
        initialize(myArray);
        long time=System.currentTimeMillis();
        System.out.println(diffItN(myArray));
        System.out.printf("N Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
        time=System.currentTimeMillis();
        System.out.println(diffItNN(myArray));
        System.out.printf("N-quare Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
        time=System.currentTimeMillis();
        System.out.println(diffItNLogN(myArray,"bubble"));
        System.out.printf("BubbleSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
        initialize(myArray);
        time=System.currentTimeMillis();
        System.out.println(diffItNLogN(myArray,"selection"));
        System.out.printf("SelectionSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
        initialize(myArray);
        time=System.currentTimeMillis();
        System.out.println(diffItNLogN(myArray,"insertion"));
        System.out.printf("InsertionSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
        initialize(myArray);
        time=System.currentTimeMillis();
        System.out.println(diffItNLogN(myArray,"merge"));
        System.out.printf("MergeSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
        initialize(myArray);
        time=System.currentTimeMillis();
        System.out.println(diffItNLogN(myArray,"quick"));
        System.out.printf("QuickSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
    }

    private static void initialize(int a[]){       
        java.util.Random ran=new java.util.Random();
        for(int i=0;i<a.length;i++){
            a[i]=ran.nextInt(100);
        }
    }

    private static int diffItN(int a[]){
        int largest=a[0];
        int smallest=a[0];
        for(int i=1;i<a.length;i++){
            if(a[i]>largest)
                largest=a[i];
            if(a[i]<smallest)
                smallest=a[i];
        }
        return largest-smallest;
    }

    private static int diffItNN(int a[]){
        int difference = 0,diff=0;
        for(int n1:a){
            for (int n2:a){
                difference = n1 - n2;
                if(difference > diff)
                    diff = difference;
            }
        }
        return diff;
    }

    private static int diffItNLogN(int a[],String s){
        switch(s){
            case "bubble":
                bubbleSort(a);
                break;
            case "selection":
                selectionSort(a);
                break;
            case "insertion":
                insertionSort(a);
                break;
            case "merge":
                mergeSort(a);
                break;
            case "quick":
                quickSort(a,0,a.length-1);
                break;
        }
        return (a[0]>a[a.length-1])?a[0]-a[a.length-1]:a[a.length-1]-a[0];
    }

    private static void bubbleSort( int [ ] num ) {
        int j;
        boolean flag = true;  
        int temp; 
        while ( flag ){
            flag= false;   
            for( j=0;  j < num.length -1;  j++ ) {
                if ( num[ j ] < num[j+1] )   {
                    temp = num[ j ];               
                    num[ j ] = num[ j+1 ];
                    num[ j+1 ] = temp;
                    flag = true;             
                }
            }
        }
    }

    private static void selectionSort ( int []num ){
        int i, j, first, temp; 
        for ( i = num.length - 1; i > 0; i-- ) {
            first = 0;  
            for(j = 1; j <= i; j ++){
                if( num[ j ] < num[ first ] )        
                    first = j;
            }
            temp = num[ first ];  
            num[ first ] = num[ i ];
            num[ i ] = temp;
        }          
    }

    private static void insertionSort(int array[]) { 
        int n = array.length; 
        for (int j = 1; j < n; j++) { 
            int key = array[j]; 
            int i = j-1; 
            while ( (i > -1) && ( array [i] > key ) ) { 
                array [i+1] = array [i]; 
                i--; 
            } 
            array[i+1] = key; 
        } 
        System.out.println();
    } 

    private static void mergeSort(int [ ] a){
        int[] tmp = new int[a.length];
        mergeSort(a, tmp,  0,  a.length - 1);
    }

    private static void mergeSort(int [ ] a, int [ ] tmp, int left, int right){
        if( left < right ){
            int center = (left + right) / 2;
            mergeSort(a, tmp, left, center);
            mergeSort(a, tmp, center + 1, right);
            merge(a, tmp, left, center + 1, right);
        }
    }

    private static void merge(int[ ] a, int[ ] tmp, int left, int right, int rightEnd ){
        int leftEnd = right - 1;
        int k = left;
        int num = rightEnd - left + 1;

        while(left <= leftEnd && right <= rightEnd)
            if(a[left]<a[right])
                tmp[k++] = a[left++];
            else
                tmp[k++] = a[right++];

        while(left <= leftEnd)  
            tmp[k++] = a[left++];

        while(right <= rightEnd)
            tmp[k++] = a[right++];

        for(int i = 0; i < num; i++, rightEnd--)
            a[rightEnd] = tmp[rightEnd];
    }

    private static void quickSort(int a[], int lowerIndex, int higherIndex) {
        int i = lowerIndex;
        int j = higherIndex;
        int pivot = a[lowerIndex+(higherIndex-lowerIndex)/2];
        while (i <= j) {
            while (a[i] < pivot) {
                i++;
            }
            while (a[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(a,i, j);
                i++;
                j--;
            }
        }
        if (lowerIndex < j)
            quickSort(a,lowerIndex, j);
        if (i < higherIndex)
            quickSort(a,i, higherIndex);
    }

    private static void exchangeNumbers(int a[],int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static String getTime(long millis){
        long second = (millis / 1000) % 60;
        long minute = (millis / (1000 * 60)) % 60;
        long hour = (millis / (1000 * 60 * 60)) % 24;
        return String.format("%02d:%02d:%02d:%04d", hour, minute, second, millis);
    }
}

BigInteger - Size Matters

As numbers get larger, you need to consider storing those values where a 64 bit data type is not enough.  Working with large numbers are fun even if the operators do not work as excepted with small numbers.

Java provides classes like java.math.BigInteger or java.math.BigDecimal to handle large numbers, but it takes some time getting used to.  

You don't just add values by using the plus operator ( + ) , you call methods like add(), multiply(), divide(), subtract() methods.

Comparing values are also a challenge.  You really need to read the API in order to know what to expect. 

compareTo() method documentation - "Compares this BigInteger with the specified BigInteger. This method is provided in preference to individual methods for each of the six boolean comparison operators (<, ==, >, >=, !=, <=). The suggested idiom for performing these comparisons is: (x.compareTo(y) <op> 0), where <op> is one of the six comparison operators."

The code below demonstrates the for loop operations using BigInteger.


public class LargeNumbers{
    public static void main(String args[]){
        final java.math.BigInteger NUM=new java.math.BigInteger("10000000");
        //final java.math.BigInteger NUM=new java.math.BigInteger("100000000");
        //final java.math.BigInteger NUM=new java.math.BigInteger("1000000000");
        //System.out.println(NUM.bitCount());  //check to see how many bits are used in the number
        long time=System.currentTimeMillis();
        System.out.println(calc(NUM));
        System.out.printf("Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
    }

    //iterative recursion
    public static java.math.BigInteger calc(java.math.BigInteger n) {
        java.math.BigInteger result =new java.math.BigInteger("1");
        for (java.math.BigInteger t=n; t.compareTo(new java.math.BigInteger("1")) != 0; t=t.subtract(new java.math.BigInteger("1")))
             result = result.add(t);
        return result;
    }

    private static String getTime(long millis){
        long second = (millis / 1000) % 60;
        long minute = (millis / (1000 * 60)) % 60;
        long hour = (millis / (1000 * 60 * 60)) % 24;
        return String.format("%02d:%02d:%02d:%04d", hour, minute, second, millis);
    }
}

Head or Tail, Who the Factorial Cares?

Based on the blog post http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044
the obvious question came up to see if the performance really noticeable and worth worrying about.  It seems that Oracle does not really concerned about the issue.  In this case, it is not the speed of the algorithm that is an issue, but the limited size of the stack that needs to be used in an optimized manner in order to avoid stack overflow condition.  Based on the code below, my tests show head recursion performs a little bit better than the suggested tail recursion ( when the StarkOverflowError is thrown ).  Over all, it seems like the glory goes to iterative recursion method and not head or tail argument. 

Note: I know that factorial is not what this code is testing, multiplication rises much too fast, so it was replaced, on purpose, by addition operations.


public class TestUtilization{
    public static void main(String args[]){
        final long NUM=5350;    //tailFactorial becomes unstable around 5250-5300, headFactorial 5300-5350
        long time=System.currentTimeMillis();
        System.out.println(IterativeFactorial(NUM));
        System.out.printf("Iterative implementation  time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
        time=System.currentTimeMillis();
        System.out.println(headFactorial(NUM));
        System.out.printf("Head Factorial  time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));  
        /*time=System.currentTimeMillis();
        System.out.println(tailFactorial(NUM));
        System.out.printf("Tail Call Optimization time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
         */ 
    }
    //Tail Call Optimization
    public static long tailFactorial (long x){
        if (x == 0)
            return 1;
        return tailFactorial(x,1);
    }
    public static long tailFactorial (long x, long current_factorial){
        if (x == 0)
            return current_factorial;
        return tailFactorial(x - 1, current_factorial + x);
    }
    //head recursion
    public static long headFactorial (long x){
        if (x == 0)
            return 1;
        return x+headFactorial(x-1);
    }
    //iterative implementation
    public static long IterativeFactorial(long n) {
        long result = 1;
        for (long t=n; t > 1; t--)
            result += t;
        return result;
    }
    private static String getTime(long millis){
        long second = (millis / 1000) % 60;
        long minute = (millis / (1000 * 60)) % 60;
        long hour = (millis / (1000 * 60 * 60)) % 24;
        return String.format("%02d:%02d:%02d:%04d", hour, minute, second, millis);
    }
}

ArrayList Processing Performance Test

There are many ways to skin a cat, but only six ways to process an ArrayList.  Thus, let's test the performance of each method.  Run it on your system and let us know about your results. Please, give a basic system info if you post.  Thanks!

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;


public class ArrayListSpeedTest {

    public static void main(String[] args) {
        long time=System.currentTimeMillis();
        ArrayList<String> colors=new ArrayList<>();

        for(int i=0;i<100000;i++){  //create a bunch of items for the list, change the value if needed
            colors.add("Red"+i);
        }

        System.out.printf("Initializing ArrayList time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));   
        time=System.currentTimeMillis();
       
        for(int i=0;i<colors.size();i++);
        //System.out.println(colors.get(i)+" ");
        System.out.printf("Simple for loop: %32s\n",(getTime(System.currentTimeMillis()-time)));   
        time=System.currentTimeMillis();
       
        for(String color:colors);
        //System.out.println(color+" ");
        System.out.printf("Enhanced for loop time: %25s\n",(getTime(System.currentTimeMillis()-time)));   
        time=System.currentTimeMillis();
       
        int i=0;
        while(i++<colors.size());
           //System.out.println(colors.get(i++)+" ");
        System.out.printf("While loop time: %32s\n",(getTime(System.currentTimeMillis()-time)));   
        time=System.currentTimeMillis();
       
        //Iterator - hasNext, next, remove
        Iterator<String> iterator = colors.iterator();
        while(iterator.hasNext())iterator.next();
             //System.out.println(iterator.next()+" ");
        System.out.printf("While loop Iterator time: %23s\n",(getTime(System.currentTimeMillis()-time)));   
        time=System.currentTimeMillis();
       
        //ListIterator - hasNext, next, remove, hasPrevious, previous, add
        ListIterator<String> lIterator = colors.listIterator();
        while(lIterator.hasNext())lIterator.next();
             //System.out.println(lIterator.next()+" ");
        System.out.printf("While loop ListIterator time: %19s\n",(getTime(System.currentTimeMillis()-time)));   
        time=System.currentTimeMillis();
        //Java 8 Stream
        colors.forEach((color)->{});
               //System.out.println(color+" ");});
        System.out.printf("ForEach Stream time: %28s\n",(getTime(System.currentTimeMillis()-time)));   
        time=System.currentTimeMillis();
       
        String name="\n6 Ways to process an ArrayList and speed performance test by Zoltan Szabo";
        name.toUpperCase().chars().forEach(s->{
            System.out.print((char)s);
        });
    }
   
    private static String getTime(long millis){
        long second = (millis / 1000) % 60;
        long minute = (millis / (1000 * 60)) % 60;
        long hour = (millis / (1000 * 60 * 60)) % 24;
        return String.format("%02d:%02d:%02d:%04d", hour, minute, second, millis);
}
}