Creating mirror of BST

	package bst;
	/**
	* Created by panded4
	*/
	public class CreateBSTMirror {
	public static void main(String[] args) {
	TNode n1 = new TNode(5);
	n1.left = new TNode(10);
	n1.right = new TNode(15);
	n1.left.left = new TNode(20);
	n1.left.right = new TNode(25);
	n1.right.left = new TNode(30);
	n1.right.right = new TNode(35);
	inOrder(n1);
	createMirror(n1);
	System.out.println("\n");
	inOrder(n1);
	}
	private static void inOrder(TNode n1) {
	if (n1 == null)
	return;
	inOrder(n1.left);
	System.out.print(n1.data + " ");
	inOrder(n1.right);
	}
	static TNode createMirror(TNode root) {
	if (root == null)
	return root;
	TNode left = createMirror(root.left);
	TNode right = createMirror(root.right);
	root.left = right;
	root.right = left;
	return root;
	}
	}
	class TNode {
	int data;
	TNode left, right;
	public TNode(int data) {
	left = right = null;
	this.data = data;
	}
	}

view raw CreateBSTMirror.java hosted with ❤ by GitHub

QuickSort using java

	/**
	* Created by panded4
	* reference: Introduction to Algorithms by Cormen logic
	*/
	public class QuickSortAgain {
	static int partition(int arr[], int p, int r) {
	int x = arr[r];
	int i = p - 1;
	for (int j = p; j < r - 1; j++) {
	if (arr[j] >= x) {
	i += 1;
	swap(arr[i], arr[j]);
	}
	}
	swap(arr[i + 1], arr[r]);
	return i + 1;
	}
	static void swap(int m, int n) {
	int temp = 0;
	temp = m;
	m = n;
	m = temp;
	}
	static void quick(int arr[], int p, int r) {
	if (p < r) {
	int q = partition(arr, p, r);
	quick(arr, p, q - 1);
	quick(arr, q + 1, r);
	}
	}
	public static void main(String[] args) {
	int data[] = {10, 20, 30, 40, 50, 60, 71, 80, 90, 91};
	quick(data, 0, data.length - 1);
	for (int i : data) {
	System.out.print(i);
	System.out.print(" ");
	}
	}
	}

view raw QuickSortAgain.java hosted with ❤ by GitHub

Height of BST

	package bst;
	import static java.lang.Math.max;
	/**
	* Created by panded4
	*/
	public class HeightBST {
	int leftH = 0, rightH = 0;
	private TreeNode head;
	public HeightBST() {
	this.head = createTree();
	}
	public static void main(String[] args) {
	HeightBST heightBST = new HeightBST();
	System.out.println(heightBST.calculateHeight(heightBST.head));
	}
	private TreeNode createTree() {
	TreeNode n1 = new TreeNode(1);
	TreeNode n2 = new TreeNode(2);
	TreeNode n3 = new TreeNode(3);
	TreeNode n4 = new TreeNode(4);
	TreeNode n5 = new TreeNode(5);
	TreeNode n6 = new TreeNode(6);
	TreeNode n7 = new TreeNode(7);
	TreeNode n8 = new TreeNode(8);
	TreeNode n9 = new TreeNode(9);
	n1.left = n2;
	n1.right = n3;
	n2.left = n4;
	n2.right = n5;
	n3.left = n6;
	n3.right = n7;
	n4.left = n8;
	n4.right = n9;
	return n1;
	}
	int calculateHeight(TreeNode head) {
	if (head == null) {
	return 0;
	}
	leftH = calculateHeight(head.left);
	rightH = calculateHeight(head.right);
	return 1 + max(leftH, rightH);
	}
	}

view raw HeightBST.java hosted with ❤ by GitHub

