Closest Pari Points

http://stackoverflow.com/questions/9405660/closest-pair-of-points-algorithm

Reservoir Sampling

http://kebomix.wordpress.com/2011/01/09/reservoir-sampling-java/

http://larrylisblog.net/WebContents/Programming/ReservoirSampling.pdf

http://www.geeksforgeeks.org/reservoir-sampling/

Delete Last Node (Head not not given) LInked Lists

public void deleteLast(){
 //check if this is the last node
 if(this.next == null) {
  this = null;
  return;
 }
 
 //look 2 nodes ahead to see if we have reached the end
 Node temp = this;
 while(temp.next.next != null){
  temp = temp.next;
 }
 
 //Finally, move to last node and set it null
 temp = temp.next;
 temp = null;
}

Reverse Double Linked List

http://www.geeksforgeeks.org/reverse-a-doubly-linked-list/

Unsorted LInked List Duplicates Removal

	package intQuestions;
	import linkedList.Node;
	public class LinkedListDuplicatesRemoval {
	public static void main(String args[]){
	Node a = new Node();
	a.setData(1);
	Node b = new Node();
	b.setData(2);
	Node c = new Node();
	c.setData(1);
	Node d = new Node();
	d.setData(3);
	a.setNext(b);
	b.setNext(c);
	c.setNext(d);
	d.setNext(null);
	Node head = removeDuplicates(a);
	while(head != null) {
	System.out.println(head.getData()+"->");
	head = head.getNext();
	}
	}
	public static Node removeDuplicates(Node head){
	// iterate over the head and for each iteration..iterate again
	//over the complete list and comparing outer item with each inner item and
	//remove the item from list if it is same
	Node current = head;
	while(current != null) {
	Node prev = current;
	Node next = current.getNext();
	while(next != null){
	if(current.getData() == next.getData()){
	prev.setNext( next.getNext());
	} else {
	prev = next;
	}
	next = next.getNext();
	}
	current = current.getNext();
	}
	return head;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Sorting Algorithms

1. Insertion Sort
2. Merge Sort
3. Quick Sort
4. Heap Sort
5. Counting Sort
6. Radix Sort
7. Bucket Sort

     http://www.cs.carleton.edu/faculty/adalal/teaching/f04/117/notes/searchSort.pdf

     http://cusatstudymaterials.files.wordpress.com/2013/04/137877333-sorting-algorithms-in-java.pdf

     http://www.sorting-algorithms.com/

Merge Sort

	package intQuestions;
	import java.util.ArrayList;
	import java.util.List;
	public class MergeSort_ {
	static List<Integer> originalList = new ArrayList<Integer>();
	static List<Integer> tempList = new ArrayList<Integer>();
	public static void main(String args[]){
	originalList.add(5);
	originalList.add(2);
	originalList.add(4);
	originalList.add(7);
	originalList.add(1);
	originalList.add(3);
	originalList.add(2);
	originalList.add(6);
	mergeSort( 0, originalList.size()-1);
	System.out.println(originalList.toString());
	}
	private static void mergeSort(int low,int high){
	if(low<high){
	int middle = (low+high)/2;
	mergeSort(low, middle);
	mergeSort(middle+1, high);
	merge(low,middle,high);
	}
	}
	private static void merge(int low,int middle,int high){
	tempList.clear();
	int i = low;
	int j = middle+1;
	while(i <= middle && j <= high){
	if(originalList.get(i) <= originalList.get(j)){
	tempList.add(originalList.get(i));
	i++;
	} else {
	tempList.add(originalList.get(j));
	j++;
	}
	}
	if(i <= middle){
	while(i<=middle) {
	tempList.add(originalList.get(i));
	i++;
	}
	}
	else if(j <= high){
	while(j<=high) {
	tempList.add(originalList.get(j));
	j++;
	}
	}
	for(int k=low;k<=high;k++){
	originalList.set(k, tempList.get(k-low));
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Counting Number of Inversions Using Merge Sort

http://www.geeksforgeeks.org/counting-inversions/

Merge Sorted Linked Lists

	package intQuestions;
	import java.util.LinkedList;
	import java.util.List;
	import linkedList.Node;
	public class MergeLinkedLists {
	public static void main(String args[]) {
	Node n1 = new Node();
	n1.setData(1);
	Node n2 = new Node();
	n2.setData(3);
	Node n3 = new Node();
	n3.setData(5);
	n1.setNext(n2);
	n2.setNext(n3);
	n3.setNext(null);
	Node n4 = new Node();
	n4.setData(2);
	Node n5 = new Node();
	n5.setData(4);
	Node n6 = new Node();
	n6.setData(6);
	n4.setNext(n5);
	n5.setNext(n6);
	n6.setNext(null);
	Node result = mergeSortedLists(n1, n4);
	while(result != null) {
	if(result.getNext() == null) {
	System.out.print(result.getData());
	} else {
	System.out.print(result.getData() + "->");
	}
	result = result.getNext();
	}
	}
	public static Node mergeSortedLists(Node n1,Node n2) {
	Node result = null;
	if(n1 != null && n2 != null) {
	if(n1.getData() < n2.getData()) {
	result = n1;
	result.setNext(mergeSortedLists(n1.getNext(), n2));
	} else {
	result = n2;
	result.setNext(mergeSortedLists(n1, n2.getNext()));
	}
	} else if(n1 != null) {
	result = n1;
	} else if(n2 != null) {
	result = n2;
	}
	return result;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub