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

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

Print all possible paths from top left to bottom right of a mXn matrix

Question : 

The problem is to print all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.(GeeksForGeeks)

Idea :

The algorithm is a simple recursive algorithm, from each cell first print all paths by going down and then print all paths by going right. Do this recursively for each cell encountered.

Solution :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 30/1/14
 * Time: 4:39 PM
 * To change this template use File | Settings | File Templates.
 */
public class AllPathsPrinter {

    int [][] array;
    int rowCount;
    int colCount;


    public AllPathsPrinter(int [][]array){

        this.array = array;
        rowCount = array.length;
        colCount = array[0].length;

    }


    public void printAllPaths(int currX, int currY, String path){

        if(currX == rowCount-1){
            for(int j=currY;j<=colCount-1;j++){
                path = path + array[currX][j];
            }
            System.out.println("Path : " + path);
            return;
        }

        if(currY == colCount-1){
            for(int i=currX;i<=rowCount-1;i++){
                path = path + array[i][currY];
            }
            System.out.println("Path : " + path);
            return;
        }
        path = path + array[currX][currY];
        printAllPaths(currX+1, currY, path);
        printAllPaths(currX, currY+1, path);

    }

    public static void main(String args[]){

        int [][] ar = new int[][]{{1, 2, 3}, {4, 5, 6}};
        AllPathsPrinter allPathsPrinter = new AllPathsPrinter(ar);
        allPathsPrinter.printAllPaths(0,0,"");


    }


}

Output :

Path : 1456
Path : 1256
Path : 1236

Convert a given Binary Tree to Doubly Linked List

Question:

Given a Binary Tree (Bt), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.(Taken from GeeksForGeeks)

The idea behind its solution is quite simple and straight.

1.  If left subtree exists, process the left subtree
1. Recursively convert the left subtree to DLL.
2. Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
3. Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
1. Recursively convert the right subtree to DLL.
2. Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
3. Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).

 Solution :

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 29/1/14
 * Time: 5:43 PM
 */
public class BTreeToList {

    private static TreeNode btreeToListUtil(TreeNode root){

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

        if(root.getLeftNode() != null){

            TreeNode leftTreeNode = btreeToListUtil(root.getLeftNode());

            while(leftTreeNode.getRightNode() != null){
                leftTreeNode = leftTreeNode.getRightNode();
            }

            leftTreeNode.setRightNode(root);
            root.setLeftNode(leftTreeNode);

        }


        if(root.getRightNode() != null){

            TreeNode rightTreeNode = btreeToListUtil(root.getRightNode());

            while(rightTreeNode.getLeftNode() != null){
                rightTreeNode = rightTreeNode.getLeftNode();
            }

            rightTreeNode.setLeftNode(root);
            root.setRightNode(rightTreeNode);
        }

        return root;

    }

    public static TreeNode btreeToList(TreeNode root){
         TreeNode head = btreeToListUtil(root);
        while(head.getLeftNode() != null){
            head = head.getLeftNode();
        }

        return head;
    }

    public static void printLL(TreeNode root){

        while(root != null){
            System.out.println("Data : " + root.getData());
            root = root.getRightNode();
        }


    }



    public static void main(String args[]){

        TreeNode root = new TreeNode(10);

        TreeNode l = new TreeNode(12);
        TreeNode r = new TreeNode(15);

        TreeNode ll = new TreeNode(25);
        TreeNode lr = new TreeNode(30);

        TreeNode rl = new TreeNode(36);

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

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

        r.setLeftNode(rl);

        printLL(btreeToList(root));

    }

}

Output :

Data : 25
Data : 12
Data : 30
Data : 10
Data : 36
Data : 15