Wednesday 26 February 2014

Infix to Postfix and Prefix conversion

Question :

Question is simply to covert a given infix expression to both prefix as well as postfix notation. The postfix part of the question is picked up from the code chef question --> Transform the Expression . I have simply extended it to output prefix part as well.

Code :

package CodeChef;

import java.util.Stack;

/**
 * Created by Aniket on 2/23/14.
 */
public class PostFixConverter {

    public static void main(String args[]){
        String infix = "((a+b)*(z+x))";
        System.out.println("Postfix : " + printPostFix(infix));
        System.out.println("Prefix : " + printPreFix(infix));

    }

    public static String printPostFix(String str){
        Stack stack = new Stack();
        String postfix = "";
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(Character.isLetter(c)){
                postfix = postfix + c;
            }
            else if(c == '('){
                continue;
            }
            else if(c == ')'){
                postfix = postfix + ((Character)stack.pop()).toString();
            }
            else{
                stack.push(c);
            }
        }
        return postfix;

    }

    public static String printPreFix(String str){
        Stack stack = new Stack();
        String prefix = "";
        for(int i=str.length()-1;i>=0;i--){
            char c = str.charAt(i);
            if(Character.isLetter(c)){
                prefix = ((Character)c).toString() + prefix;
            }
            else if(c == '('){
                prefix = ((Character)stack.pop()).toString() + prefix;
            }
            else if(c == ')'){
                continue;
            }
            else{
                stack.push(c);
            }
        }
        return prefix;

    }

}


Output :

Postfix : ab+zx+*
Prefix : *+ab+zx

Note :

 Note that the expression provided as input is well bracketed input and hence we are not taking care of ordering. If the question asks for ordering then you need to take care of that as well. For example if infix expression in a+b*c answer(post fix) would be abc*+ and not ab+c*.

MCQ #14

Question : 

There are two code snippets given below. You have to predict output for both.

First :

String str1="str";
String str2="ing";
String concat=str1+str2;

System.out.println(concat=="string");

Second :

final String str1="str";
final String str2="ing";
String concat=str1+str2;

System.out.println(concat=="string");

In both case answer will be either true or false.

Answer : 

Answer is 1st case is false.
Answer in 2nd case is true.

Explanation :

When Java code is compiled, compiler does some optimizations of it's own. An expression that is know to not change during runtime is know as compile time constant expression. So lets say if you have a String
String concat = "str" + "ing";
after compilation it becomes
String concat = "string";
So if question is framed like how many String instances are created in above java code then the answer is one. String literals are interned. So lets come to our problem

  1. (False)In first case Strings are not final. Also as we know String is immutable in nature. Concatenation of two String literals yields a new String instance and hence the answer on comparison would be false.
  2. (True)In second case Strings are defined as final. That equivalently means the Strings will not change at runtime and hence they form compile time constant expression. So when the code is compiled concat actually points to "string" literal(which is interned as all String literals are). Now since we are comparing this with another String literal with same content both will point to same String instance in the String pool. So the answer in this case would be true.   

Important Links

  1. Difference between using == operator and equals() method in Java
  2. Comparing strings with == which are declared final in Java
  3. how many java String objects will be created in the statement String s=“abc”+“xyz”

Monday 24 February 2014

Mounting Solaris NFS Share on Linux(Ubuntu)

Basics

  1. When we say we are sharing/mounting partition of one machine on another machine there are some prerequisites that must be first understood and taken care of. First of all both machines must be connected via some network or in other terms both machine must be accessible to each other. How do we check that? -> Simply open command prompt and execute

    ping IPAddress of other machine (Eg. ping 192.168.1.202)

    If the ping is successfull in both ways we are good to proceed.
  2. To fully understand point mentioned above it is important to know that mounting a partition to another machine essentially involves a server-client architecture. The machine whose partition is to be share acts as a server where as machine on which the partition is to be mounted acts as a client.
  3. When we say we have server-client architecture what immediately comes into mind is what rules govern the communication between server and client. More precisely it is called protocol. For eg. files can be shared over FTP(File transfer protocol). For mounting partitions over network we have different set of protocols. Most commonly used are Network File System (NFS) for Linux and Common Internet File System (CIFS) for Windows.
  4. As long as we are on mounting topic it would be beneficial to revise mount and umount System calls as they will be used later.

