Graph

<?php
$example = range(0, 9);
foreach ($example as $value)
{
 echo $value;
}

Graph and basic Graph Traversals:

package com.amazom.graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph<T> {

private List<Edge<T>> allEdges;
private Map<Long, Vertex<T>> allVertex;
boolean isDirected = false;

public Graph(boolean isDirected) {
allEdges = new ArrayList<Edge<T>>();
allVertex = new HashMap<Long, Vertex<T>>();
this.isDirected = isDirected;
}

public void addEdge(long id1, long id2) {
addEdge(id1, id2, 0);
}

public void addEdge(long id1, long id2, int weight) {
Vertex<T> vertex1 = null;
if (allVertex.containsKey(id1)) {
vertex1 = allVertex.get(id1);
} else {
vertex1 = new Vertex<T>(id1);
allVertex.put(id1, vertex1);
}
Vertex<T> vertex2 = null;
if (allVertex.containsKey(id2)) {
vertex1 = allVertex.get(id2);
} else {
vertex2 = new Vertex<T>(id2);
allVertex.put(id2, vertex2);
}
Edge<T> edge = new Edge<T>(vertex1, vertex2, isDirected, weight);
allEdges.add(edge);
vertex1.addAdjacentVertex(edge, vertex1);
if (!isDirected) {
vertex2.addAdjacentVertex(edge, vertex1);
}
}

public List<Edge<T>> getEdges() {
return allEdges;
}

public Collection<Vertex<T>> getAllVertex() {
return allVertex.values();

}



}

class Edge<T> {
private boolean isDirected = false;
private Vertex<T> vertex1;
private Vertex<T> vertex2;

private int weight;

Edge(Vertex<T> vertex1, Vertex<T> vertex2) {
this.vertex1 = vertex1;
this.vertex2 = vertex2;
}

Edge(Vertex<T> vertex1, Vertex<T> vertex2, boolean isDirected, int weight) {
this.vertex1 = vertex1;
this.vertex2 = vertex2;
this.isDirected = isDirected;
this.weight = weight;
}

Edge(Vertex<T> vertex1, Vertex<T> vertex2, boolean isDirected) {
this.isDirected = isDirected;
this.vertex1 = vertex1;
this.vertex2 = vertex2;
}

public Vertex<T> getVertex1() {
return vertex1;
}

public Vertex<T> getVertex2() {
return vertex2;
}

int getWeight() {
return weight;
}

public boolean isDirected() {
return isDirected;
}

}

class Vertex<T> {
long id;
private T data;
private List<Edge<T>> edges = new ArrayList<Edge<T>>();
private List<Vertex<T>> adjacentVertex = new ArrayList<Vertex<T>>();

Vertex(long id) {
this.id = id;
}

public long getId() {
return id;
}

public void setId(long id) {
this.id = id;
}

public T getData() {
return data;
}

public void setData(T data) {
this.data = data;
}

public void addAdjacentVertex(Edge<T> e, Vertex<T> v) {
edges.add(e);
adjacentVertex.add(v);
}

public List<Vertex<T>> getAdjacentVertexes(){
        return adjacentVertex;
    }
}

Depth First Traversal for Graph:

package com.amazom.graph;

import java.util.HashSet;

import java.util.Set;

public class GraphTraversal {

public void DFS(Graph<Integer> graph) {

Set<Long> visited = new HashSet<Long>();

for (Vertex<Integer> vertex : graph.getAllVertex()) {

if (!visited.contains(vertex.getId())) {

DFSUtil(vertex, visited);

}

}

}

private void DFSUtil(Vertex<Integer> vertex, Set<Long> visited) {

visited.add(vertex.getId());

System.out.println(" vertex " + vertex.id);

for (Vertex<Integer> ver : vertex.getAdjacentVertexes()) {

if (!visited.contains(ver.getId())) {

DFSUtil(vertex, visited);

}

}

}

public static void main(String args[]) {

Graph<Integer> graph = new Graph<Integer>(true);

graph.addEdge(1, 2);

graph.addEdge(1, 5);

graph.addEdge(1, 6);

graph.addEdge(1, 9);

graph.addEdge(2, 3);

graph.addEdge(3, 4);

graph.addEdge(6, 7);

graph.addEdge(7, 8);

GraphTraversal graphTraversal = new GraphTraversal();

graphTraversal.DFS(graph);

}

}

• Graph: Boggele Game

package com.amazom.graph;

import java.util.Dictionary;
import java.util.HashSet;
import java.util.Set;

public class Boggle {

public void game(Set<String> dictionary, char board[][]) {

boolean visited[][] = new boolean[board.length][board[0].length];

for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
StringBuffer buffer = new StringBuffer();
DFS(dictionary, i, j, board, visited, buffer);
}
}

}

