Dynamic Programming - Egg Dropping Puzzle

Dynamic Programming -- Egg Dropping Puzzle

The following is a description of the instance of this famous puzzle involving n=2 eggs and a building with k=36 floors.

Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing.

 We make a few assumptions:

1)An egg that survives a fall can be used again.
2)A broken egg must be discarded.
3)The effect of a fall is the same for all eggs.
4)If an egg breaks when dropped, then it would break if dropped from a higher floor.
5)If an egg survives a fall then it would survive a shorter fall.
6)It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor do not cause an egg to break.

If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second floor window. Continue upward until it breaks.

 In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the least number of egg-droppings that is guaranteed to work in all cases?

The problem is not actually to find the critical floor, but merely to decide floors from which eggs should be dropped so that total number of trials are minimized.

Solution:

When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn’t break.

1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs

2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.

Since we need to minimize the number of trials in worst case, we take the maximum of two cases. We consider the max of above two cases for every floor and choose the floor which yields minimum number of trials.

  k ==> Number of floors
  n ==> Number of Eggs
 
  eggDrop(n, k) ==> Minimum number of trails needed to find the critical floor in worst case.
  eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1) , eggDrop(n, k - x)) :x in {1, 2, ..., k}}

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */

public class EggDropingProblemApp
{
public static int max(int a, int b)
{
return (a > b)? a: b;
}
   public static int eggDrop(int n, int k)
    {
        int eggFloor[][] = new int[n+1][k+1];
        int res;
        int i, j, x;
         
        for (i = 1; i <= n; i++)
        {
            eggFloor[i][1] = 1;
            eggFloor[i][0] = 0;
        }
         
        for (j = 1; j <= k; j++)
            eggFloor[1][j] = j;

        for (i = 2; i <= n; i++)
        {
            for (j = 2; j <= k; j++)
            {
                eggFloor[i][j] = Integer.MAX_VALUE;
               
                for (x = 1; x <= j; x++)
                {
                     res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x]);
                     if (res < eggFloor[i][j])
                        eggFloor[i][j] = res;
                }
            }
        }  
       return eggFloor[n][k];
    }

public static void main(String[] args)
{
     int n = 2, k = 10;
    System.out.println("Minimum number of trials in worst case with "+n+"  eggs and "+k+"                   floors is "+eggDrop(n, k));
}
}

Output: Minimum number of trials in worst case with 2  eggs and 10 floors is 4

Time Complexity:  O(nk^2)
Auxiliary Space: O(nk)

Dynamic Programming - Coin Change

Dynamic Programming -- Coin Change Problem

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, 
for N = 4 and S = {1,2,3},
there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4.
 For N = 10 and S = {2, 5, 3, 6}
 there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.
 So the output should be 5.

 Solution:

 To count total number solutions, we can divide all set solutions in two sets.

1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.

Let count(S[], m, n) be the function to count the number of solutions, then it can be written as sum of count(S[], m-1, n) and count(S[], m, n-Sm).

Sample Code:

import java.util.Arrays;
/**
 * @author Abhinaw.Tripathi
 *
 */
public class CoinChangeApp
{
public static long countWays(int S[], int m, int n)
{
       long[] table = new long[n+1];
       Arrays.fill(table, 0);         // this will take o(n)
       table[0] = 1;

       for (int i=0; i<m; i++)
           for (int j=S[i]; j<=n; j++)
               table[j] += table[j-S[i]];

       return table[n];
}
public static void main(String[] args)
{
int arr[] = {1, 2, 3};
        int m = arr.length;
        int n = 4;
        System.out.println("Output: "  +countWays(arr, m, n));
}
}


Output: 4

Time Complexity:O(mn)

Dynamic Programming - Min Cost Path

Dynamic Programming - Min Cost Path

