Sorting

Counting Sort

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing).

For simplicity, consider the data in the range 0 to 9. 
Input data: 1, 4, 1, 2, 7, 5, 2
  1) Take a count array to store the count of each unique object.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  2  0   1  1  0  1  0  0

  2) Modify the count array such that each element at each index 
  stores the sum of previous counts. 
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  4  4  5  6  6  7  7  7

The modified count array indicates the position of each object in 
the output sequence.
 
  3) Output each object from the input sequence followed by 
  decreasing its count by 1.
  Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
  Put data 1 at index 2 in output. Decrease count by 1 to place 
  next data 1 at an index 1 smaller than this index.

 

// Java implementation of Counting Sort
class CountingSort
{
    void sort(char arr[])
    {
        int n = arr.length;
 
        // The output character array that will have sorted arr
        char output[] = new char[n];
 
        // Create a count array to store count of inidividul
        // characters and initialize count array as 0
        int count[] = new int[256];
        for (int i=0; i<256; ++i)
            count[i] = 0;
 
        // store count of each character
        for (int i=0; i<n; ++i)
            ++count[arr[i]];
 
        // Change count[i] so that count[i] now contains actual
        // position of this character in output array
        for (int i=1; i<=255; ++i)
            count[i] += count[i-1];
 
        // Build the output character array
        for (int i = 0; i<n; ++i)
        {
            output[count[arr[i]]-1] = arr[i];
            --count[arr[i]];
        }
 
        // Copy the output array to arr, so that arr now
        // contains sorted characters
        for (int i = 0; i<n; ++i)
            arr[i] = output[i];
    }
 
    // Driver method
    public static void main(String args[])
    {
        CountingSort ob = new CountingSort();
        char arr[] = {'g', 'e', 'e', 'k', 's', 'f', 'o',
                      'r', 'g', 'e', 'e', 'k', 's'
                     };
 
        ob.sort(arr);
 
        System.out.print("Sorted character array is ");
        for (int i=0; i<arr.length; ++i)
            System.out.print(arr[i]);
    }
}

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
Auxiliary Space: O(n+k)

Points to be noted:
1. Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. Consider the situation where the input sequence is between range 1 to 10K and the data is 10, 5, 10K, 5K.
2. It is not a comparison based sorting. It running time complexity is O(n) with space proportional to the range of data.
3. It is often used as a sub-routine to another sorting algorithm like radix sort.
4. Counting sort uses a partial hashing to count the occurrence of the data object in O(1).
5. Counting sort can be extended to work for negative inputs also.

Counting sort for negative numbers:   Calculate the minimum value in the array and alter the value of the array elements by subtracting the minimum value.
eg. -2 – (-2) = 0

Now all values are greater than equal to zero. Apply counting sort and in the end add the minimum value to array elements to regain the original array.

http://stackoverflow.com/questions/11001797/using-counting-sort-on-negative-values

Advertisements

Working with Bitmaps

The BitmapFactory.decode* methods should not be executed on the main UI thread if the source data is read from disk or a network location (or really any source other than memory). The time this data takes to load is unpredictable and depends on a variety of factors (speed of reading from disk or network, size of image, power of CPU, etc.). If one of these tasks blocks the UI thread, the system flags your application as non-responsive and the user has the option of closing it.


Loading Large Bitmaps into an ImageView Efficiently:
(https://developer.android.com/training/displaying-bitmaps/load-bitmap.html)

Images come in all shapes and sizes. In many cases they are larger than required for a typical application user interface (UI).

Given that you are working with limited memory, ideally you only want to load a lower resolution version in memory. The lower resolution version should match the size of the UI component that displays it. An image with a higher resolution does not provide any visible benefit, but still takes up precious memory and incurs additional performance overhead due to additional on the fly scaling.

public static Bitmap decodeSampledBitmapFromResource(Resources res, int resId,
        int reqWidth, int reqHeight) {

    // First decode with inJustDecodeBounds=true to check dimensions
    final BitmapFactory.Options options = new BitmapFactory.Options();
    options.inJustDecodeBounds = true;
    BitmapFactory.decodeResource(res, resId, options);

    // Calculate inSampleSize
    options.inSampleSize = calculateInSampleSize(options, reqWidth, reqHeight);

    // Decode bitmap with inSampleSize set
    options.inJustDecodeBounds = false;
    return BitmapFactory.decodeResource(res, resId, options);
}

We have set inJustDecodeBounds to true to calculate the size of the image. Then we have calculated the sample size (the factor by which we can scale down the image). Then we decode the image.

 

https://android-developers.googleblog.com/2010/07/multithreading-for-performance.html

https://developer.android.com/training/displaying-bitmaps/process-bitmap.html

Caching & its issues

https://developer.android.com/training/displaying-bitmaps/cache-bitmap.html#memory-cache

 

Considerations to take while designing Cache:

How memory intensive is the rest of your activity and/or application?

How many images will be on-screen at once? How many need to be available ready to come on-screen?

What is the screen size and density of the device? An extra high density screen (xhdpi) device like Galaxy Nexus will need a larger cache to hold the same number of images in memory compared to a device like Nexus S (hdpi).

What dimensions and configuration are the bitmaps and therefore how much memory will each take up?

How frequently will the images be accessed? Will some be accessed more frequently than others? If so, perhaps you may want to keep certain items always in memory or even have multiple LruCache objects for different groups of bitmaps.

Can you balance quality against quantity? Sometimes it can be more useful to store a larger number of lower quality bitmaps, potentially loading a higher quality version in another background task.

 

DiskLRUCache: https://developer.android.com/samples/DisplayingBitmaps/src/com.example.android.displayingbitmaps/util/DiskLruCache.html

Rounding off double to specified number of digits

You can’t set the precision of a double (or Double) to a specified number of decimal digits, because floating-point values don’t have decimal digits. They have binary digits.

You will have to convert into a decimal radix, either via BigDecimal or DecimalFormat, depending on what you want to do with the value later.

DecimalFormat df = new DecimalFormat("#.####");
df.setRoundingMode(RoundingMode.CEILING);
for (Number n : Arrays.asList(12, 123.12345, 0.23, 0.1, 2341234.212431324)) {
    Double d = n.doubleValue();
    System.out.println(df.format(d));
}
You can try BIGDECIMAL for this purpose

Double toBeTruncated = new Double("3.5789055");

Double truncatedDouble = new BigDecimal(toBeTruncated)
    .setScale(3, BigDecimal.ROUND_HALF_UP)
    .doubleValue();

Java coding tricks

1) To copy array

