Tuesday, June 27, 2017

Find the common vacant meeting slot

Problem:
Given the meeting slots of several persons, find the common vacant slot in which all the persons can meet.

Input and Output format:
The first line of input contains a single integer n denoting the number of persons. Next n lines of input contain the start and end time of meetings of each person in HH:MM format separated by a space character.

The first line of output should contain the number of distinct vacant slots followed by those many lines containing the start and end time of each vacant slot in HH:MM format separated by a space character.

Sample Input:
4
08:30 09:00
08:45 09:30
09:00 09:30
10:00 11:00

Sample Output:
3
00:00 08:30
09:30 10:00
11:00 23:59

Java Program:
 
package com.sourabh.first;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class CommonMeeting {
    public static void main(String[] args) {
        int A[] = new int[86401];
        Scanner scanner = new Scanner(System.in);
        int persons = Integer.parseInt(scanner.nextLine());
        List<Integer> meetingStartHour = new ArrayList<>();
        List<Integer> meetingStartMinute = new ArrayList<>();
        List<Integer> meetingStartSecond = new ArrayList<>();
        List<Integer> meetingEndHour = new ArrayList<>();
        List<Integer> meetingEndMinute = new ArrayList<>();
        List<Integer> meetingEndSecond = new ArrayList<>();
        
        List<Integer> vacantStartHour = new ArrayList<>();
        List<Integer> vacantStartMinute = new ArrayList<>();
        List<Integer> vacantStartSecond = new ArrayList<>();
        List<Integer> vacantEndHour = new ArrayList<>();
        List<Integer> vacantEndMinute = new ArrayList<>();
        List<Integer> vacantEndSecond = new ArrayList<>();
        
        for(int i=0;i<persons;i++)
        {
            String meeting = scanner.nextLine();
            //System.out.println(meeting);
            String[] parts = meeting.split(" ");
            String[] start = parts[0].split(":");
            String[] end = parts[1].split(":");
            
            meetingStartHour.add(Integer.parseInt(start[0]));
            meetingStartMinute.add(Integer.parseInt(start[1]));
            meetingStartSecond.add(Integer.parseInt(start[2]));
            
            meetingEndHour.add(Integer.parseInt(end[0]));
            meetingEndMinute.add(Integer.parseInt(end[1]));
            meetingEndSecond.add(Integer.parseInt(end[2]));
        }
        
        for(int i=0;i<persons;i++)
        {
            for(int j = 3600 * meetingStartHour.get(i) 
                        + 60 * meetingStartMinute.get(i)
                        + meetingStartSecond.get(i);
                    j <= 3600 * meetingEndHour.get(i) 
                        + 60 * meetingEndMinute.get(i)
                        + meetingEndSecond.get(i);
                    j++) {
                A[j]=1;
            }
        }
        if(A[0] == 0)
        {
            vacantStartHour.add(0);
            vacantStartMinute.add(0);
            vacantStartSecond.add(0);
        }
        for(int i=0;i<86400;i++)
        {
            if(A[i]==1 && A[i+1]==0)
            {
                vacantStartHour.add(i/3600);
                vacantStartMinute.add((i%3600)/60);
                vacantStartSecond.add(i%60);
            }
            else if(A[i]==0 && A[i+1]==1)
            {
                vacantEndHour.add(i/3600);
                vacantEndMinute.add((i%3600)/60);
                vacantEndSecond.add(i%60);
            }
        }
        if(A[86399] == 0)
        {
            vacantEndHour.add(86399/3600);
            vacantEndMinute.add((86399%3600)/60);
            vacantEndSecond.add(59);
        }
        System.out.println(vacantStartHour.size());
        for(int i=0;i<vacantStartHour.size();i++)
        {
            String vacantSlotStart = format(vacantStartHour.get(i)) + ":" +
                                     format(vacantStartMinute.get(i)) + ":" +
                                     format(vacantStartSecond.get(i));
            String vacantSlotEnd = format(vacantEndHour.get(i)) + ":" +
                                   format(vacantEndMinute.get(i)) + ":" +
                                   format(vacantEndSecond.get(i));
            System.out.println(vacantSlotStart + " " + vacantSlotEnd);
        }
    }
    
    private static String format(Integer time) {
        if(time < 10) {
            return "0" + time;
        }
        else {
            return time.toString();
        }
    }
}

Longest subarray containing all values greater than a given value

Problem:
Given the temperature trends over a number of days, find the longest streak of continuous days having temperatures greater than a given temperature k.

Input and Output format:
The first line of input contains two space separated integers n and k. The second line of input contains n space separated integers denoting the temperatures.

The output should contain three integers denoting the length of the longest streak of days having temperatures greater than k, the starting index of the longest streak and the ending index of the longest streak. Index starts from 1.

Sample Input:
5 30
29 31 28 32 33

Sample Output:
2 4 5

Explanation:
The longest streak of days having temperatures greater than 30 are days 4 and 5 with a length of 2.

Saturday, April 22, 2017

Projectile Motion


Find the minimum number of train platforms needed in each direction

Given the arrival time, departure time and direction of trains, find the minimum number of platforms needed in each direction to accommodate all trains such that no train has to wait.
Arrival time Departure time Direction
11:00 11:15 Up
11:05 11:20 Up
11:00 11:10 Down
11:15 11:25 Down

Sample Output:
2 platforms are needed in Up direction.
1 platform is needed in Down direction.

Vertical Order Traversal of Tree


Java Program using HashMap:
public class TreeTraversalPrograms {
    private static Map<Integer, List<TreeNode>> treeNodeVerticalLevelMap = new TreeMap<>();

    public static void main(String[] args) {
        // Tree construction
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.right.left.right = new TreeNode(8);
        root.right.right.right = new TreeNode(9);

        verticalOrderTraversal(root, 0);
        SortedSet<Integer> keys = new TreeSet<Integer>(treeNodeVerticalLevelMap.keySet());
        for (Integer key : keys) {
            List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(key);
            for (TreeNode treeNode : treeNodesList) {
                System.out.print(treeNode.data + ",");
            }
            System.out.println();
        }
    }
    public static void verticalOrderTraversal(TreeNode node, int width) {
        if (node == null) {
            return;
        }
        if (treeNodeVerticalLevelMap.containsKey(width)) {
            List<TreeNode> treeNodesList = treeNodeVerticalLevelMap.get(width);
            treeNodesList.add(node);
            treeNodeVerticalLevelMap.put(width, treeNodesList);
        } else {
            List<TreeNode> treeNodesList = new ArrayList<>();
            treeNodesList.add(node);
            treeNodeVerticalLevelMap.put(width, treeNodesList);
        }
        if (node.left != null) {
            verticalOrderTraversal(node.left, width - 1);
        }
        if (node.right != null) {
            verticalOrderTraversal(node.right, width + 1);
        }
    }
}

Sample Output:
4,
2,
1,5,6,
3,8,
7,
9,

Thursday, February 9, 2017

Streak of Consecutive Numbers


Given a streak of numbers, find k length block of consecutive numbers
Given an array of 0s and 1s, find k length streak of consecutive 0s or 1s.