Before we proceed to see how Solaris partition/share is mounted on a Linux machine you may want to go though how Linux share is mounted on another Linux machine. Following link also provides the basics like installing portmap, understanding exports, mount, umount etc.

How To Set Up an NFS Mount on Ubuntu 12.04 


Mounting Solaris NFS Share on Linux

  1. Create directory on your Solaris machine which you wish to share. Next provide permissions to that directory. You can either use chmod command or you can change permissions from file properties.

  2. By default Solaris or rather mostly all unix based systems have Bourne shell(sh). If you are more comfortable with Bourne Again Shell(bash) like me you can easily switch to it. Steps provided in screen shot below -

  3. Next step is to check if NFS server is up and running. For that you can execute following command in the console -

    svcs | grep nfs

    If you get the output as shown in the screen shot below you are good to proceed. If not then you have to start the nfs server. You can do that with following command -

    svcadm -v enable network/nfs/server
    Similar command goes for disabling the server

    svcadm -v disable network/nfs/server

    Info :
    svcs :- report service status
    For more info execute man svcs on console
    svcadm :- System administation command. Manipulate service instance.
    For more info execute man svcadm on console
  4. Next you need to make an entry of the directory you are going to share in the file /etc/dfs/dfstab. Add following lines to the file and save.(Note : You need su privileges to edit the file).

    #share [-F nfs] [-o specific-options] [-d description] pathname
    share  -F nfs -o rw -d "TestDescription" /Desktop/aniket/mount


  5. Save the changes above and restart the server.Infact for any further changes in this file to take effect you will have to bring down the server amd restart.

    svcadm -v disable network/nfs/server
    svcadm -v enable network/nfs/server
    After restarting the server you can check that that the entry is successfull by executing command - share.
    If you are able to see the entry, execute the command - shareall.
    This will inform your server that the directory represented by the entry made can be shared over the network.
  6. That is all for server(Solaris) side. Now lets move on to Client(Linux/Ubuntu) side. Here you simply need to execute mount system call.

    sudo mount -vt  nfs 192.168.1.202:/Desktop/aniket/mount /home/aniket/SolarisShared/mount/

    or if you wish to remount you can do

    sudo mount -o remount -vt  nfs 192.168.1.202:/Desktop/aniket/mount /home/aniket/SolarisShared/mount/

    By syntax you must have guessed the format is

    mount -vt nfs serverIP:/serverDirPath localDirPath

  7. Finally you can see if the directory is really mounted/mapped. You can see it physically or use the command - mount




Thats all! Let me know if there are any further doubts.

Saturday 22 February 2014

Lowest Common Ancestor in a Binary Search Tree.

Question : 

Given values of two nodes in a Binary Search Tree, write a c program to find the Lowest Common Ancestor (LCA). You may assume that both the values exist in the tree. (GeeksForGeeks)

LCA(Lowest Common Ancestor) :


Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself). 