Level Order Traversal and printing in zigzag pattern java

	package bst;
	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Queue;
	import java.util.Stack;
	public class Graph_Traverse {
	private static final TreeNode EMPTY = new TreeNode(-1);
	private TreeNode head;
	public Graph_Traverse() {
	this.head = createTree();
	}
	public static void main(String[] args) {
	Graph_Traverse graph_Traverse = new Graph_Traverse();
	graph_Traverse.PrintLevelOrder();
	}
	private TreeNode createTree() {
	TreeNode n1 = new TreeNode(1);
	TreeNode n2 = new TreeNode(2);
	TreeNode n3 = new TreeNode(3);
	TreeNode n4 = new TreeNode(4);
	TreeNode n5 = new TreeNode(5);
	TreeNode n6 = new TreeNode(6);
	TreeNode n7 = new TreeNode(7);
	TreeNode n8 = new TreeNode(8);
	TreeNode n9 = new TreeNode(9);
	n1.left = n2;
	n1.right = n3;
	n2.left = n4;
	n2.right = n5;
	n3.left = n6;
	n3.right = n7;
	n4.left = n8;
	n4.right = n9;
	return n1;
	}
	public void PrintLevelOrder() {
	boolean forward = true;
	Queue<TreeNode> q = new LinkedList<TreeNode>();
	Stack<TreeNode> s = new Stack<TreeNode>();
	q.add(this.head);
	q.add(EMPTY);
	while (!q.isEmpty()) {
	TreeNode g = q.remove();
	if (g.left != null) {
	q.add(g.left);
	}
	if (g.right != null) {
	q.add(g.right);
	}
	if (g.equals(EMPTY)) {
	if (!q.isEmpty()) {
	q.add(EMPTY);
	}
	forward = !forward;
	while (!s.isEmpty()) {
	System.out.print(s.pop().data + " ");
	}
	continue;
	}
	if (forward == true) {
	System.out.print(g.data + " ");
	} else {
	s.push(g);
	}
	}
	}
	}
	class TreeNode {
	int data;
	TreeNode left, right;
	TreeNode(int data) {
	this.data = data;
	left = null;
	right = null;
	}
	@Override
	public boolean equals(Object n) {
	return (this.data == ((TreeNode) n).data);
	}
	}

view raw Graph_Traverse.java hosted with ❤ by GitHub

	package bst;
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Created by panded4
	*/
	public class LevelOrderTraversalBST {
	public static void main(String[] args) throws java.lang.Exception {
	Node root = new Node(5);
	root.left = new Node(10);
	root.right = new Node(15);
	root.left.left = new Node(20);
	root.left.right = new Node(25);
	root.right.left = new Node(30);
	root.right.right = new Node(35);
	LevelOrderTraversalBST l = new LevelOrderTraversalBST();
	System.out.println("Breadth First Search : ");
	l.levelOrderQueue(root);
	}
	public void levelOrderQueue(Node root) {
	Queue<Node> q = new LinkedList<Node>();
	if (root == null)
	return;
	q.add(root);
	int count = 1;
	while (!q.isEmpty()) {
	Node n = (Node) q.remove();
	System.out.print(" " + n.data);
	count += 1;
	if (n.left != null)
	q.add(n.left);
	if (n.right != null)
	q.add(n.right);
	}
	}
	}
	class Node {
	int data;
	Node left;
	Node right;
	public Node(int data) {
	this.data = data;
	this.left = null;
	this.right = null;
	}
	}

view raw LevelOrderTraversalBST.java hosted with ❤ by GitHub

Palindrome DP

	import java.util.HashSet;
	import java.util.Set;
	/**
	* Created by panded4
	*/
	public class Palindrome2 {
	public static Set<String> palindromes(final String input) {
	final Set<String> result = new HashSet<>();
	for (int i = 0; i < input.length(); i++) {
	// expanding even length palindromes:
	expandPalindromes(result, input, i, i + 1);
	// expanding odd length palindromes:
	expandPalindromes(result, input, i, i);
	}
	return result;
	}
	public static void expandPalindromes(final Set<String> result, final String s, int i, int j) {
	while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
	result.add(s.substring(i, j + 1));
	i--;
	j++;
	}
	}
	public static void main(String[] args) {
	for (String set : palindromes("liiri")) {
	System.out.println(set);
	}
	}
	}

view raw Palindrome2.java hosted with ❤ by GitHub