Given a cost matrix cost[][] and a position (m, n) in cost[][],
write a function that returns cost of minimum cost path to reach (m, n) from (0, 0).

 Each cell of the matrix represents a cost to traverse through that cell. Total cost of a path to reach (m, n) is sum of all the costs on that path (including both source and destination). You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1) and (i+1, j+1) can be traversed. You may assume that all costs are positive integers.

 The path to reach (m, n) must be through one of the 3 cells:
 (m-1, n-1) or (m-1, n) or (m, n-1).

 So minimum cost to reach (m, n) can be written as “minimum of the 3 cells plus cost[m][n]”.

Solution: 

minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class MinCostPathApp
{
private static int min(int x, int y, int z)
{
       if (x < y)
           return (x < z)? x : z;
       else
           return (y < z)? y : z;
 }

private static int minCost(int cost[][], int m, int n)
{
       int i, j;
       int tc[][]=new int[m+1][n+1];

       tc[0][0] = cost[0][0];

       /* Initialize first column of total cost(tc) array */
       for (i = 1; i <= m; i++)
           tc[i][0] = tc[i-1][0] + cost[i][0];

       /* Initialize first row of tc array */
       for (j = 1; j <= n; j++)
           tc[0][j] = tc[0][j-1] + cost[0][j];

       /* Construct rest of the tc array */
       for (i = 1; i <= m; i++)
           for (j = 1; j <= n; j++)
               tc[i][j] = min(tc[i-1][j-1],
                              tc[i-1][j],
                              tc[i][j-1]) + cost[i][j];

       return tc[m][n];
   }

public static void main(String[] args)
{
int cost[][]= {{1, 2, 3},{4, 8, 2},{1, 5, 3}};
        System.out.println("minimum cost to reach (2,2) == " + minCost(cost,2,2));
}

}

Output: minimum cost to reach (2,2) == 8

Time Complexity: O(mn) which is much better than Naive Recursive implementation.

Find common elements in three sorted arrays

Find common elements in three sorted arrays

Given three arrays sorted in non-decreasing order, print all common elements in these arrays.

Examples:

ar1[] = {1, 5, 10, 20, 40, 80}
ar2[] = {6, 7, 20, 80, 100}
ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}

Output: 20, 80

ar1[] = {1, 5, 5}
ar2[] = {3, 4, 5, 5, 10}
ar3[] = {5, 5, 10, 20}

Output: 5, 5

A simple solution is to first find intersection of two arrays and store the intersection in a temporary array, then find the intersection of third array and temporary array.

Time complexity of this solution is O(n1 + n2 + n3) where n1, n2 and n3 are sizes of ar1[], ar2[] and ar3[] respectively.

The above solution requires extra space and two loops, we can find the common elements using a single loop and without extra space. The idea is similar to intersection of two arrays. Like two arrays loop, we run a loop and traverse three arrays.

Let the current element traversed in ar1[] be x, in ar2[] be y and in ar3[] be z. We can have following cases inside the loop.

1) If x, y and z are same, we can simply print any of them as common element and move ahead in all three arrays.
2) Else If x < y, we can move ahead in ar1[] as x cannot be a common element
3) Else If y < z, we can move ahead in ar2[] as y cannot be a common element
4) Else (We reach here when x > y and y > z), we can simply move ahead in ar3[] as z cannot be a common element.

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class FindCommonElement
{
public void findcommonElement(int arr1[],int arr2[],int arr3[])
{
int i=0, j=0 , k=0;

while(i < arr1.length && j<arr2.length && k<arr3.length)
{
if(arr1[i] == arr2[j] && arr2[j]==arr3[k])
{
System.out.print(arr1[i]+" ");  
i++;
j++;
k++;
}
else if (arr1[i] < arr2[j])
                i++;

            else if (arr2[j] < arr3[k])
                j++;

            else
                k++;
}
}

public static void main(String[] args)
{
  FindCommonElement ob = new FindCommonElement();
          int ar1[] = {1, 5, 10, 20, 40, 80};
          int ar2[] = {6, 7, 20, 80, 100};
          int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120};
          System.out.print("Common elements are :");
          ob.findcommonElement(ar1, ar2, ar3);
}
}