The LCA of n1 and n2 in T is the shared ancestor of n1 and n2 that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor. (Source Wiki

Example :





For example, consider the BST in diagram, LCA of 10 and 14 is 12 and LCA of 8 and 14 is 8.


Solution :

We can solve this problem using BST properties. We can recursively traverse the BST from root. The main idea of the solution is, while traversing from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 or same as one of the n1 or n2, is LCA of n1 and n2 (assuming that n1 < n2). So just recursively traverse the BST in, if node's value is greater than both n1 and n2 then our LCA lies in left side of the node, if it's is smaller than both n1 and n2, then LCA lies on right side. Otherwise root is LCA (assuming that both n1 and n2 are present in BST)

Code : 

package Tree;

/**
 * Created by Aniket on 2/22/14.
 */
public class LCAFinder {

    public static TreeNode findLCA(TreeNode root, int n1,int n2){

        if(root == null){
            return null;
        }

        int data = root.getData();
        if(data > n1 && data > n2){
            return findLCA(root.getLeftNode(),n1, n2);
        }

        if(data < n1 && data < n2){
            return findLCA(root.getRightNode(), n1, n2);
        }
        return root;
    }

    public static void main(String args[]){

        TreeNode root = new TreeNode(20);

        TreeNode l = new TreeNode(8);
        TreeNode r = new TreeNode(22);

        TreeNode ll = new TreeNode(4);
        TreeNode lr = new TreeNode(12);

        TreeNode lrl = new TreeNode(10);
        TreeNode lrr = new TreeNode(14);

        root.setLeftNode(l);
        root.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        lr.setLeftNode(lrl);
        lr.setRightNode(lrr);

        System.out.println("LCA : " + findLCA(root,10,14).getData());
    }
}

Output : 

LCA of Node with data 10 and 14 : 12
(You can similarly execute the code for 8 and 14( Answer is 8))

Important Links : 

  1. Lowest common ancestor
  2. How to find the lowest common ancestor of two nodes in any binary tree?
  3.  Lowest Common Ancestor in a Binary Tree. (OSFG)



Friday 21 February 2014

Sort a stack using recursion in Java

Question : 

Sorting a Stack using push,pop,isEmpty and peek.

Code :

 package SortingTechniques;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/2/14
 * Time: 11:02 AM
 */
public class StackSort {

    public void sortStack(Stack<Integer> stack){

        int no = stack.pop();
        if(stack.size() != 1){
            sortStack(stack);
        }
        insert(stack,no);
    }

    private void insert(Stack<Integer> stack, int no){

        if(stack.size() == 0){
            stack.push(no);
        }
        else{
            int newPeakedNo = stack.peek();
            if(no >= newPeakedNo){
                stack.push(no);
            }
            else{
                int newPoppedNo = stack.pop();
                insert(stack, no);
                stack.push(newPoppedNo);
            }
        }
    }

    public static void main(String args[]){

        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(4);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        System.out.println("Stack Before Sort : " + Arrays.toString(stack.toArray()));
        new StackSort().sortStack(stack);
        System.out.println("Stack After Sort : " + Arrays.toString(stack.toArray()));

    }

}



Output :

Stack Before Sort : [5, 4, 3, 2, 1]
Stack After Sort : [1, 2, 3, 4, 5]


Note :

A similar question was solver in previous post about how to reverse a Stack in Java. It has similar logic. 

Counting Sort in java

Background

 Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Code :

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/2/14
 * Time: 8:03 PM
 */
public class CountingSort {


    public int[] sort(int[] array) {

        int maxValue = getMaxValue(array);
        return countingSort(array,maxValue);

    }

    public int[] countingSort(int[] input, int maxValue){

        int[] countArray = new int[maxValue+1];
        for(int no : input){
            countArray[no] = countArray[no] + 1;
        }

        for(int i=1;i<countArray.length;i++){
            countArray[i] = countArray[i] + countArray[i-1];
        }

        int[] output = new int[input.length];

        for(int i=output.length-1;i>=0;i--){

            output[countArray[input[i]]-1] = input[i];
            countArray[input[i]] = countArray[input[i]] -1;

        }

        return output;

    }


    private int getMaxValue(int[] array){

        int maxValue = Integer.MIN_VALUE;
        for(int no : array){
            if(no > maxValue){
                maxValue = no;
            }
        }
        return maxValue;
    }


    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        System.out.println("Array after Sort : " + Arrays.toString(new CountingSort().sort(array)));

    }

}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]


 NOTE : The modified count array indicates the position of each object in the output sequence.


Time Complexity

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space:
O(n+k)

Related Links

Quick Sort in Java

Background

 Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.

Steps :

  1. Pick an element, called a pivot, from the array.
  2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Code :

import java.io.IOException;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 19/2/14
 * Time: 8:32 PM
 */
public class QuickSort {

    public void quickSort(int[] array, int start, int end){
        int i = start;
        int j = end;

        int pivot = array[(start + end)/2];

        while (i <= j) {

            while (array[i] < pivot) {
                i++;
            }

            while (array[j] > pivot) {
                j--;
            }

            if (i <= j) {
                swap(array, i, j);
                i++;
                j--;
            }
        }

        if (start < j)
            quickSort(array, start, j);
        if (i < end)
            quickSort(array, i, end);
    }

    public static void swap(int[] array, int index1, int index2){

        if(index1 == index2)
            return;

        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;

    }

    public static void main(String args[]) throws IOException {

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new QuickSort().quickSort(array,0,array.length-1);
        System.out.println("Array after Sort : " + Arrays.toString(array));

    }
}


Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]


 Complexity

Quick sort like merge sort has an average complexity of O(Nlog N)


Worst-case analysis

The most unbalanced partition occurs when one of the sublists returned by the partitioning routine is of size n − 1. This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations when all the elements are equal.

