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;
 }
}

Geometric Counter

Problem: https://www.hackerrank.com/challenges/strange-code
Solution:
Consider the following geometric progression (G.P.): 3,6,12,24,... with first term a = 3 and common ratio r = 2. Some basics
nth term of GP: $$a_n = ar^{n-1}$$
Solving, $$\frac{a_n}{a} = r^{n-1}$$
Taking log of both sides: $$\log_2 \frac{a_n}{a} = (n-1)\log_2 r$$
Now looking at the sample input, it can inferred that the given input t is the sum to nth term of the above GP.
Sum to n terms of GP: $$S_n = a\frac{1 - r^n}{1-r}$$ Solving the above equation,
$$S_n\frac{1-r}{a} = 1 - r^n$$ $$=> r^n = 1 - S_n\left(\frac{1-r}{a}\right)$$ Taking log of both sides:
$$=> n\log_2 r = \log_2 \left(1 - S_n\frac{1-r}{a}\right)$$ $$=> n = \frac{\log_2 \left(1 - S_n\frac{1-r}{a}\right)}{log_2 r}$$ "power" variable in the below program is the n to which the sum has been given as input.
After finding the value of n, we need to find the difference between the given input and the sum to the nth term. The "diff" variable in the below program is that difference.
Then observation on the sample input shows if diff is 0, the next iteration of the counter starts at that point, so the output will be 1. Else, the difference between the (n+1)th term and the input plus 1 is the output.

Java Program:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

int main(){
    long long t;
    cin >> t;
    double tmp = t*(1-2)/3;
    double numerator = 1-tmp;
    int power = log(numerator)/log(2.0);
    long long sum = 3*(1-pow(2, power))/(-1);
    long long diff = t - sum;
    if(diff == 0) {
        cout<<"1"<<endl;
    }
    else {
        long long nextTerm = 3*pow(2,power);
        cout<<nextTerm - (diff - 1)<<endl;
    }
    return 0;
}