Sunday, June 16, 2013

How would you round a double value to certain decimal Precision and Scale ?

Firstly let us understand the difference between Precision and Scale.
If the number is 9232.129394, then

Precision represents the number of number of significant digits to which a number is calculated i.e. 4 digits (9232)
Scale represents the number of digits to the right of the decimal point i.e. 6 in above case (129394)

Some other examples are,
Precision 4, scale 2: 99.99
Precision 10, scale 0: 9999999999
Precision 8, scale 3: 99999.999
Precision 5, scale -3: 99999000
No one wants to loose the precision of the number as it will change the value by large amount. If you still want to loose the precision simply divide the number by 10 to the power precision.
There are multiple ways in Java to round the double value to certain scale, as mentioned in the below example

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.text.DecimalFormat;
public class RoundDouble {
    public double round1(double input, int scale) {
        BigDecimal bigDecimal = new BigDecimal(input).setScale(scale, RoundingMode.HALF_EVEN);
        return bigDecimal.doubleValue();
    }
    public double round2(double input) {
        return Math.round(input * 100) / 100.0d;
    }
    public double round3(double input) {
        DecimalFormat df = new DecimalFormat("#.00");
        return Double.parseDouble(df.format(input));
    }
    public static void main(String[] args) {
        RoundDouble rd = new RoundDouble();
        System.out.println(rd.round1(9232.129394d, 2));
        System.out.println(rd.round2(9232.129394d));
        System.out.println(rd.round3(9232.129394d));
    }
}

The first method of rounding using BigDecimal should be preferred in most scenarios.

Sunday, June 9, 2013

Given a collection of 1 million integers, All ranging between 1 to 9, how would you sort them in Big O(n) time ?

This is a typical Integer Sorting problem with a constraint that the number range to sort is very limited in spite 1 million total entries. Integer Sorting with limited range is achieved efficiently with Bucket Sorting.


TIP- What does Wiki Says about Sorting ?

Bucket sort, counting sort, radix sort, and van Emde Boas tree sorting all work best when the key size is small; for large enough keys, they become slower than comparison sorting
algorithms…

Integer Sorting Techniques : http://en.wikipedia.org/wiki/Integer_sorting#Algorithms_for_few_items
Sorting Algorithms : http://en.wikipedia.org/wiki/Sorting_algorithm


Algorithm

Create a array of size 9 and at each index store the occurrence count of the respective integers. Doing this will achieve this sorting with time complexity of Big O(n) and even the memory requirements are minimized. In Order to print the output just traverse the above created array.

public class BucketSort {
    public int[] sort(int[] array, int min, int max) {
        int range = max - min + 1;
        int[] result = new int[range];
        for (int i: array) {
            result[i]++;
        }
        return result;
    }
}

public class BucketSortTest {@
    Test
    public void testBucketSortFor1To9() {
        int[] array = {
            2, 1, 5, 1, 2, 3, 4, 3, 5, 6, 7, 8, 5, 6, 7, 0
        };
        int[] sort = new BucketSort().sort(array, 0, 8);

        for (int i = 0; i & lt; sort.length; i++) {
            for (int j = 0; j & lt; sort[i]; j++) {
                System.out.println(i);
            }
        }
    }
}

Program output : 0,1,1,2,2,3,3,4,5,5,5,6,6,7,7,8

Tuesday, June 4, 2013

Removing elements while Iterating over a Collection ?

Intent here is to check if you are aware of technique of modifying the collection structure while iterating over it. If we call collection.remove() from within the for loop then ConcurrentModificationException will be thrown by the JVM at runtime.


So lets take code snippet the given method
/***Failing Program, Never call Collection.remove(Object) while iterating***/

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

import static java.util.Arrays.asList;

public class Test {
    public void removeFromCollection(List marks) {
        for (Integer mark : marks) {
            if (mark < 40)
                marks.remove(mark); ==> Will throw java.util.ConcurrentModificationException
        }
    }

    public static void main(String[] args) {
        Test test = new Test();
        test.removeFromCollection(new ArrayList(asList(10,20,50,60)));
    }
}

Actually, the right way to handle such scenario is to use Iterator to remove the element from the underlying Collection while iterating over it. ConcurrentModificationException is thrown because the for loop internally creates a fail-fast iterator which throws exception whenever it finds any structural modification in the underlying data structure (ArrayList in this case).

