Maximize number of 0s by flipping a subarray in java

Maximize number of 0s by flipping a sub-array

Given a binary array, find the maximum number zeros in an array with one flip of a sub-array allowed. A flip operation switches all 0s to 1s and 1s to 0s.

Examples:

Input :  arr[] = {0, 1, 0, 0, 1, 1, 0}
Output : 6
We can get 6 zeros by flipping the sub-array {1, 1}

Input :  arr[] = {0, 0, 0, 1, 0, 1}
Output : 5

The idea is very simple just count the original zero and find the largest sum in the sub-array.
i would provide a solution for it which will work in o(n) complexity.

Solution:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class FlipZeroApp
{
public static void main(String[] args)
{
//int[] arr={0, 1, 0, 0, 1, 1, 0};  output should 6
int[] arr={0, 0, 0, 1, 0, 1};   // here output should be 5
int size=arr.length;
int count=findMaxZeroCount(arr, size);
System.out.println(count);
}
public static int findMaxZeroCount(int arr[], int n)
{
   int orig_zero_count = 0;
   int max_diff = 0;
   int curr_max = 0;

   for (int i=0; i<n; i++)
   {
       if (arr[i] ==0)
          orig_zero_count++;
       // Value to be considered for finding maximum sum
       int val = (arr[i] ==1)? 1 : -1;

       // Update current max and max_diff
       curr_max = Math.max(val, curr_max + val);
       max_diff = Math.max(max_diff, curr_max);
   }
   max_diff = Math.max(0, max_diff);

   return orig_zero_count + max_diff;
}


}

Complexity= o(n) where as any other solution would work in o(n^2).

Output: 5

Non Fibonacci Numbers in Java

Given a positive integer n, the task is to print the n'th non Fibonacci number. The Fibonacci numbers are defined as:

Fib(0) = 0
Fib(1) = 1
for n >1, Fib(n) = Fib(n-1) + Fib(n-2)

First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141,....

Examples:

Input : n = 2
Output : 6

Input : n = 5
Output : 10

There are basically two solutions for it,

Naive Approach: First Approach is to find find Fibonacci numbers and then print first n numbers not present in the found Fibonacci numbers.

Better Solution: A better solution is to use the formula of Fibonacci numbers and keep adding of gap between two consecutive Fibonacci numbers. Value of sum of gap is count of non-Fibonacci numbers seen so far.

Solution:

/**
 * @author Abhinaw.Tripathi
 *
 */
public class FibonaciNumber
{
public static int nonFibonaciNumber(int n)
{
int prevprev=1,prev=2,current=3;

while(n>0)
{
prevprev=prev;
prev=current;
current=prevprev + prev;
n=n-(current-prev-1); //it can be negative
}
n=n+(current-prev-1); //make it positive

return prev+n;
}

public static void main(String[] args)
{
int count=nonFibonaciNumber(5);
System.out.println(count);
}

}

Output: 10

The Stock Span Problem Solution in Java

The Stock Span Problem

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate span of stock’s price for all n days.

The span of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

For example, 
if an array of 7 days prices is given as {100, 80, 60, 70, 60, 75, 85}, then the span values for corresponding 7 days are {1, 1, 1, 2, 1, 4, 6}

Solution:

Traverse the input price array. For every element being visited, traverse elements on left of it and increment the span value of it while elements on the left side are smaller.

Code:

import java.util.Stack;

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

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int price[] = {10, 4, 5, 90, 120, 80};
stockSpanProblem(price);

}
@SuppressWarnings({ "unchecked", "rawtypes" })
private static int[] stockSpanProblem(int[] arr)
{
Stack<Integer> s = new Stack();
Stack<Integer> s2 = new Stack();
int[] returned_arr = new int[arr.length];
int temp;
int count;
for(int i = 0;i < arr.length; i++)
{
 count = 1;
//to push elements inside it until larger element comes
if (s.empty())

s.push(arr[i]);

if (s.peek() > arr[i])
{
 s.push(arr[i]);
}
else
{
 while (!s.empty() && s.peek() < arr[i])
 {
temp = s.pop();
s2.push(temp);
count ++;
 }
s.push(arr[i]);//push this element
while (!s2.empty())
{
 s.push(s2.pop());
}//so s2 empty at last
}
returned_arr[i] = count;
System.out.println(returned_arr[i]);
  }
   return returned_arr;
}
}

Output:

1 1 2 4 5 1

But this solution is inefficient.Can be a better solution than this.

Time Complexity: O(n). It seems more than O(n) at first look. If we take a closer look, we can observe that every element of array is added and removed from stack at most once. So there are total 2n operations at most. Assuming that a stack operation takes O(1) time, we can say that the time complexity is O(n).

Auxiliary Space: O(n) in worst case when all elements are sorted in decreasing order.

Bucket Sort Java Implementation

Bucket Sort

Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem.
Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range. How do we sort the numbers efficiently?

A simple way is to apply a comparison based sorting algorithm. The lower bound for Comparison based sorting algorithm (Merge Sort, Heap Sort, Quick-Sort .. etc) is Ω(n Log n), i.e., they cannot do better than nLogn.
Can we sort the array in linear time? Counting sort can not be applied here as we use keys as index in counting sort. Here keys are floating point numbers.