In System class:
public static void arraycopy(Object src,
             int srcPos,
             Object dest,
             int destPos,
             int length)

eg.  System.arraycopy(arr, 0, arr1, 0, arr.length);

2) To print array
eg. System.out.println(Arrays.toString(arr));

3) Sorting : To sort collections and array

// Collections.sort

List list = new ArrayList();
Collections.sort(list, new Comparator() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
// Arrays.sort
ObjectName[] arr = new ObjectName[10];
Arrays.sort(arr, new Comparator() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});

4) Using sorted data structure

If it is a list or set, use TreeSet to sort.

// TreeSet

Set sortedSet = new TreeSet(new Comparator() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedSet.addAll(unsortedSet);

If it is a map, use TreeMap to sort. TreeMap is sorted by key.

// TreeMap - using String.CASE_INSENSITIVE_ORDER which is a Comparator that orders Strings by compareToIgnoreCase
Map sortedMap = new TreeMap(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);

 

//TreeMap - In general, defined comparator
Map sortedMap = new TreeMap(new Comparator() {
	public int compare(ObjectName o1, ObjectName o2) {
		return o1.toString().compareTo(o2.toString());
	}
});
sortedMap.putAll(unsortedMap);

This approach is very useful, if you would do a lot of search operations for the collection. The sorted data structure will give time complexity of O(logn), which is lower than O(n).

5) Sort a Map with Values

Java – Sort Map By Value

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
 
public class Solution {
	public static void main(String[] args) {
		HashMap map = new HashMap();
		map.put("a", 10);
		map.put("b", 30);
		map.put("c", 50);
		map.put("d", 40);
		map.put("e", 20);
		System.out.println(map);
 
		Map sortedMap = sortByValue(map);
		System.out.println(sortedMap);
	}
 
	public static Map sortByValue(Map unsortedMap) {
		Map sortedMap = new TreeMap(new ValueComparator(unsortedMap));
		sortedMap.putAll(unsortedMap);
		return sortedMap;
	}
 
}
 
class ValueComparator implements Comparator {
	Map map;
 
	public ValueComparator(Map map) {
		this.map = map;
	}
 
	public int compare(Object keyA, Object keyB) {
		Comparable valueA = (Comparable) map.get(keyA);
		Comparable valueB = (Comparable) map.get(keyB);
		return valueB.compareTo(valueA);
	}
}

6) Comparator for sorting the string in case insensitive manner

Map map = new TreeMap(String.CASE_INSENSITIVE_ORDER);

7) Comparing strings

Commonly used String methods such as:

String.equalsIgnoreCase(String) //Ignores case while comparing
String.compareTo(String) // To compare two strings

8) Choosing the right java data structure: http://www.javapractices.com/topic/TopicAction.do;jsessionid=4430DA53231A3B560F0BE08F4C48CD54?Id=65

Graph Algorithms

Study:

1)
Topological Sort

2)
Eulerian Path
is a path in graph that visits every edge exactly once.

We can find whether a given graph has a Eulerian Path or not in polynomial time. In fact, we can find it in O(V+E) time.

An undirected graph has Eulerian Path if following two conditions are true.

a) Same as condition (a) for Eulerian Cycle
b) If zero or two vertices have odd degree and all other vertices have even degree.

Note that only one vertex with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph)

Eulerian Circuit/Cycle is an Eulerian Path which starts and ends on the same vertex.

An undirected graph has Eulerian cycle if following two conditions are true.

a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges).

b) All vertices have even degree.

http://www.geeksforgeeks.org/eulerian-path-and-circuit/

3)

Hamiltonian Path in an undirected graph is a path that visits each vertex exactly once.

Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian Path such that there is an edge (in graph) from the last vertex to the first vertex of the Hamiltonian Path.

http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/