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

Trie Data Structure

A trie (or a prefix tree) is a data structure similar to n-ary trees, where each node can have n children. Each child holds a reference to the next n children.

Here an example trie is discussed where some words are stored in the trie.

The TrieNode consists of the following elements:

class TrieNode {
    boolean isWord = false;
    TrieNode[] children = new TrieNode[26];
}

Here each node can have 26 children. Some children may point to null and others may point to the next character in the word.

For example, when the words "home" and "hot" are added to the trie, the state of the trie can be described as follows:
1. The first level will hold 26 children with only the 8th ("h") child holding a non-null reference. Rest of the 25 children will be null.
2. The second level which is the children of "h" will hold 25 null children with only the 15th ("o") child holding a non-null reference.
3. The third level will which is the children of "o" will hold 2 non-null references ("m" and "t") and rest 24 children will be null.
4. The fourth level will have one non-null reference ("e"), which is one of the children of "m", and "t" will hold 26 null references.

Java Code:

package com.sourabh.third;

import java.util.LinkedList;
import java.util.Queue;

class TrieNode {
 boolean isWord = false;
 TrieNode[] children = new TrieNode[26];
 public TrieNode() {
  
 }
 
 public TrieNode(String key) {
  this.add(key);
 }
 
 public boolean contains(String in) {
  TrieNode node = this;
  for(int i=0; i<in.length();i++) {
   TrieNode child = node.children[getAscii(in.charAt(i))];
   if(child == null) {
    // This particular character is not present in the current branch.
    return false;
   }
   else {
    if(in.length() - 1 == i) {
     // We have reached the end of the input string.
     return true;
    }
    else {
     node = child;
    }
   }
  }
  return false;
 }
 
 public void add(String in) {
  if(in.length() == 0) {
   this.isWord = true;
   return;
  }
  else {
   char first = in.charAt(0);
   TrieNode child = children[getAscii(first)];
   if(child == null) {
    child = new TrieNode();
    children[getAscii(first)] = child;
   }
   child.add(in.substring(1));
  }
 }
 
 public int getAscii(char c) {
  char A[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
  int i=0;
  for(i=0;i<A.length;i++) {
   if(A[i] == c) {
    break;
   }
  }
  return i;
 }
}

public class TriePrograms {
 public TrieNode createNode(String word) {
  if(word == null) {
   return new TrieNode();
  }
  else {
   return new TrieNode(word);
  }
 }
 
 public void levelOrderTraversal(TrieNode node) {
  Queue<TrieNode[]> queue = new LinkedList<>();
  if(node == null) {
   return;
  }
  queue.add(node.children);
  int thisLevel = 1;
  int nextLevel = 0;
  while(!queue.isEmpty()) {
   for(int ele = 0; ele < thisLevel; ele++) {
    TrieNode[] childrenAtThisLevel = queue.remove();
    for(int i=0; i<childrenAtThisLevel.length; i++) {
     if(childrenAtThisLevel[i] != null) {
      System.out.print(getChar(i) + ".");
      queue.add(childrenAtThisLevel[i].children);
      nextLevel++;
     }
     else {
      System.out.print(".");
     }
    }
   }
   thisLevel = nextLevel;
   System.out.println();
   for(int i=0;i<26;i++) {
    System.out.print("-");
   }
   System.out.println();
   for(int i=0;i<26;i++) {
    System.out.print("|");
   }
   System.out.println();
   nextLevel = 0;
  }
  thisLevel = nextLevel;
 }
 
 public char getChar(int ascii) {
  char A[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
  return A[ascii];
 }
}

Unit Tests:

package com.sourabh.third;

import org.junit.Assert;
import org.junit.Test;

public class TrieProgramTests {

 TriePrograms instance = new TriePrograms();
 
 @Test
 public void testContains() {
  TrieNode node = instance.createNode(null);
  node.add("home");
  Assert.assertTrue(node.contains("home"));
  node.add("house");
  Assert.assertTrue(node.contains("house"));
  node.add("hot");
  Assert.assertTrue(node.contains("hot"));
  Assert.assertFalse(node.contains("hole"));
 }
 
 @Test
 public void testConstructor() {
  TrieNode node = instance.createNode("home");
  Assert.assertTrue(node.contains("home"));
  node.add("house");
  Assert.assertTrue(node.contains("house"));
  node.add("hot");
  Assert.assertTrue(node.contains("hot"));
  Assert.assertFalse(node.contains("hole"));
 }
 