The idea behind the bucket sort:

bucketSort(arr[], n)

1) Create n empty buckets (Or lists).
2) Do following for every array element arr[i].
 a) Insert arr[i] into bucket[n*array[i]]
3) Sort individual buckets using insertion sort.
4) Concatenate all sorted buckets.

So, Bucket sort or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, and is a cousin of radix sort in the most to least significant digit flavor. Bucket sort is a generalization of pigeonhole sort. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity estimates involve the number of buckets.

Bucket sort works as follows:

Set up an array of initially empty "buckets".
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.

Optimizations:

A common optimization is to put the unsorted elements of the buckets back in the original array first, then run insertion sort over the complete array; because insertion sort's run-time is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.

Time Complexity: If we assume that insertion in a bucket takes O(1) time then steps 1 and 2 of the above algorithm clearly take O(n) time. The O(1) is easily possible if we use a linked list to represent a bucket (In the following code, C++ vector is used for simplicity). Step 4 also takes O(n) time as there will be n items in all buckets.

Sample Code :

import java.util.Arrays;
/**
 * @author Abhinaw.Tripathi
 *
 */
public class BucketSortApp
{
 public static void sort(int[] a, int maxVal)
 {
     int [] bucket=new int[maxVal+1];

     for (int i=0; i<bucket.length; i++)
     {
        bucket[i]=0;
     }

     for (int i=0; i<a.length; i++)
     {
        bucket[a[i]]++;
     }

     int outPos=0;
     for (int i=0; i<bucket.length; i++)
     {
        for (int j=0; j<bucket[i]; j++)
        {
           a[outPos++]=i;
        }
     }
  }

public static void main(String[] args)
{
 int maxVal=5;
          int [] data= {5,3,0,2,4,1,0,5,2,3,1,4};

     System.out.println("Before: " + Arrays.toString(data));
     sort(data,maxVal);
     System.out.println("After:  " + Arrays.toString(data));
}

}

Result:

Before: [5, 3, 0, 2, 4, 1, 0, 5, 2, 3, 1, 4]
After:  [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5]

Comb Sort Algo in Java

The basic idea is to eliminate turtles, or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. Rabbits, large values around the beginning of the list, do not pose a problem in bubble sort.

In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1. The inner loop of bubble sort, which does the actual swap, is modified such that gap between swapped elements goes down (for each iteration of outer loop) in steps of shrink factor: [ input size / shrink factor, input size / shrink factor^2, input size / shrink factor^3, ..., 1 ].

The gap starts out as the length of the list being sorted divided by the shrink factor (generally 1.3; see below) and one pass of the aforementioned modified bubble sort is applied with that gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.

The shrink factor has a great effect on the efficiency of comb sort. 1.3 has been suggested as an ideal shrink factor by the authors of the original article after empirical testing on over 200,000 random lists. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles.

So,Comb Sort is mainly an improvement over Bubble Sort. Bubble sort always compares adjacent values. So all inversions are removed one by one. Comb Sort improves on Bubble Sort by using gap of size more than 1. The gap starts with a large value and shrinks by a factor of 1.3 in every iteration until it reaches the value 1. Thus Comb Sort removes more than one inversion counts with one swap and performs better than Bublle Sort.

The shrink factor has been empirically found to be 1.3 (by testing Combsort on over 200,000 random lists).

Although, it works better than Bubble Sort on average, worst case remains O(n2).


Code Implementation:

import java.util.*;

public class CombSort
 {

    public static void sort(int[] array, int size)
    {
        int gap = size; // The distance between elements being compared
        boolean swapped = true;
        int i; // Our index

        while (gap > 1 || swapped)
        {
            if (gap > 1) {
                gap = (int)(gap / 1.3);
            }

            if (gap == 9 || gap == 10)
            {
                gap = 11;
            }

            i = 0;
            swapped = false;

            // Loop through comparing numbers a gap-length apart.
            // If the first number is bigger than the second, swap them.
            while (i + gap < size)
            {
                if (array[i] > array[i+gap])
                {
                    swap(array, i, i+gap);
                    swapped = true;
                }
                i++;
            }
        }
    }

    public static void swap(int[] list, int i, int j)
    {
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }

    public static String input(String s)
    {    
        System.out.print(s);
        Scanner scan = new Scanner(System.in);
        return scan.next();
    }

    public static void main(String[] args) {
        /* Ask the user how many numbers of what range
        should be sorted by the algorithm and if they want to see the array */

        int ammount = Integer.parseInt( input("How many numbers shall be generated? ") );
        int min = Integer.parseInt( input("Min value of numbers: ") );
        int max = Integer.parseInt( input("Max value of numbers: ") );
        boolean show_array = input("Would you like to see the sorted and unsorted list?(y/n) ").equals("y");
       
        int[] numbers = new int[ammount];
        Random rand = new Random();
        for (int n=0; n < ammount; n++)
        {
            numbers[n] = rand.nextInt(max - min + 1) + min;
        }

        if (show_array)
        {
            System.out.println("__UNSORTED ARRAY__");
            System.out.println(Arrays.toString(numbers));
        }
        sort(numbers, ammount);
        if (show_array)
        {
            System.out.println("__SORTED ARRAY__");
            System.out.println(Arrays.toString(numbers));
        }

    }
}