If this happens repeatedly in every partition, then each recursive call processes a list of size one less than the previous list. Consequently, we can make n − 1 nested calls before we reach a list of size 1. This means that the call tree is a linear chain of n − 1 nested calls. The ith call does O(n − i) work to do the partition, and , so in that case, Quicksort takes O(n²) time.

Best-case analysis

In the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only log2 n nested calls before we reach a list of size 1. This means that the depth of the call tree is log2 n. But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only O(n) time all together (each call has some constant overhead, but since there are only O(n) calls at each level, this is subsumed in the O(n) factor). The result is that the algorithm uses only O(n log n) time.

Average-case analysis

To sort an array of n distinct elements, quicksort takes O(n log n) time in expectation, averaged over all n! permutations of n elements with equal probability. We list here three common proofs to this claim providing different insights into quicksort's workings.

Other Info

 As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. Python uses Timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm in Java SE & on the Android platform, and in GNU Octave.

Related Links

Merge Sort in java

Background

 Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Conceptually it works as follows - 

  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce newly sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Code :

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 12/2/14
 * Time: 11:24 AM
 */
public class MergeSort {

    public void sort(int[] array) {
        mergeSort(array,0,array.length-1);

    }

    private void mergeSort(int[] array, int start, int end){

        if(start == end){
            return;
        }
        int mid = (start + end)/2;
        mergeSort(array, start, mid);
        mergeSort(array, mid+1, end);
        merge(array,start,mid,end);

    }

    private void merge(int[] array, int start, int mid, int end){

        int[] leftArray = Arrays.copyOfRange(array,start,mid+1);
        int[] rightArray = Arrays.copyOfRange(array,mid+1,end+1);

        int i = 0;
        int j = 0;

        int counter = start;

        while(i<leftArray.length && j<rightArray.length){
            if(leftArray[i] < rightArray[j]){
                array[counter] = leftArray[i];
                i++;
            }
            else {
                array[counter] = rightArray[j];
                j++;
            }
            counter++;
        }

        if(i == leftArray.length){
            while(j != rightArray.length){
                array[counter] = rightArray[j];
                j++;
                counter++;
            }
        }
        else{//j == rightArray.length
            while(i != leftArray.length){
                array[counter] = leftArray[i];
                i++;
                counter++;
            }

        }

    }

    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new MergeSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));

    }

}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]


Complexity

In sorting n objects, merge sort has an average and worst-case performance of O(n log n).

You can visualize it with the following diagram -



Handling very large data

If the data set is very large (large that what can fit into RAM/main memory) then above approach will not work. In that case, you need to do what is popularly known as - 
External merge sort is one such external sorting algorithm
  • Sort chunks that each fit in RAM, then merges the sorted chunks together.
  • First divide the file into runs such that the size of a run is small enough to fit into main memory. Then sort each run in main memory using merge sort sorting algorithm.  
  • Finally merge the resulting runs together into successively bigger runs, until the file is sorted.
Example -
For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

  1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
  2. Write the sorted data to disk.
  3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks (there are 900MB / 100MB = 9 chunks), which now need to be merged into one single output file.
  4. Read the first 10 MB (= 100MB / (9 chunks + 1)) of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
  5. Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally -- because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.


You can use the following approach to sort sorted runs -

Related Links

Insertion Sort in Java

Background

 Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

At any iteration i, elements 0 to i-1 will be sorted and with each increment in i previous list of sorted elements will grow.

Code :

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 12/2/14
 * Time: 11:14 AM
 */
public class InsertionSort {


    public void sort(int[] array) {

        for(int i=1;i<array.length;i++){
            int j = i;
            while(j>0 && array[j-1]>array[j]){
                Swapper.inMemorySwap(array,j-1,j);
                j--;
            }
        }

    }

    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new InsertionSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));

    }
}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]


A slightly better version would be where you don't have to swap numbers every time -

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


Complexity

 Worst case complexity is O(N2) like bubble sort. However the best case is O(N) - already sorted array. Both bubble sort and insertion sort are not suitable for sorting large numbers.

Related Links

Bubble Sort in Java

Background

 In bubble sort the largest elements goes to the end of the array and the remaining array (0 - array.length-i) is sorted again. It's like a bubble where on each iteration largest element goes to the end.

Code : 

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 11/2/14
 * Time: 8:29 PM
 */
public class BubbleSort {

