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

Advertisements

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/