Output:

How many numbers shall be generated?
4
Min value of numbers: 2
Max value of numbers: 8
Would you like to see the sorted and unsorted list?(y/n) y
__UNSORTED ARRAY__
[5, 3, 8, 6]
__SORTED ARRAY__
[3, 5, 6, 8]


Another Implementation:

import java.util.Scanner;

public class CombSort
{
    public static void main(String[] args)
    {
        int i;
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter no elements you want (Size):");
        int size = sc.nextInt();
        int[] a = new int[size];
        System.out.println("Please enter the " + size + " elements:");
        for (i = 0; i < size; i++)
        {
            a[i] = sc.nextInt();
        }
        System.out.println("Sorted array is :");
        CombSort cs = new CombSort(a);
        for (i = 0; i < size; i++)
        {
            System.out.printf("%d\t", a[i]);
        }
    }
    private final int[] a;

    private CombSort(int[] b)
    {
        this.a = b;
        combSort(a.length);
    }

    private void combSort(int size)
    {
        float shrink = 1.3f;
        int swap;
        int i, gap = size;
        boolean swapped = false;
        while ((gap > 1) || swapped)
        {
            if (gap > 1)
            {
                gap = (int) ((float) gap / shrink);
            }
            swapped = false;
            for (i = 0; gap + i < size; ++i)
            {
                if (a[i] - a[i + gap] > 0)
                {
                    swap = a[i];
                    a[i] = a[i + gap];
                    a[i + gap] = swap;
                    swapped = true;
                }
            }
        }
    }
}

Result:

Enter no elements you want (Size):
4
Please enter the 4 elements:
12
23
08
44
Sorted array is :
8 12 23 44

Re-throwing an Exception Example Java

What is the difference between throws and throw?

Ans: throws clause is used when the programmer does not want to handle the exception and throw it out of a method.throw clause is used when the programmer wants to throw an exception explicitly and wants to handle it using catch block.Hence throw and throws are contradictory.

Re-Throwing an Exception

When an exception occurs in a try block it is caught by a catch block.This means that the thrown exception is available to the catch block .eg.

try
{
   thrown exception;
}
catch(Exception e)
{
 thrown exception;   // re-throw the exception out
}

Program:

/**
 *
 */
package com.collectionpack;

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

class A
{
void method()
{
try
{
String str="Hello";
char ch=str.charAt(5);
}
catch (Exception e)
{
System.out.println("Please see the index is within the range");
throw e;
}
}

}

public class ReThrowingExceptionApp
{
/**
* @param args
*/
public static void main(String[] args)
{
A a=new A();
try
{
a.method();
}
catch (Exception e)
{
e.printStackTrace();
System.out.println("I caught re-thrwon exception");
}
}


}

Output:

Please see the index is within the range

java.lang.StringIndexOutOfBoundsException: String index out of range: 5

at java.lang.String.charAt(Unknown Source)

at com.collectionpack.A.method(ReThrowingExceptionApp.java:18)

at com.collectionpack.ReThrowingExceptionApp.main(ReThrowingExceptionApp.java:39)

I caught re-thrwon exception

Is it possible to re-throw exceptions?

Ans: Yes,it is,re-throw an exception from a catch block to another class where it can handled.

Design a Cache mechanism which uses LRU(Least Recently Used) in java

Solution Description:

The Processing costs for selecting a value from a database-table is high compared to the cost having the value already in memory.So there should be some mechanism that keeps often used values in your application instead getting these values from resource somewhere outside.

But there is a point when using cache in java is the size of the cache;when chache grows too big the java garbage collector has to cleanup more often or our application crashes with a out of memory error.

So we can implement LRU using "LinkedHashMap" class allows us to implement both an LRU and FIFO queues almost without coding.

Why LinkedHashMap? we are using?.
Because the map to become an LRU map. That's because  the map is ordered by access-order.

public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)

Implementation:

import java.util.LinkedHashMap;

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class LRUCache extends LinkedHashMap
{

private static final long serialVersionUID =1L;
private final int capacity;
private long accessCount = 0;
private long hitCount =0;

public LRUCache(int capacity)
{
this.capacity =capacity;
}

public Object get(Object key)
{
accessCount++;
if(super.containsKey(key))
{
hitCount++ ;
}
Object value=super.get(key);
return value;
}

public boolean containsKey(Object key)
{
accessCount ++ ;
if(super.containsKey(key))
{
hitCount++ ;
return true;
}
else
{
return false;
}
}

protected boolean removeEldesEntry(Entry eldest)
{
return size() > capacity ;
}

public long getHitCount() {
return hitCount;
}

public long getAccessCount() {
return accessCount;
}

}

Note: There is a Catch here.What if the interviewer does not allow us to use"LinkedHashMap"?

I am leaving on you guys to solve without "LinkedHashMap".