private void DFS(Set<String> set, int i, int j, char[][] board,
boolean[][] visited, StringBuffer buffer) {

if (i < 0 || j < 0 || i >= board.length || j >= board[i].length) {
return;
}

if (visited[i][j] == true)
return;

visited[i][j] = true;

buffer.append(board[i][j]);

if (set.contains(buffer.toString())) {
System.out.println("  String is " + buffer.toString());
}

for (int k = i - 1; k <= i + 1; k++) {
for (int l = j - 1; l <= j + 1; l++) {
DFS(set, k, l, board, visited, buffer);// Recursion for the overlapping Strings
}
}

buffer.deleteCharAt(buffer.length() - 1);
visited[i][j] = false;

}

public static void main(String args[]) {
Boggle boggle = new Boggle();
char[][] board = { { 't', 'a', 's', 'g' }, { 'l', 'u', 'n', 'h' },
{ 't', 'e', 'i', 'a' }, { 'a', 'w', 's', 'r' }

};

Set<String> dictionary = new HashSet<String>();

dictionary.add("tushar");
dictionary.add("anisweta");
boggle.game(dictionary, board);

}

}

• Binary MaxHeap:

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

class BinaryMaxHeap<T> {
private List<Node> allNodes = new ArrayList<Node>();

class Node {
int weight;
T data;
}

public T extractMax() {

int size = allNodes.size() - 1;

T max = allNodes.get(0).data;

int lastNodeWeight = allNodes.get(size).weight;
allNodes.get(0).weight = lastNodeWeight;
allNodes.get(0).data = allNodes.get(size).data;
allNodes.remove(size);

int currentIndex = 0;
size--;

while (true) {
int left = 2 * currentIndex + 1;
int right = 2 * currentIndex + 2;
if (left > size)
break;
if (right > size) {
right = left;
}

int largerIndex = allNodes.get(left).weight >= allNodes.get(right).weight ? left
: right;
if (allNodes.get(currentIndex).weight < allNodes.get(largerIndex).weight) {
Node temp = allNodes.get(currentIndex);
temp.data = allNodes.get(currentIndex).data;
temp.weight = allNodes.get(currentIndex).weight;

allNodes.get(currentIndex).data = allNodes.get(largerIndex).data;
allNodes.get(currentIndex).weight = allNodes.get(largerIndex).weight;

allNodes.get(largerIndex).data = temp.data;
allNodes.get(largerIndex).weight = temp.weight;
currentIndex = largerIndex;
} else {
break;
}
}
return max;

}

public void add(int weight, T data) {
Node node = new Node();
node.weight = weight;
node.data = data;
allNodes.add(node);
int size = allNodes.size();
int current = size - 1;
int parentIndex = (current - 1) / 2;
while (parentIndex >= 0) {
Node parentNode = allNodes.get(parentIndex);
Node currentNode = allNodes.get(current);
if (parentNode.weight < currentNode.weight) {
/* swap(parentNode,currentNode); */
data = parentNode.data;
weight = parentNode.weight;

parentNode.data = currentNode.data;
parentNode.weight = currentNode.weight;

currentNode.data = data;
currentNode.weight = weight;

current = parentIndex;
parentIndex = (parentIndex - 1) / 2;
} else {
break;
}
}
}

public void displayHeap() {
for (Node n : allNodes) {
System.out.println(" " + n.data + " -- " + n.weight);
}
}

private void swap(Node first, Node second) {

T data = first.data;
int weight = second.weight;

first.data = second.data;
first.weight = second.weight;

second.data = data;
second.weight = weight;

}

}

public class BinaryMaxHeapSample {

public static void main(String args[]) {

BinaryMaxHeap<String> binaryMaxHeap = new BinaryMaxHeap<String>();

BinaryMaxHeap<Integer> binaryMaxHeapInt = new BinaryMaxHeap<Integer>();

binaryMaxHeap.add(3, "Tushar");
binaryMaxHeap.add(4, "Ani");
binaryMaxHeap.add(8, "Vijay");
binaryMaxHeap.add(10, "pramila");
binaryMaxHeap.add(5, "Roy");
binaryMaxHeap.add(6, "NTF");

binaryMaxHeap.displayHeap();

System.out.println(" Max is " + binaryMaxHeap.extractMax());

System.out.println(" HEAP WITH DATATYPE : Integer");

binaryMaxHeapInt.add(3, 007);
binaryMaxHeapInt.add(4, 1007);
binaryMaxHeapInt.add(1, 4007);
binaryMaxHeapInt.add(6, 2007);
binaryMaxHeapInt.add(9, 507);

binaryMaxHeapInt.displayHeap();

System.out.println(" Max is " + binaryMaxHeapInt.extractMax());

}


}

The above example explains the ArrayList implementation for MaxHeap
Explains the usage for the Generic Type defined as the data hence two use case:
1. data as String
2. data as Integer

Arrays

• Find the minimum distance between two numbers in an array

public class MinimumDistanceBetween {
public int getDistanceBetween(int[] arr, int first, int second) {
int minDis = Integer.MAX_VALUE;
int j = 0;
int temp = 0;

for (int i = 0; i < arr.length; i++) {
if (arr[i] == first || arr[i] == second) {
temp = arr[i];
j = i;
break;
}
}
for (int i = j; i < arr.length; i++) {
if (arr[i] == first || arr[i] == second) {
if (arr[i] != temp) {
if (minDis > i - j){
minDis = i - j;
}
j = i;
}

}
}

return minDis;
}

public static void main(String args[]) {
int[] arr = {2, 5, 3, 5, 4, 4, 2, 3};
System.out.println(" Min distance is " + new MinimumDistanceBetween().getDistanceBetween(arr, 3, 2));
}
}

