CodeChef problem

Question : 

STATEMENT

There are n events. Each has a start time and end time. You wish to attend maximum of such events.

NOTE:If start time of one event is same as end time of other you cannot attend both. You can imagine some time to travel from event1 to event2.

INPUT

The first line will contain an integer T, denoting the number of test cases.

Each test case contains several lines.

The first line of each test case will contain an integer N, denoting the number of events.

The next N lines, one for each event, contain two space separated integers, starttime and endtime.

1 <= T <= 10
1 <= N <= 10000
0 <= starttime < endtime <= 1000000000

OUTPUT

For each test case, output a single integer denoting the maximal number of events that you can attend.
EXAMPLE
INPUT

2
5
0 5
0 2
3 5
3 4
5 6
6
0 8
8 10
11 12
11 15
2 5
7 9
OUTPUT

3
3
EXPLANATION

In the first case you can attend events (0, 2), (3, 4), (5, 6)

Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

/**
 * 
 * @author athakur
 *
 */
public class Quark1 {

    public static void main(String args[]) throws IOException {
        
         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
         PrintWriter writer = new PrintWriter(System.out,true);
        
         int noOfTestCases = Integer.parseInt(reader.readLine());
        
         for(int i=0; i<noOfTestCases; i++) {
             int noOfEvents = Integer.parseInt(reader.readLine());
             Event[] events = new Event[noOfEvents];
             for(int j=0; j< noOfEvents; j++) {
                 String[] times = reader.readLine().split(" ");
                 events[j] = new Event(Integer.parseInt(times[0]),Integer.parseInt(times[1]));
             }
             writer.println(getMaxEvents(events));
         }
    }
    
    private static int getMaxEvents(Event[] events) {
        Arrays.sort(events);
        int i=0;
        int count = 1;
        for (int j=1; j<events.length;j++) {
            if(events[j].startTime > events[i].endTime) {
                count++;
                i=j;
            }
        }
        return count;
    }
    
    static class Event implements Comparable<Event>
    {
        int startTime;
        int endTime;
        
        public Event(int startTime, int endTime) {
            this.startTime = startTime;
            this.endTime = endTime;
        }

        @Override
        public int compareTo(Event event) {
            return this.endTime > event.endTime ? 1 : (this.endTime < event.endTime ? -1 : 0);
        }
    }
    
}
 

Explanation : 

First we sort the events based on the finish time because we want to attend earliest events first. Now if end times if two events are same we can attend either. So we don't bother about it. On sorting such events can have sequential positioning (one after the other) in either way. Next we start from first event in sorted events list. We can only attend next event if it's start time is greater (mind even equals will not work as we have to consider commute delay) than the end time of current event. Current event is tracked with i variable where as next event is tracked with j.

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

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

Replace the data of each node by the sum of data of all its descendent nodes

Question :

Given a Binary Tree, replace the data of each node by the sum of data of all its descendent nodes.(Leaf nodes will have 0)

 Solution : 

The solution is simple recursive one.  For each node you need to set value of the node equal to the sum of value of it's left and right node. Each sub node will in turn calculate their value and based on sum of their children and return the sum with it's original value added.

Before providing the solution lets view the problem graphically

Before we process the tree lets say it is something like below

 The final result we are interested is 

Lets write the code for it. Note the code for Node data structure as well as various traversals is provided in this post which was poster earlier. There is a slight modification that we are adding and int value instance variable along with its getters ans setters. There is corresponding change in the constructor but the logic remains same.

Code : 

package in.blogspot.osg.Demo;

public class ReplaceWithDescendantSum {
    
    public static int replace(Node root){
        
        int rightValue = 0;
        int leftValue = 0 ;
        
        if(root.getRight() != null)
            rightValue = replace(root.getRight());
        if(root.getLeft() != null)
            leftValue = replace(root.getLeft());
        
        int sumOfDesendants = rightValue + leftValue;
        int retunValue = root.getValue() + sumOfDesendants;
        root.setValue(sumOfDesendants);
        return (retunValue);
        
    }

}

Above code will do the job.

 Lets write the main() method to test this out.

    public static void main(String args[]){
        
        Node root = new Node(1);
        Node l = new Node(2);
        Node r = new Node(3);
        
        Node l1 = new Node(12);
        Node l2 = new Node(13);
        
        Node r1 = new Node(6);
        Node r2 = new Node(8);
        
        root.setLeft(l);
        root.setRight(r);
        
        l.setLeft(l1);
        l.setRight(l2);
        
        r.setLeft(r1);
        r.setRight(r2);
        
        System.out.println("***Before***");
        PreOrder.printPreOrder(root);
        ReplaceWithDescendantSum.replace(root);
        System.out.println("**After**");
        PreOrder.printPreOrder(root);
        
    }

Output : 

 

***Before***
Value : 1
Value : 2
Value : 12
Value : 13
Value : 3
Value : 6
Value : 8
**After**
Value : 44
Value : 25
Value : 0
Value : 0
Value : 14
Value : 0
Value : 0