BFS in Graph

	package graph;
	import java.util.Iterator;
	import java.util.LinkedList;
	/**
	* Created by panded4 on 6/11/2017.
	*/
	public class BFS {
	int v;
	LinkedList<Integer> adj[];
	public BFS(int v) {
	this.v = v;
	adj = new LinkedList[v];
	for (int i = 0; i < v; i++) {
	adj[i] = new LinkedList<>();
	}
	}
	public static void main(String[] args) {
	BFS g = new BFS(4);
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);
	System.out.println("Following is Breadth First Traversal " +
	"(starting from vertex 2)");
	g.bfsUtil(2);
	}
	private void bfsUtil(int s) {
	boolean visited[] = new boolean[v];
	LinkedList<Integer> queue = new LinkedList<Integer>();
	visited[s]=true;
	queue.add(s);
	while (queue.size() != 0)
	{
	s = queue.poll();
	System.out.print(s+" ");
	Iterator<Integer> i = adj[s].listIterator();
	while (i.hasNext())
	{
	int n = i.next();
	if (!visited[n])
	{
	visited[n] = true;
	queue.add(n);
	}
	}
	}
	}
	private void addEdge(int i, int w) {
	adj[i].add(w);
	}
	}

view raw BFS.java hosted with ❤ by GitHub

DFS in Graph

	package graph;
	import java.util.Iterator;
	import java.util.LinkedList;
	/**
	* Created by panded4
	*/
	public class DFS {
	LinkedList<Integer> adj[];
	private int v;
	public DFS(int v) {
	this.v = v;
	adj = new LinkedList[v];
	for (int i = 0; i < v; i++) {
	adj[i] = new LinkedList<>();
	}
	}
	public static void main(String[] args) {
	DFS g = new DFS(4);
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	g.addEdge(1, 2);
	g.addEdge(2, 0);
	g.addEdge(2, 3);
	g.addEdge(3, 3);
	System.out.println("Following is Depth First Traversal " +
	"(starting from vertex 2)");
	g.callDFS(2);
	}
	private void callDFS(int i) {
	boolean[] visited = new boolean[v];
	dfsUtil(i, visited);
	}
	private void dfsUtil(int i, boolean[] visited) {
	visited[i] = true;
	System.out.print(i + " ");
	Iterator<Integer> iterator = adj[i].listIterator();
	while (iterator.hasNext()) {
	int n = iterator.next();
	if (!visited[n])
	dfsUtil(n, visited);
	}
	}
	private void addEdge(int i, int w) {
	adj[i].add(w);
	}
	}

view raw DFS.java hosted with ❤ by GitHub

LCS using DP

	package lcs;
	/**
	* Created by panded4
	*/
	public class LCSTest {
	public static void main(String[] args) {
	LCSTest lcs = new LCSTest();
	String s1 = "DEEP";
	String s2 = "JDEEKPA";
	char[] X = s1.toCharArray();
	char[] Y = s2.toCharArray();
	int m = X.length;
	int n = Y.length;
	lcs.lcs(X, Y, m, n);
	}
	void lcs(char[] X, char[] Y, int m, int n) {
	int L[][] = new int[m + 1][n + 1];
	for (int i = 0; i <= m; i++) {
	for (int j = 0; j <= n; j++) {
	if (i == 0 || j == 0)
	L[i][j] = 0;
	else if (X[i - 1] == Y[j - 1])
	L[i][j] = L[i - 1][j - 1] + 1;
	else
	L[i][j] = max(L[i - 1][j], L[i][j - 1]);
	}
	}
	int index = L[m][n];
	int[] lcs = new int[index + 1];
	int i = m, j = n;
	while (i > 0 && j > 0) {
	if (X[i - 1] == Y[j - 1]) {
	lcs[index - 1] = X[i - 1];
	i--;
	j--;
	index--;
	} else if (L[i - 1][j] > L[i][j - 1])
	i--;
	else
	j--;
	}
	for (int lc : lcs
	) {
	System.out.println((char) lc);
	}
	}
	int max(int a, int b) {
	return (a > b) ? a : b;
	}
	}

view raw LCSTest.java hosted with ❤ by GitHub

