Street Trees

A group of trees is planted along a straight line.
KOI is planning to plant more trees so that the distance between two adjacent trees is equal for all trees.
For simplicity, each tree can only be planted on an integer coordinate.
For example, if 4 trees were originally planted on coordinates (1,3,7,13), and if KOI plants 3 more trees on coordinates (5,9,11), then the distance between two adjacent trees will equal for all trees.
Your task is to calculate the minimal number of trees that KOI can plant so that the distance between two adjacent trees will equal for all trees.
Input :
The first line is an integer N (3<=N<=100,000), which denotes the number of already planted trees.
The next N lines will have an integer X (1<=X<=1,000,000,000), which denotes the coordinate of each tree.
You can safely assume that the value of X will be unique.
Output :
Output the minimal number of trees that must be planted.
Example :
Input: 
4
1  3  7  13
Output:  3
Solution : Get the difference between alternate numbers into an array.Now find out the gcd of all the numbers.GCD is  the minimum distance between the trees.Start from the starting tree and keep on adding gcd to previous number.
Answer : http://www.ideone.com/Cfyr9

No of words in a language

There is a language with only two elements ie 'a' and 'bc'. How many words can be
made out of it if whose Length is n.

Let N(k) be the number of strings of length k. Since you can
make a string of length k by appending 'a' onto a string of length k-1
or by appending 'bc' onto a string of length k-2, it follows that

N(k) = N(k-1) + N(k-2)

Furthermore, there are no strings of length -1 and only one string of
length 0.

Restaurent problem

Yuckdonald's is considering opening a series of restaurants along
Quaint Valley Highway (QVH).The n possible locations are along a
straight line, and the distances of these locations from the start of
QVH are, in miles and in increasing order,m1;m2; : : : ;mn. The
constraints are as follows:
1)At each location,Yuckdonald's may open at most one restaurant.The
expected profi t from opening a restaurant at location i is pi, where
pi > 0 and i = 1; 2; : : : ; n.
2)Any two restaurants should be at least k miles apart, where k is a
positive integer.
Give an effi cient algorithm to compute the maximum expected total
pro fit subject to the given
constraints.

http://codepad.org/DDtJ6yBF

Longest Increasing Subsequence

Given a sequence of n real numbers A(1) ... A(n), determine a subsequence (not necessarily contiguous) of maximum length in which the values in the subsequence form a strictly increasing sequence.


http://codepad.org/C3sr0oF3

Ransom Note

Question:given an arbitrary ransom note string and another string containing all the contents of all the magazines, write a function that will return true if the ransom note can be made from the magazines; otherwise, it will return false. Remember, every letter found in the magazine string can only be used once in your ransom note. For example, if the ransom note string was "no scheme" and the magazine string was "programming interviews are weird", you would return false since you can't form the first string by grabbing and rearranging letters from the second string.


Solution is here.

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