Output:  Common elements are :20 80

Time complexity of the above solution is O(n1 + n2 + n3). 
In worst case, the largest sized array may have all small elements and middle sized array has all middle elements.

Find k closest elements to a given value in java

Find k closest elements to a given value

Examples:

Input: K = 4, X = 35
       arr[] = {12, 16, 22, 30, 35, 39, 42, 45, 48, 50, 53, 55, 56}
 
Output: 30 39 42 45

Note that if the element is present in array, then it should not be in output, only the other closest elements are required.

In the following solutions, it is assumed that all elements of array are distinct.

A simple solution is to do linear search for k closest elements but Binary Search would be an
optimized Solution for it.

1) Start from the first element and search for the crossover point (The point before which elements are smaller than or equal to X and after which elements are greater). This step takes O(n) time.
2) Once we find the crossover point, we can compare elements on both sides of crossover point to print k closest elements. This step takes O(k) time.

The time complexity of the above solution is O(n).

An Optimized Solution is to find k elements in O(Logn + k) time. The idea is to use Binary Search to find the crossover point. Once we find index of crossover point, we can print k closest elements in O(k) time.

Sample Code Solution:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class KClosest
{

public int crossOver(int arr[],int low,int high,int x)
{
if (arr[high] <= x) // x is greater than all
           return high;
       if (arr[low] > x)  // x is smaller than all
           return low;
     
       int mid = (low + high)/2;
     
       if (arr[mid] <= x && arr[mid+1] > x)
           return mid;
     
       if(arr[mid] < x)
           return crossOver(arr, mid+1, high, x);
     
       return crossOver(arr, low, mid - 1, x);

}

public void printKclosest(int arr[], int x, int k, int n)
      {  
        int l = crossOver(arr, 0, n-1, x);
        int r = l+1;  
        int count = 0;            
        if (arr[l] == x)
        l--;

        while (l >= 0 && r < n && count < k)
        {
            if (x - arr[l] < arr[r] - x)
                System.out.print(arr[l--]+" ");
            else
                System.out.print(arr[r++]+" ");
            count++;
        }
        while (count < k && l >= 0)
        {
            System.out.print(arr[l--]+" ");
            count++;
        }

        while (count < k && r < n)
        {
            System.out.print(arr[r++]+" ");
            count++;
        }
    }

public static void main(String[] args)
{
   KClosest ob = new KClosest();
       int arr[] = {12, 16, 22, 30, 35, 39, 42,45, 48, 50, 53, 55, 56};
       int n = arr.length;
       int x = 35, k = 4;
       ob.printKclosest(arr, x, 4, n);
}
}

Output:

39 30 42 45

The time complexity of this method is O(Logn + k).

Sorting Algorithm - Merge Sort

Merge Sort

MergeSort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

MergeSort(arr[], l,  r)

If r > l
     1. Find the middle point to divide the array into two halves:
             middle m = (l+r)/2
     2. Call mergeSort for first half:  
             Call mergeSort(arr, l, m)
     3. Call mergeSort for second half:
             Call mergeSort(arr, m+1, r)
     4. Merge the two halves sorted in step 2 and 3:
             Call merge(arr, l, m, r)