    public void sort(int[] array) {

        int arrayLength = array.length;
        for(int i=0;i<arrayLength;i++){
            for( int j=0;j<arrayLength-i-1;j++){
                if(array[j] > array[j+1]){
                    Swapper.inMemorySwap(array,j,j+1);
                }
            }
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new BubbleSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));

    }

}

Complexity

Bubble sort has worst-case and average complexity both O(n2), where n is the number of items being sorted.

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]


 As we know that bubble sort runs in O(N^2) time complexity. If this question is asked(mostly in the 1st round to make sure you know basic sorting algorithms)  then it will mostly be followed by a counter question. How can you optimize bubble sort ?


Bubble Sort Optimization

If you notice we iterate over all the indexes and for each outer iteration we bubble out the largest number to the end. Now if at some index the array is completely sorted we need to proceed iterating on further indexes. That is precisely what we are going to do. Keep a boolean flag denoting if array is completely sorted or not. At the outer loop initialize it to true and make it false if any iteration of inner for loop happens denoting array is not completely sorted yet. When inner loop does not execute it means array is completely sorted and there is no need to proceed. In this case flag will be true which we initialized in outer loop. If such condition happens i.e if flag is true than break from the loops and print the sorted array.

Code :

package Sorts;

import java.util.Arrays;

/**
 * Created by Aniket on 2/19/14.
 */
public class BubbleSort {

    public void sort(int[] array) {

        int arrayLength = array.length;
        for(int i=0;i<arrayLength;i++){
            boolean isSorted = true;
            for( int j=0;j<arrayLength-i-1;j++){
                if(array[j] > array[j+1]){
                    isSorted = false;
                    Swapper.inMemorySwap(array,j,j+1);
                }
            }
            if(isSorted){
                System.out.println("Breaking at index : " + i);
                break;
            }
        }
    }

    public static void main(String args[]){
        int[] array = new int[]{2,7,5,9,4,7,1,0,1,2,3,};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new BubbleSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));
    }


}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0, 1, 2, 3]
Breaking at index : 7
Array after Sort : [0, 1, 1, 2, 2, 3, 4, 5, 7, 7, 9]



NOTE :  Swapper.inMemorySwap in a normal swap function where data at two indexes are swapper. You can choose to use a temporary variable or not (see swapping of variables in related links section).

Sample method could be -

    public void swap(int[] array, int x, int y) {
         array[x] = array[x] + array[y];
        array[y] = array[x] - array[y];
        array[x] = array[x] - array[y];
    }

Related Links

Saturday 8 February 2014

Finding minimum window containing given subsequence

Question : 

It was long description for a DNA problem. Main DNA sequence(a string) is given (let say strDNA) and another string to search for(let say strPat). You have to find the minimum length window in strDNA where strPat is subsequence. (GeeksForGeeks)

Code : 

package Miscellaneous;

/**
 * Created by Aniket on 2/8/14.
 */
public class SmallestCommonSubSequenceFinder {

    String strDna;
    String strPat;


    char[] patternArray;
    char[] dnaArray;


    int bestLength;
    int bestStart;
    int bestEnd;

    public int getBestEnd() {
        return bestEnd;
    }

    public void setBestEnd(int bestEnd) {
        this.bestEnd = bestEnd;
    }

    public int getBestStart() {
        return bestStart;
    }

    public void setBestStart(int bestStart) {
        this.bestStart = bestStart;
    }

    public int getBestLength() {
        return bestLength;
    }

    public void setBestLength(int bestLength) {
        this.bestLength = bestLength;
    }


    public SmallestCommonSubSequenceFinder(String strDna, String strPat){
        this.strDna = strDna;
        this.strPat = strPat;
        this.patternArray = strPat.toCharArray();
        this.dnaArray = strDna.toCharArray();
    }

    public int getStartIndex(int start){
        for(int i=start;i<dnaArray.length;i++){
            if(dnaArray[i] == patternArray[0]){
                return i;
            }
        }
        return -1;
    }

