Number of bus-stations

Question: At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be accommodated as per their schedule.
 Example:  Time table is like below:
Bus Arrival Departure
BusA 0900 hrs 0930 hrs
BusB 0915 hrs 1300 hrs
BusC 1030 hrs 1100 hrs
BusD 1045 hrs 1145 hrs
Then the answer must be 3. Otherwise the bus-station will not be able to accommodate all the buses.


Let’s take the same example as described above. Now we have to calculate the number of bus-station, which will be nothing but the maximum number of buses at the bus-station at any time.

So first sort all the arrival(A) and departure(D) time in an int array. Please save the corresponding arrival or departure in the array also. Either you can use a particular bit for this purpose or make a structure. After sorting our array will look like this:
0900 0915 1930 1030 1045 1100 1145 1300 
A A D A A D D D
Now modify the array as put 1 where you see A and -1 where you see D. So new array will be like this:
1 1 -1 1 1 -1 -1 -1 
And finally make a cumulative array out of this:
1 2 1 2 3 2 1 0
Your solution will be the maximum value in this array. Here it is 3.
PS: If you have a arriving and another departing at same time then put departure time first in sorted array.
Solution is here.

How to sort 4GB files

Using merge sort.

Refer here

Count the number of ways

You have n number of chocolates. Your best friend asks for the chocolate but you say that he can take only 1 or maximum 2 chocolates at a time.

Find the number of ways in which your friend can take all the chocolates in any number of times

Answer: Starting from the base level, if we have 3 coins how many ways we could take all 3 coins if we allowed to take single or max 2 coins at once.
So it can be generalized as
no_of_ways(n) = no_of_ways(n-1) + no+_of_ways(n-2);

Liner time Majority Vote Algorithm

You are given a sequence of element. WAP to find which element of the sequence is in Majority, provided there is such a element.

Java Code :

public class LinearTimeMajorityAlgorithm {

 public static void main(String[] args) {
  // find an element which repeats majority times
  int[] a = { 1, 2, 3, 4, 2, 1, 3, 2, 4, 1, 2, 2, 3, 2, 2, 2 };

  if (a.length == 0)
   return;

  int count = 1;
  int maorityTracker = a[0];
  for (int i = 0; i < a.length; i++) {
   if (count == 0) {
    maorityTracker = a[i];
    count = 1;
   } else {
    if (a[i] == maorityTracker) {
     count++;
    } else {
     count--;
    }
   }
  }
  System.out.println("Majority occuring element position is :"
    + maorityTracker);
 }
}

Refer : http://www.geeksforgeeks.org/archives/4722

Boolean paranthesize

Counting Boolean Parenthesizations. You are given a boolean expression consisting of a string of the symbols 'true', 'false', 'and', 'or', and 'xor'. Count the number of ways to parenthesize the expression such that it will evaluate to true. For example, there is only 1 way to parenthesize 'true and false xor true' such that it evaluates to true. 

http://codepad.org/wlvIr0Km

Apple Problem

A table composed of N*M cells,each having a certain quantity of apples, is given. you start from the upper-left corner. At each step you can go down or right one cell.Design an algorithm to find the maximum number of apples you can collect ,if you are moving from upper-left corner to bottom-right corner. 
Here is a code for solving the problem using Dynamic programming :
Java code :

public class AppleProblem {
 public static void main(String[] args) {
  int[][] apples = { { 2, 3, 1 }, { 4, 6, 2 }, { 7, 8, 2 } };

  int rows = apples.length;
  int columns = apples[0].length;

  // Create a temporary array to store the maximum sum upto that position
  int[][] dp = new int[rows][columns];

  int prevRowValue = 0;
  int prevColumnValue = 0;

  for (int i = 0; i < rows; i++) {
   for (int j = 0; j < columns; j++) {

    if (i - 1 < 0)
     prevRowValue = 0;
    else
     prevRowValue = dp[i - 1][j];

    if (j - 1 < 0)
     prevColumnValue = 0;
    else
     prevColumnValue = dp[i][j - 1];

    dp[i][j] = apples[i][j] + max(prevRowValue, prevColumnValue);
   }
  }
  System.out.println(dp[rows - 1][columns - 1]);
 }

 private static int max(int a, int b) {
  return a > b ? a : b;
 }
}

Prims's Algorithm

Prim's algorithm  finds a minimum-cost spanning tree of an edge-weighted, connected, undirected graph . The algorithm constructs the minimum-cost spanning tree of a graph by selecting edges from the graph one-by-one and adding those edges to the spanning tree.
http://compprog.wordpress.com/2007/11/09/minimal-spanning-trees-prims-algorithm/

http://pages.pacificcoast.net/~cazelais/222/prim.pdf