 @Test
 public void testLevelOrderTraversal() {
  TrieNode node = instance.createNode("home");
  node.add("house");
  node.add("hot");
  instance.levelOrderTraversal(node);
 }
}

Trie printed in level order:

.......h...................
--------------------------
||||||||||||||||||||||||||
..............o............
--------------------------
||||||||||||||||||||||||||
............m.......t.u......
--------------------------
||||||||||||||||||||||||||
....e..................................................................s........
--------------------------
||||||||||||||||||||||||||
..............................e......................
--------------------------
||||||||||||||||||||||||||
..........................
--------------------------
||||||||||||||||||||||||||

Find the smallest window within an array that contains all the elements of another array

Java Program:

package com.sourabh.test;

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

public class MinimumArrayContains {
 class Interval
 {
  private int start;
  private int end;
  public Interval()
  {
   super();
  }
  public Interval(int start, int end) {
   super();
   this.start = start;
   this.end = end;
  }
  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;
  }
 }
 
 Map<Integer, Boolean> map = new HashMap<>();
 Queue<Integer> queue = new LinkedList<>();
 public void resetMap(int... A) {
  for(int i=0;i<A.length;i++) {
   map.put(A[i], false);
  }
 }
 
 public Interval resetQueue() {
  int start = queue.peek();
  int end = 0;
  while(!queue.isEmpty()) {
   end = queue.remove();
  }
  return new Interval(start, end);
 }
 
 public List<Interval> getIntervals(int[] A1, int[] A2) {
  int found = 0;
  int end = 0;
  List<Interval> intervalsContainingAllElementsOfA2 = new ArrayList<>();
  resetMap(A2);
  for(int i=0; i<A1.length; i++) {
   if(map.containsKey(A1[i])) {
    if(map.get(A1[i]) == false) {
     found++;
     map.put(A1[i], true);
    }
    if(queue.peek()!= null && A1[i] == A1[queue.peek()]) {
     queue.remove();
    }
    queue.add(i);
    end = i;
   }
   if(found == A2.length) {
    int start = queue.peek();
    intervalsContainingAllElementsOfA2.add(new Interval(start, end));
    int prevIndex = queue.remove();
    map.put(A1[prevIndex], false);
    found--;
    int currIndex = queue.remove();
    map.put(A1[currIndex], false);
    found--;
    while(currIndex - prevIndex ==1) {
     prevIndex = currIndex;
     currIndex = queue.remove();
     found--;
     map.put(A1[currIndex], false);
    }
    i = currIndex;
    queue.add(currIndex);
    map.put(A1[currIndex], true);
    found++;
   }
  }
  return intervalsContainingAllElementsOfA2;
 }
 
 public Interval getMinimumInterval(int[] A1, int[] A2) {
  List<Interval> intervalsList = getIntervals(A1, A2);
  Interval minInterval = intervalsList.get(0);
  for(Interval interval : intervalsList) {
   if(interval.getEnd() - interval.getStart() < minInterval.getEnd() - minInterval.getStart()) {
    minInterval = interval;
   }
  }
  return minInterval;
 }
}

Unit Tests:

package com.sourabh.test;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.junit.Test;
import org.junit.Assert;
import com.sourabh.test.MinimumArrayContains.Interval;

public class QueueTest {

 Queue<Integer> queue = new LinkedList<>();
 MinimumArrayContains instance = new MinimumArrayContains();
 
 @Test
 public void testQueueFunctions() {
  queue.add(1);
  queue.add(2);
  queue.add(3);
  queue.add(4);
  Assert.assertTrue(queue.peek() == 1);
  Assert.assertTrue(queue.remove() == 1);
  Assert.assertTrue(queue.peek() == 2);
  Assert.assertTrue(queue.remove() == 2);
 }
 
 @Test
 public void testGetMinInterval1() {
  int[] A1 = {1,2,3,1,2,1,4,6,5,4,2,3,4,1};
  int[] A2 = {1,2,4,5};
  Interval interval = instance.getMinimumInterval(A1, A2);
  Assert.assertEquals(4, interval.getStart());
  Assert.assertEquals(8, interval.getEnd());
 }
 