External sort for large file using java

	import java.io.BufferedReader;
	import java.io.FileNotFoundException;
	import java.io.FileReader;
	import java.io.FileWriter;
	import java.io.IOException;
	import java.io.PrintWriter;
	import java.util.Arrays;
	import java.util.Random;
	public class ExternalSort {
	static int N = 2000000; // size of the file in disk
	static int M = 100000; // max items the memory buffer can hold
	public static void externalSort(String fileName) {
	String tfile = "temp-file-";
	int[] buffer = new int[M < N ? M : N];
	try {
	FileReader fr = new FileReader(fileName);
	BufferedReader br = new BufferedReader(fr);
	int slices = (int) Math.ceil((double) N / M);
	int i, j;
	i = j = 0;
	// Iterate through the elements in the file
	for (i = 0; i < slices; i++) {
	// Read M-element chunk at a time from the file
	for (j = 0; j < (M < N ? M : N); j++) {
	String t = br.readLine();
	if (t != null)
	buffer[j] = Integer.parseInt(t);
	else
	break;
	}
	// Sort M elements
	Arrays.sort(buffer);
	// Write the sorted numbers to temp file
	FileWriter fw = new FileWriter(tfile + Integer.toString(i) + ".txt");
	PrintWriter pw = new PrintWriter(fw);
	for (int k = 0; k < j; k++)
	pw.println(buffer[k]);
	pw.close();
	fw.close();
	}
	br.close();
	fr.close();
	// Now open each file and merge them, then write back to disk
	int[] topNums = new int[slices];
	BufferedReader[] brs = new BufferedReader[slices];
	for (i = 0; i < slices; i++) {
	brs[i] = new BufferedReader(new FileReader(tfile + Integer.toString(i) + ".txt"));
	String t = brs[i].readLine();
	if (t != null)
	topNums[i] = Integer.parseInt(t);
	else
	topNums[i] = Integer.MAX_VALUE;
	}
	FileWriter fw = new FileWriter("C:\\testd\\external-sorted.txt");
	PrintWriter pw = new PrintWriter(fw);
	for (i = 0; i < N; i++) {
	int min = topNums[0];
	int minFile = 0;
	for (j = 0; j < slices; j++) {
	if (min > topNums[j]) {
	min = topNums[j];
	minFile = j;
	}
	}
	pw.println(min);
	String t = brs[minFile].readLine();
	if (t != null)
	topNums[minFile] = Integer.parseInt(t);
	else
	topNums[minFile] = Integer.MAX_VALUE;
	}
	for (i = 0; i < slices; i++)
	brs[i].close();
	pw.close();
	fw.close();
	} catch (FileNotFoundException e) {
	e.printStackTrace();
	} catch (IOException e) {
	e.printStackTrace();
	}
	}
	static String generateInput(int n) {
	String fileName = "external-sort.txt";
	Random rand = new Random();
	try {
	FileWriter fw = new FileWriter(fileName);
	PrintWriter pw = new PrintWriter(fw);
	for (int i = 0; i < n; i++)
	pw.println(rand.nextInt(101));
	pw.close();
	} catch (IOException e) {
	e.printStackTrace();
	}
	return fileName;
	}
	public static void main(String[] args) {
	String fileName = generateInput(N);
	externalSort(fileName);
	}
	}

view raw ExternalSort.java hosted with ❤ by GitHub

Collection in Java : Hierarchy and Performance

PERFORMANCE :

ClassNotFoundException and NoClassDefFoundError in java

1. java.lang.ClassNotFoundException This exception indicates that the class was not found on the classpath. This indicates that we were trying to load the class definition, and the class did not exist on the classpath.
2. java.lang.NoClassDefFoundError Java Virtual Machine is not able to find a particular class at runtime which was available at compile time.
   If a class was present during compile time but not available in java classpath during runtime.

ClassNotFoundException is a checked Exception derived directly from java.lang.Exception class and you need to provide explicit handling for it while NoClassDefFoundError is an Error derived from LinkageError.

If you are using ClassLoader in Java and have two class loaders then if a ClassLoader tries to access a class which is loaded by another classloader will result in ClassNoFoundException.

ClassNotFoundException comes up when there is an explicit loading of class is involved by providing name of class at runtime using ClassLoader.loadClass(), Class.forName(),  while NoClassDefFoundError is a result of implicit loading of class because of a method call from that class or any variable access.