    public void findMinSubSeqDNAWindow(int start,int currIndex, int comparingIndex, boolean isStart){

        if(start >= dnaArray.length || currIndex >= dnaArray.length){
            return;
        }

        while(currIndex < dnaArray.length && dnaArray[currIndex] != patternArray[comparingIndex]){
            currIndex++;
        }

        //check if currIndex has exceeded the array length

        if(currIndex >= dnaArray.length){
            //element not found
            return;
        }

        if(isStart){
            start = currIndex;
            isStart = false;
        }

        if(comparingIndex == patternArray.length-1){
            int lengthOfSubSeq = currIndex - start + 1;
            if(bestLength == 0 || lengthOfSubSeq < bestLength){
                bestLength = lengthOfSubSeq;
                bestStart = start;
                bestEnd = currIndex;
            }
            //start finding new sub sequence
            findMinSubSeqDNAWindow(start + 1, start + 1, 0, true);
        }
        else {
            //go for next character
            findMinSubSeqDNAWindow(start, currIndex+1, comparingIndex+1, isStart);
        }
    }

    public static void main(String args[]){
        String strPat = "bdf";
        String strDna = "abcdefgbdf";

        SmallestCommonSubSequenceFinder finder = new SmallestCommonSubSequenceFinder(strDna,strPat);
        finder.findMinSubSeqDNAWindow(0,0,0,true);
        System.out.println("Best Length : " + finder.getBestLength());
        System.out.println("BestStart : " + finder.getBestStart());
        System.out.println("Best End : " + finder.getBestEnd());
    }
}



Output :

Best Length : 3
BestStart : 7
Best End : 9

Friday 7 February 2014

Finding Earnings of a Zoo Driver

Question : 

There is a zoo and there are several groups(number of groups:K) of people for tour. Each group is having different size (g1,g2,g3…gK). There is one bus with capacity C. Journey starts from a point and bus will come back to the same point. A group can only be included in the bus if all the members of the groups can be accumulated in bus. After coming back from the tour, each group in the bus will again wait in the queue at the bus-stand. Bus-driver earns a rupee for each person travelled. You have to find the earning of the bus driver after R rounds.

Example : 

Number of groups G = 4

 Group size for each group : 2 4 3 5

 Bus capacity : 7

 Number of rounds R : 4



 queue : (from front side) 2 4 3 5

 First round : 2 4 (we can’t take 3rd group as 3 members can’t be accumulated after 2 and 4.)

 queue : 3 5 2 4 (1st and 2nd group are enqueued. i.e. 2 and 4)

 Second round : 3

 queue : 5 2 4 3

 Third Round : 5 2

 queue : 4 3 5 2

 Fourth Round : 4 3

 After 4 rounds, total earning is 6+3+7+7 = 23.

Code : 

 import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created by Aniket on 2/8/14.
 */
public class ZooDriverEarningsFinder {

    int numberOfGroups;
    int[] groupSizes;
    int busCapacity;
    int noOfRounds;

    public ZooDriverEarningsFinder(int numberOfGroups, int[] groupSizes,int busCapacity,int noOfRounds){
        this.numberOfGroups = numberOfGroups;
        this.groupSizes = groupSizes;
        this.busCapacity = busCapacity;
        this.noOfRounds = noOfRounds;
    }

    public int calculateEarnings(){

        Queue<Integer> groupsQueue = new LinkedList<Integer>();
        for(int grpSize : groupSizes){
            groupsQueue.offer(grpSize);
        }

        int roundsCount = 0;
        int earnings = 0;

        while(roundsCount < noOfRounds){

            int currentCapacity = 0;

            while(currentCapacity <= busCapacity){
                int nextGrpSize = groupsQueue.peek();
                if((currentCapacity + nextGrpSize) <= busCapacity){
                    currentCapacity = currentCapacity + nextGrpSize;
                    groupsQueue.offer(groupsQueue.poll());
                }
                else {
                    //bus is full. Commence journey
                    break;
                }
            }
            //capacity is full. Add earning.
            earnings = earnings + currentCapacity;
            //increment rounds
            roundsCount++;
        }
        return earnings;
    }

    public static void main(String args[]){

        Scanner scanner = new Scanner(System.in);

        //get number of groups
        int numberOfGroups = scanner.nextInt();

       int[] groupSizes = new int[numberOfGroups];

        //get group sizes
        for(int i=0; i<numberOfGroups; i++){
            groupSizes[i] = scanner.nextInt();
        }

        int busCapacity = scanner.nextInt();

        int noOfRounds = scanner.nextInt();

        ZooDriverEarningsFinder earningsFinder = new ZooDriverEarningsFinder(numberOfGroups,groupSizes,busCapacity,noOfRounds);
        System.out.println("Total Earnings : " + earningsFinder.calculateEarnings());
    }
}


Output : 