 @Test
 public void testGetMinInterval2() {
  int[] A1 = {6, 7, 1, 3, 2, 4, 5, 2, 3, 1, 2, 5};
  int[] A2 = {1, 3, 5};
  Interval interval = instance.getMinimumInterval(A1, A2);
  Assert.assertEquals(3, interval.getEnd() - interval.getStart());
 }
}

Water in valley one dimensional

Problem:
Given a one dimensional array of integers representing the height of cliffs of a valley, find the total amount of water that can be filled in the valley.

Diagram:

Java Program:

package com.sourabh.test;

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

public class ValleyWater {
 class Valley
 {
  private int start;
  private int end;
  private int water;

  public Valley() {
   super();
  }
  public Valley(int start, int end) {
   super();
   this.start = start;
   this.end = end;
  }
  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 int getWater() {
   return water;
  }
  public void setWater(int water) {
   this.water = water;
  }
 }
 
 public List<Valley> getValleys(int... A) {
  List<Integer> maxima = new ArrayList<>();
  List<Integer> minima = new ArrayList<>();
  List<Valley> valleysList = new ArrayList<>();
  int index = 0;
  for(int i=0;i<A.length - 1;i++) {
   if(A[i+1] > A[i]) {
    minima.add(i);
    index = i;
    break;
   }
   if(A[i+1] < A[i]) {
    maxima.add(i);
    index = i;
    break;
   }
  }
  for(int i=index+1;i+1<A.length;i++) {
   if(A[i+1] < A[i] && A[i] >= A[i-1]) {
    maxima.add(i);
   }
   if(A[i+1] > A[i] && A[i] <= A[i-1]) {
    minima.add(i);
   }
  }
  for(int i = 0; i < maxima.size() - 1; i++) {
   valleysList.add(new Valley(maxima.get(i), maxima.get(i+1)));
  }
  return valleysList;
 }
 
 public int addWater(List<Valley> valleysList, int... A) {
  int totalWater = 0;
  for(Valley valley : valleysList) {
   int min = A[valley.getStart()] < A[valley.getEnd()] ? A[valley.getStart()] : A[valley.getEnd()];
   int water = 0;
   for(int i=valley.getStart(); i<=valley.getEnd(); i++) {
    if(A[i] < min) {
     water += min - A[i];
    }
   }
   valley.setWater(water);
   totalWater += water;
  }
  for(Valley valley : valleysList) {
   System.out.println(valley.getWater());
  }
  return totalWater;
 }
 
 public int getWater(int... A) {
  return addWater(getValleys(A), A);
 }
}

Unit Tests:

package com.sourabh.test;

import static org.junit.Assert.*;

import java.util.List;
import com.sourabh.test.ValleyWater.Valley;
import org.junit.Assert;

import org.junit.Test;

public class ValleyWaterTests {

 ValleyWater instance = new ValleyWater();
 
 @Test
 public void getValleysTest() {
  int[] A = {1,2,3,1,2,1,4,6,5,4,2,3,4,1};
  List<Valley> valleysList = instance.getValleys(A);
  Assert.assertEquals(3, valleysList.size());
  Assert.assertEquals(2,valleysList.get(0).getStart());
  Assert.assertEquals(4,valleysList.get(0).getEnd());
  Assert.assertEquals(4,valleysList.get(1).getStart());
  Assert.assertEquals(7,valleysList.get(1).getEnd());
  Assert.assertEquals(7,valleysList.get(2).getStart());
  Assert.assertEquals(12,valleysList.get(2).getEnd());
 }
 
 @Test
 public void getWaterTest() {
  int[] A = {1,2,3,1,2,1,4,6,5,4,2,3,4,1};
  int totalWater = instance.getWater(A);
  Assert.assertEquals(5, totalWater);
 }
}

Friction on Inclined Plane

Collision

Elastic Collision

A collision of masses where both momentum and energy of the system is conserved before and after the collision.

Conservation of Momentum:

m₁u₁ + m₂u₂ = m₁v₁ + m₂v₂

Conservaation of Energy:

m₁u₁² + m₂u₂² = m₁v₁² + m₂v₂²

Inelastic Collision

A collision of masses where only momentum of the system is conserved before and after the collision.

Conservation of Momentum:

m₁u₁ + m₂u₂ = m₁v₁ + m₂v₂