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.

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,

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.

Optimal Selfies

On your recent trip with your friends (numbered from 1 to n), you have taken multiple selfies with different subsets of firends. Find the minimal set of photos so that each friend is covered at least once.

Optimised Painting

Problem https://saikatd.wordpress.com/2016/07/03/optimized-painting/
Given the cost of painting different intervals of a wall, find the minimum cost of painting the entire wall.
Java Program

package com.sourabh.first;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class OptimisedPainting {
 public static void main(String[] args) {
  Interval paintInterval = new Interval();
  paintInterval.setStart(0);
  paintInterval.setEnd(5);
  Map<Interval, Integer> unitHashMap = new HashMap<>();
  for(int i=paintInterval.getStart(); i<paintInterval.getEnd(); i++)
  {
   Interval interval = new Interval();
   interval.setStart(i);
   interval.setEnd(i+1);
   unitHashMap.put(interval, 0);
  }
  //String intervalString = "[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]";
  String intervalString = "[1, 4, 10], [2, 5, 6]";
  String[] intervals = intervalString.split("],");
  List<Interval> intervalsList = new ArrayList<>();
  for(int i=0;i<intervals.length;i++)
  {
   String[] parts = intervals[i].split(",");
   Interval interval = new Interval();
   interval.setStart(Integer.parseInt(parts[0].trim().substring(1)));
   interval.setEnd(Integer.parseInt(parts[1].trim().replaceAll(",", "")));
   interval.setCost(Double.parseDouble(parts[2].trim().replaceAll("]", "")));
   intervalsList.add(interval);
  }
  System.out.println("Input");
  for(Interval combination : intervalsList) {
   System.out.println(combination.getStart() + "," + combination.getEnd() + "," + combination.getCost());
  }
  System.out.println("Output");
  OptimisedPainting op = new OptimisedPainting();
  List<List<Interval>> intervalsCombinations = op.generateCombinations(intervalsList, new ArrayList<>(), 0, new ArrayList<>());
  Double minCost = 999999.99;
  for(List<Interval> intervalsCombination : intervalsCombinations) {
   Double cost = 0.0;
   if(op.isValidIntervalList(intervalsCombination, unitHashMap)) {
    for(Interval combination : intervalsCombination) {
     cost += combination.getCost();
    }
    if(minCost > cost) {
     minCost = cost;
    }
   }
   unitHashMap = op.refreshUnitHashMap(paintInterval);
  }
  if(minCost == 999999.99) {
   System.out.println("-1");
  } else {
   System.out.println("Minimum cost: " + minCost);
  }
 }
 
 public Map<Interval, Integer> refreshUnitHashMap(Interval paintInterval) {
  Map<Interval, Integer> unitHashMap = new HashMap<>();
  for(int i=paintInterval.getStart(); i<paintInterval.getEnd(); i++)
  {
   Interval interval = new Interval();
   interval.setStart(i);
   interval.setEnd(i+1);
   unitHashMap.put(interval, 0);
  }
  return unitHashMap;
 }
 
 public boolean isValidIntervalList(List<Interval> intervalsList, Map<Interval, Integer> unitHashMap) {
  for(Interval interval : intervalsList) {
   for(int i=interval.getStart(); i<interval.getEnd(); i++)
   {
    Interval temp = new Interval();
    temp.setStart(i);
    temp.setEnd(i+1);
    unitHashMap.put(temp, 1);
   }
  }
  return !unitHashMap.containsValue(0);
 }
 
 public List<List<Interval>> generateCombinations(List<Interval> intervalsList, 
   List<List<Interval>> intervalsCombinations, int start, List<Interval> outputList) {
  for(int index = start; index < intervalsList.size(); index++) {
   outputList.add(intervalsList.get(index));
   List<Interval> tempList = new ArrayList<>();
   for(Interval interval : outputList) {
    tempList.add(interval);
   }
   intervalsCombinations.add(tempList);
   tempList = null;
   intervalsCombinations = generateCombinations(intervalsList, intervalsCombinations, index+1, outputList);
   outputList.remove(outputList.size() - 1);
  }
  return intervalsCombinations;
 }
}

class Interval {
 private int start;
 private int end;
 private double cost;
 public int getStart() {
  return start;
 }
 public void setStart(int start) {
  this.start = start;
 }
 public int getEnd() {
  return end;
 }
 public void setEnd(int end) {
  this.end = end;
 }
 public double getCost() {
  return cost;
 }
 public void setCost(double cost) {
  this.cost = cost;
 }
 @Override
 public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + end;
  result = prime * result + start;
  return result;
 }
 @Override
 public boolean equals(Object obj) {
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;
  Interval other = (Interval) obj;
  if (end != other.end)
   return false;
  if (start != other.start)
   return false;
  return true;
 }
}