4
2
4
3
5
7
4
Total Earnings : 23

Search an element in a sorted and pivoted array

Question : 

Link of Question : (GeeksForGeeks)
An element in a sorted array can be found in O(log n) time via binary search. But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.



Algorithm :

Find the pivot point, divide the array in two sub-arrays and call binary search.
The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it.
Using above criteria and binary search methodology we can get pivot element in O(logn) time

  • Input arr[] = {3, 4, 5, 1, 2}
  • Element to Search = 1
  1.  Find out pivot point and divide the array in two 
    sub-arrays. (pivot = 2) /*Index of 5*
  2. Now call binary search for one of the two sub-arrays.
    • If element is greater than 0th element then search in left array
    • Else Search in right array (1 will go in else as 1 < 0th element(3))
  3. If element is found in selected sub-array then return index 
         Else return -1.

Code : 

package Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 5/2/14
 * Time: 12:08 PM
 */
public class RotatedBinarySearcher {

    public int pivotedBinarySearch(int[] array, int no){

        int endIndex = array.length - 1;

        int pivot = findPivot(array,0,endIndex);

        System.out.println("Pivot Index : " + pivot);


        if(pivot == -1){    //Array is just sorted and not rotated
            return binarySearch(array,0,endIndex,no);
        }

        if(array[pivot] == no){
            return pivot;
        }
        else if(array[0] <= no){    //If number is greater than array[0] then it is must be left side of pivot
            return binarySearch(array,0,pivot-1,no);
        }
        else {
            return binarySearch(array,pivot+1,endIndex,no);
        }
    }


    private int findPivot(int [] array, int start, int end){

        if(start > end){
            return -1;
        }

        if(start == end){
            return start;
        }

        int mid = (start + end) / 2;

        if(mid > start && array[mid] < array[mid-1]){
            return mid - 1;
        }
        if(mid < end && array[mid] > array[mid + 1]){
            return mid;
        }

        if(array[mid] <= array[start]){
            return findPivot(array, start, mid-1);
        }
        else {  //array[mid] > array[end]
            return findPivot(array, mid + 1, end);
        }
    }

    private int binarySearch(int[] array, int start, int end, int number){

        if(start > end){
            return -1;
        }

        int mid = (end + start)/2;

        if(array[mid] == number){
            return mid;
        }

        if(number < array[mid]){
            return binarySearch(array, start, mid - 1, number);
        }
        else{
            //number > array[mid]
            return binarySearch(array, mid + 1, end, number);
        }
    }

    public static void main(String args[]){

        int[] array = new int[]{3,4,5,1,2};
        int searchIndex = new RotatedBinarySearcher().pivotedBinarySearch(array,1);
        System.out.println("Number is at index : " + searchIndex);

    }

}



Output : 

Pivot Index : 2
Number is at index : 3

Monday 3 February 2014

Output maximum repeating integer in an array.

Question : 

Given array of N integers ranging from 0 to N-1. Output maximum repeating integer. Use only O(1) memory.

Idea : 

Idea is to iterate over the array. Computer array[i]%N  which will give back the value in array[i]. Now use this computed value as index and add N to the value at that index. Do this for all elements in the array. Return index of the maximum element in the array. If we have a number say X<N appearing M times(Maximum) then we simply add N value M times to the value present at index X which makes it maximum.

Solution : 

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 3/2/14
 */
public class MaxOccurrencesFinder {

    public static int findMqxOccurrenceNumber(int[] array){

        int numberWithMaxOccurrence = 0;
        int indexOfNumberWithMaxOccurrence = 0;

        int arrayLength = array.length;

        for(int i=0;i<arrayLength;i++){
            array[array[i]%arrayLength]  = array[array[i]%arrayLength] + arrayLength;
        }

        for(int i=0;i<arrayLength;i++){
            if(array[i] > numberWithMaxOccurrence){
                numberWithMaxOccurrence = array[i];
                indexOfNumberWithMaxOccurrence = i;

            }
        }

        return indexOfNumberWithMaxOccurrence;

    }

    public static void main(String args[]){

        //array of length 10
        //permitted values 0-9
        int [] array = new int[]{4,6,1,9,2,4,9,1,4,6};
        System.out.println("Max occurred number : " + MaxOccurrencesFinder.findMqxOccurrenceNumber(array));

    }
}  

Output :

 Max occurred number :4
t> UA-39527780-1 back to top