Example : The complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}.

  we can see that the array is recursively divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.
 
  Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class MergeSortApp
{

   public void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
   public void sort(int arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public static void main(String[] args)
{
int arr[] = {12, 11, 13, 5, 6, 7};
MergeSortApp ob = new MergeSortApp();
               System.out.println("Given Array");
               ob.printArray(arr);
               ob.sort(arr, 0, arr.length-1);
              System.out.println("\nSorted array");
             ob.printArray(arr);
}
}

Output:

Given Array
12
11
13
5
6
7
Sorted array
5
6
7
11
12
13

Time Complexity: Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + Theta(n)

The above recurrence can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is Theta(nLogn).
Time complexity of Merge Sort is Theta(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.

Auxiliary Space: O(n)
Algorithmic Paradigm: Divide and Conquer
Sorting In Place: No in a typical implementation
Stable: Yes





  

Sorting Algorithm - Insertion Sort

Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

For Example:

Algorithm:

// Sort an arr[] of size n
insertionSort(arr, n);
Loop from i = 1 to n-1.
Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

Another Example: 

12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 5 (Size of input array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class InsertionSortApp
{
public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public void insertionSort(int arr[])
{
       int n = arr.length;
     
       for (int i=1; i<n; ++i)
       {
           int key = arr[i];
           int j = i-1;

           while (j>=0 && arr[j] > key)
           {
               arr[j+1] = arr[j];
               j = j-1;
           }
           arr[j+1] = key;
       }
}

public static void main(String[] args)
{
       int arr[] = {12, 11, 13, 5, 6};
               InsertionSortApp ob = new InsertionSortApp();      
              ob.insertionSort(arr);  
              ob.printArray(arr);
}
}

Output:

5
6
11
12
13

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Algorithmic Paradigm: Incremental Approach

Sorting In Place: Yes

Stable: Yes

Uses: Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

Sorting Algorithm - Bubble Sort

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in some random order.

For Example:

First Pass:

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Java implementations of Bubble Sort:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class BubbleSortApp
{
public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public  void bubbleSort(int arr[])
   {
       int n = arr.length;
       for (int i = 0; i < n-1; i++)
           for (int j = 0; j < n-i-1; j++)
               if (arr[j] > arr[j+1])
               {                  
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
   }

public static void main(String[] args)
{
BubbleSortApp ob = new BubbleSortApp();
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
        ob.bubbleSort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
}

}

Output: 

Sorted array
11
12
22
25
34
64
90

Worst and Average Case Time Complexity: O(n*n).
Worst case occurs when array is reverse sorted.

Best Case Time Complexity: O(n).
Best case occurs when array is already sorted.

Auxiliary Space: O(1)
Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already sorted.

Sorting In Place: Yes

Stable: Yes

Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm.
In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).

For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines

Sorting Algorithm - Selection Sort

Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning.

The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element from the unsorted subarray is picked and moved to the sorted subarray.

Note: consider it in ascending order.

Time Complexity:  O(n^2)
Space Complexity: O(1) because the good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Sample Code Implementation in Java:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class SelectionSortApp
{

public void printArray(int arr[])
{
for(int i=0;i<arr.length;i++)
{
System.out.println(arr[i] + " ");
}
System.out.println(" ");
}

public void selectionSort(int arr[])
{
int min_idx;
int n=arr.length;

for(int i=0;i<n-1;i++)
{
min_idx=i;
for(int j=i+1; j<n;j++)
if(arr[j] <arr[min_idx])
min_idx=j;

int temp=arr[min_idx];
arr[min_idx]=arr[i];
arr[i]=temp;
}
}

public static void main(String[] args)
{
SelectionSortApp ob=new SelectionSortApp();
int arr[] = {64,25,12,22,11};
        ob.selectionSort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
}
}

OutPut: Sorted array

11
12
22
25
64

Happy Number(YepMe Interview Question) in Java

Happy Number

I have been interviewed  in YepMe few days back .It was very nice interview taken by the technical interviewer ,simply a nice guy.He asked me this question.So i am giving you its solution what it is and how it works,a complete solution.

Happy Number -- A number is called happy if it leads to 1 after a sequence of steps where in each step number is replaced by sum of squares of its digit ie. if we start with Happy Number and keep replacing it with digits square sum, we reach 1.

Examples:

Input: n = 19
Output: True

19 is Happy Number,See how?

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

As we reached to 1, 19 is a Happy Number.

Input: n = 20
Output: False

A number will not be a Happy Number when it makes a loop in its sequence that is it touches a number in sequence which already been touched. So to check whether a number is happy or not, we can keep a set, if same number occurs again we flag result as not happy.

Sample Code implementation in Java:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class HappyNumberSolution
{
public static boolean isHappyNumber(int  n)
{
int slow=n,fast=n;

do
{
              slow = numSquareSum(slow);
     fast = numSquareSum(numSquareSum(fast));
}
while (slow!=fast);
 
return (slow==1);
}


       public static int numSquareSum(int n)
{
   int squareSum=0;
 
   while (n>0)
   {
    squareSum += (n % 10) * (n % 10);
       n /= 10;
}

return squareSum;
}

public static void main(String[] args)
{
int n = 13;  //20

   if (isHappyNumber(n))
     System.out.println(n+" is a Happy Number");
   else
    System.out.println(n+" is not a Happy Number");
}


}

Output:

1) 13 is a Happy Number(for input as 13).
2)20 is not a Happy Number(for input as 20)

Reverse an array or String in java

Question:

Write a program to reverse an array or string?.

Solution:(Recursively)

1) Initialize start and end indexes
start = 0, end = n-1
2) Swap arr[start] with arr[end]
3) Recursively call reverse for rest of the array.

Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class ReverseArray
{
public static void reverse(int arr[],int start,int end)
{
int temp;
if(start>=end)
return;

temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
reverse(arr, start+1, end-1);
}

public static void printArray(int arr[], int size)
{
       for (int i=0; i < size; i++)
           System.out.print(arr[i] + " ");
       System.out.println("");
}

public static void main(String[] args)
{
    int arr[] = {1, 2, 3, 4, 5, 6};
            printArray(arr, 6);
            reverse(arr, 0, 5);
           System.out.println("Reversed array is ");
           printArray(arr, 6);
}
}