• Convert the Arrays so as the following pattern as defined in comments is observed

/**
	* Convert an unsorted array into an array such that
	* a < b > c < d > e < f and so on
	*/

import java.util.Arrays;
public class DecreaseIncreaseArray {
private static void getOrderChanged(int[] arr) {
int n = arr.length - 1;
int temp = 0;
Arrays.sort(arr);
for (int i = 1; i < n; i += 2) {
if (i + 1 < n) {
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
for (int i : arr) {
System.out.print(i + " ");
}
}

public static void main(String args[]) {
int[] arr = { 0, 6, 9, 13, 10, -1, 8, 2, 4, 14, -5 };
getOrderChanged(arr);
}
}

Steps:
1. Sort the array : O(nlogn)
2.compare the element: O(n)
total time complexity : O(nlogn + n)

• Find the number repeating maximum number of time in an array of size length and range of the number is defined by range wherein length <= range

class MaxRepeating {
public int maxRepeating(int[] arr, int length, int range) {
for (int i = 0; i < length; i++) {
arr[arr[i] % range] += range; // as arr[i] will always be <= range so will always have the value for the index falling within the range
}

int max = arr[0];
int result = 0;
for (int i = 1; i < length; i++) {
if (arr[i] > max) {
max = arr[i];
result = i;
}
}
return result;
}

public static void main(String[] args) {
int arr[] = { 2, 3, 3, 5, 3, 4, 1, 7, 4, 4, 4, 4, 4 };
int n = arr.length - 1;
int k = 8;
System.out.println("Maximum repeating element is: "
+ new MaxRepeating().maxRepeating(arr, n, k));
}

}

Dynamic Programming

Find Common SubString in two Strings

public class LongestCommonSubString {
 public int lcSubString(char[] first,char[] second){
  int max=0;
  int temp[][] = new int[first.length][second.length];
  for(int i=1;i<temp.length;i++){
   for(int j=1;j<temp[0].length;j++){
    if(first[i-1] == second[j-1])
     temp[i][j] =  temp[i-1][j-1] + 1;
        if(max < temp[i][j])
         max = temp[i][j];
   }
  }
  return max;
 }
 
 public static void main(String args[]) {
  String first = "OldSite:GeeksforGeeks.org";
  String second = "NewSite:GeeksQuiz.com";
  System.out.println(" ---  " + new LongestCommonSubString().lcSubString(first.toCharArray(), second.toCharArray()));
 }
}

Find the longest SubSequence(length) in a Suquence

public class LongestIncreasingSubSequence {
 public int lis(int[] arr){
 int max = 0;
 int[] ls = new int[arr.length];
 for(int i=0;i<arr.length;i++){
  ls[i] = 1;
 }
 for(int i=1;i<arr.length;i++){
  for(int j = 0;j<i;j++){
     if(arr[j]<arr[i] && (ls[j]+1)-ls[i]>0){
      ls[i] = ls[i] +1;
     }
  }
 }
 
 
 for(int i=0;i<ls.length;i++){
  if(ls[i] > max)
   max = ls[i];
 }
  return max;
 }
 
 public static void main(String args[]) {
  int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
  System.out.println(" Longest increasing seq. has length  "+new LongestIncreasingSubSequence().lis(arr));
 }
}

Edit Distance

public class EditDistance {
 private final int EDIT_COST = 1;
 public int minEdits(char[] ch1, char[] ch2) {
  int min = 0;
  int[][] temp = new int[ch1.length + 1][ch2.length + 1];
  for (int i = 0; i < temp.length; i++) {
   temp[i][0] = i;
  }
  for (int j = 0; j < temp[0].length; j++) {
   temp[0][j] = j;
  }
  for (int i = 1; i < ch1.length; i++)
   for (int j = 1; j < ch2.length; j++) {
    if (ch1[i] == ch2[j]) {
     temp[i][j] = temp[i - 1][j - 1];
    } else {
     temp[i][j] = min(temp[i - 1][j - 1] + 1, temp[i - 1][j]
       + EDIT_COST, temp[i][j - 1] + EDIT_COST);
    }
   }
  return min;
 }

 private int min(int a, int b, int c) {
  int temp = Math.min(a, b);
  return Math.min(temp, c);
 }

 public static void main(String args[]) {
  String str1 = "sunday";
  String str2 = "saturday";
  System.out.println(" Minimum edits needed are "
    + new EditDistance().minEdits(str1.toCharArray(),
      str2.toCharArray()));

 }

}

Example above explains the minimum number of edits required to change a string to another, where in the edits include the following operations:

Add

Remove

Edit/Modify

EDIT_Cost is the value associated with the cost for a single edit.