The correct implementation for removal method would look something like,
public void removeFromCollection(List marks) {
        for (Iterator iterator = marks.iterator(); iterator.hasNext(); ) {
            Integer mark = iterator.next();
            if (mark < 40)
                iterator.remove();
        }
    }

Saturday, June 1, 2013

What do you understand by Token Bucket Algorithm. What are its applications ?

Token Bucket Algorithm


Token bucket algorithm is used to define the upper limits on bandwidth and burstiness on the data transmission in a software application. The token bucket algorithm is based on an analogy of a fixed capacity bucket into which tokens, normally representing a unit of bytes or a single packet of predetermined size, are added at a fixed rate.

Applications

1.) To provide download bandwidth limits in software applications like torrent & download managers.

2.) To control the download speed on 3G network by our cellular provider.


Implementation

Lets try to create an implementation for this algorithm. We will choose a Leaky Bucket Implementation, where a fixed amount of tokens are filled after a predefined interval into the bucket. If no one utilizes those token, then they do not get accumulated over time, they just over flow after the capacity of bucket is reached. Let's name this strategy as FixedIntervalRefillStrategy.


Our TokenBucket Class will have following properties


1. ) Refill Strategy

2. ) Maximum Capacity of Tokens - this is the maximum amount of tokens that a client can ask for, otherwise an exception is thrown.

3.) Size - it is the current size of the bucket which will keep on changing as it is refilled after specific interval and emptied by the clients.



TokenBucket's consume() method accepts the number of tokens to consume. This method will then remove those number of Tokens from the bucket, refilling the bucket if required. This method utilizes CAS (CompareAndSet) operation of AtomicLong to make the resize operation atomic so that no-locking is required. This will make the class thread-safe when multiple threads will simultaneously demand for the tokens.



public class TokenBucket {
    private final RefillStrategy refillStrategy;
    private final long capacity;
    private AtomicLong size;

    public TokenBucket(long capacity, RefillStrategy refillStrategy) {
        this.refillStrategy = refillStrategy;
        this.capacity = capacity;
        this.size = new AtomicLong(0L);
    }

    public void consume(long numTokens) throws InterruptedException {
        if (numTokens < 0)
            throw new RuntimeException("Number of tokens to consume must be positive");
        if (numTokens >= capacity)
            throw new RuntimeException("Number of tokens to consume must be less than the capacity of the bucket");

        long newTokens = Math.max(0, refillStrategy.refill());
        while (!Thread.currentThread().isInterrupted()) {
            long existingSize = size.get();
            long newValue = Math.max(0, Math.min(existingSize + newTokens, capacity));
            if (numTokens <= newValue) {
                newValue -= numTokens;
                if (size.compareAndSet(existingSize, newValue))
                    break;
            } else {
                Thread.sleep(refillStrategy.getIntervalInMillis());
                newTokens = Math.max(0, refillStrategy.refill());
            }
        }
    }


@Override
 public String toString() {
     return "Capacity : " + capacity + ", Size : " + size;
 }
}


public static interface RefillStrategy {
     long refill();
     long getIntervalInMillis();
 }


public final class TokenBuckets {

    private TokenBuckets() {}

    public static TokenBucket newFixedIntervalRefill(long capacityTokens, long refillTokens, long period, TimeUnit unit)
    {
        TokenBucket.RefillStrategy strategy = new FixedIntervalRefillStrategy(refillTokens, period, unit);
        return new TokenBucket(capacityTokens, strategy);
    }

}

public class FixedIntervalRefillStrategy implements TokenBucket.RefillStrategy {
    private final long numTokens;
    private final long intervalInMillis;
    private AtomicLong nextRefillTime;

   public FixedIntervalRefillStrategy(long numTokens, long interval, TimeUnit unit) {
        this.numTokens = numTokens;
        this.intervalInMillis = unit.toMillis(interval);
        this.nextRefillTime = new AtomicLong(-1L);
    }

    public long refill() {
        final long now = System.currentTimeMillis();
        final long refillTime = nextRefillTime.get();
        if (now < refillTime) {
            return 0;
        }

        return nextRefillTime.compareAndSet(refillTime, now + intervalInMillis) ? numTokens : 0;
    }

    public long getIntervalInMillis() {
        return intervalInMillis;
    }

}

API Client User

TokenBucket bucket = TokenBuckets.newFixedIntervalRefill(1024 * 10, speedLimitKBps, 1, TimeUnit.SECONDS); 


 
References
http://en.wikipedia.org/wiki/Token_bucket