Output:

1 2 3 4 5 6
Reversed array is
6 5 4 3 2 1

Time Complexity: O(n)

Find Missing Number

Question:

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list.
Write an efficient code to find the missing integer.

Example:
Input:    [1, 2, 4, ,6, 3, 7, 8]
Output:    5

Solution:  There is a very simple sum formula for this solution.just have to use that formula.

Formula:

1. Get the sum of numbers
       total = (n+1)*(n+2)/2
2  Subtract all the numbers from sum and
   you will get the missing number.


Sample Code:
/**
 * @author Abhinaw.Tripathi
 *
 */
public class MissingNumber
{
public static int getMissingNo(int arr[],int n)
{
int total,i;
total=(n+1)*(n+2)/2;
for(i=0;i<n;i++)
total-=arr[i];
return total;
}
public static void main(String[] args)
{
int a[] = {1,2,4,5,6};
       int miss = getMissingNo(a,5);
      System.out.println("Missing Number is: "+miss);

}


}

Result: Missing Number is: 3

Time Complexity: O(n)

Note: There can be overflow if n is large. In order to avoid Integer Overflow, we can pick one number from known numbers and subtract one number from given numbers. This way we wont have Integer Overflow ever.

   

Will happen if we take n such that n(n+1)/2 > INT_MAX .

Heap Sort implementation in Java

Heap Sort:

Heap sort is a comparison based sorting technique based on Binary Heap Data-Structures.Now, What is Binary Heap?

Binary Heap is a complete Binary Tree in which every level is completely filled except possibly the last.So,A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array.

So Heap sort is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

Now, again question comes why heap sort can be represented by binary tree or array?

Ans: Because, we all know,a Binary Heap is a Complete Binary Tree, it can be easily represented as array and array based representation is space efficient.

If the parent node is stored at index I, the left child can be calculated by 2 * I + 1 and right child by 2 * I + 2 (assuming the indexing starts at 0).

Heap Sort Algorithm for Sorting in Increasing Order:

1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
3. Repeat above steps until size of heap is greater than 1.


Sample Code:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class HeapSortApp
{
public void sort(int arr[])
    {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        for (int i=n-1; i>=0; i--)
        {          
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

   
    void heapify(int arr[], int n, int i)
    {
        int largest = i;  // Initialize largest as root
        int l = 2*i + 1;  // left = 2*i + 1
        int r = 2*i + 2;  // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
     
            heapify(arr, n, largest);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

public static void main(String[] args)
{
int arr[] = {12, 11, 13, 5, 6, 7};

        HeapSortApp ob = new HeapSortApp();
        ob.sort(arr);

        System.out.println("Sorted array is-->");
        printArray(arr);

}
}

Output: 

Sorted array is-->

5 6 7 11 12 13

Mobile Numeric Keypad Problem Solution in Java

Mobile Numeric Keypad Problem

Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).
Given a number N, find out the number of possible numbers of given length.

Examples:

For N=1, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N=2, number of possible numbers would be 36
Possible numbers: 00,08 11,12,14 22,21,23,25 and so on.
If we start with 0, valid numbers will be 00, 08 (count: 2)
If we start with 1, valid numbers will be 11, 12, 14 (count: 3)
If we start with 2, valid numbers will be 22, 21, 23,25 (count: 4)
If we start with 3, valid numbers will be 33, 32, 36 (count: 3)
If we start with 4, valid numbers will be 44,41,45,47 (count: 4)
If we start with 5, valid numbers will be 55,54,52,56,58 (count: 5)

Question is: We need to print the count of possible numbers.


Solution 1(Based on DFS):

N = 1 is trivial case, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N > 1, we need to start from some button, then move to any of the four direction (up, left, right or down) which takes to a valid button (should not go to *, #). Keep doing this until N length number is obtained (depth first traversal).

Solution 2(Recursive):

Mobile Keypad is a rectangular grid of 4X3 (4 rows and 3 columns)
Lets say Count(i, j, N) represents the count of N length numbers starting from position (i, j)

If N = 1
  Count(i, j, N) = 10
Else
  Count(i, j, N) = Sum of all Count(r, c, N-1) where (r, c) is new
                   position after valid move of length 1 from current
                   position (i, j)

Sample Code:

/************@Author : Abhinaw Tripathi*******************/

class IndexResult
{
int up,down,left,right;

public IndexResult()
{
up = down = left = right = -1;
}
}

public class KepadProblem
{

// check if given index is safe
static boolean isSafe(int i, int j)
{
return (i>=0 && i<3 && j>=0 && j<3);
}

// get set of indices in all 4 directions
static IndexResult getIndices(int n)
{
IndexResult result = new IndexResult();

// handle case for digit 0 separately
if(n == 0)
{
result.up = 8;

return result;
}

// get row and column of digit in 3*3 matrix
int row = n/3;
if(n%3 == 0)
row--;
int col = n - (row*3) - 1;

// set up index
if(isSafe(row-1,col))
result.up = (row-1)*3 + col + 1;

// set down index handling case for digit 8 separately
if(n == 8)
result.down = 0;
else
{
if(isSafe(row+1,col))
result.down = (row+1)*3 + col + 1;
}

if(isSafe(row,col-1))
result.left = row*3 + col;

if(isSafe(row,col+1))
result.right = row*3 + col + 2;

return  result;
}

static int getCount(int N)
{
int[][] mat = new int[10][N];

for(int j=0;j<N;j++)
{
for(int i=0;i<=9;i++)
{
if(j == 0)
mat[i][j] = 1;
else
{
// get set of indices in all 4 directions in "result"
IndexResult result = getIndices(i);

mat[i][j] = mat[i][j-1];
if(result.up != -1)
mat[i][j] += mat[result.up][j-1];
if(result.down != -1)
mat[i][j] += mat[result.down][j-1];
if(result.left != -1)
mat[i][j] += mat[result.left][j-1];
if(result.right != -1)
mat[i][j] += mat[result.right][j-1];
}
}
}

// sum of answers for length N for all starting digits
int sum = 0;
for(int i=0;i<=9;i++)
sum += mat[i][N-1];

return sum;
}

public static void main(String[] args)
{
int N = 5;
System.out.println("N = " + N);
System.out.println("\nAns = " + getCount(N));
}
}

OutPut: 

N = 5
Ans = 2062