longest increasing subsequence

import java.util.*;

public class Temp{
public static void main(String args[]){

StringBuilder sb=new StringBuilder();

int arr[]={0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int dp[]=new int[arr.length];
int print[]=new int[arr.length];

dp[0]=1;

for(int i=1;i<arr.length;i++){
dp[i]=0;
print[i]=i;
//int max;
int temp=i;
for(int j=0;j<i;j++){
if(arr[i]>arr[j]){
dp[i]=(dp[i]>dp[j]) ? dp[i] : dp[j];
temp=(dp[i]>dp[j]) ? temp : j;
}
print[i]=temp;
}
dp[i]+=1;

}

for(int i=0;i<arr.length;i++){
System.out.print(dp[i]);
}

  System.out.println("\n");

System.out.print("print[i]");
for(int i=0;i<print.length;i++){
System.out.print(+print[i]);
}

System.out.println("\n");
// print longest common subsequesce...

int index=0;
int max=0;
for(int i=0;i<dp.length;i++){
if(max<dp[i]){
max=dp[i];
index=i;
}
}

int count=dp[index];
System.out.println("count = "+count);
System.out.println("index = "+index);

while(count>0){
sb.insert(0,arr[index]+" ");

index=print[index];

count--;
}

System.out.println(sb);


}
}

Longest common subsequesce

import java.util.*;

public class Temp{
public static void main(String args[]){

StringBuilder sb=new StringBuilder();
String str1="AGGTAB";
String str2="GXTXAYB";
int c[][]=new int[str1.length()+1][str2.length()+1];

for(int i=0;i<=str2.length();i++){
c[0][i]=0;
}

for(int j=0;j<=str1.length();j++){
c[j][0]=0;
}

for(int i=1;i<=str1.length();i++){
for(int j=1;j<=str2.length();j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
c[i][j]=1+c[i-1][j-1];
}
else{
c[i][j]=(c[i][j-1]>=c[i-1][j])?c[i][j-1]:c[i-1][j];
}
}
}


System.out.println(c[str1.length()][str2.length()]+"\n");

for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
System.out.print(c[i][j]);
}
System.out.println();
}


// print LCS.....

int i=str1.length();
int j=str2.length();

while(i>0 && j>0){
if(str1.charAt(i-1)==str2.charAt(j-1)){
sb.append(str1.charAt(i-1)+"");
i--;
j--;
}
else{
if(c[i][j-1]>=c[i-1][j]){
j--;
}
else{
i--;
}

}
System.out.println(i + " "+ j +"\n"  );

}

System.out.println(sb.reverse());


}
}

Depth First Traversal For Graph.

// Implementation of basic graph with linked list representation.


import java.util.*;

class Vertex{
String name;
Neighbor adjList;
// for bfs operations , as per COREMAN book.
String status;
int parentIndex;
int d; // discovered time
int f; // finish time

Vertex(String name ,Neighbor adjList){
this.name=name;
this.adjList=adjList;
}
}

class Neighbor{
int vertexNum;
Neighbor link;

Neighbor(int vertexNum,Neighbor link){
this.vertexNum=vertexNum;
this.link=link;
}
}

class MyGraph{

Vertex verList[];
int time; // global variable time

MyGraph(){
Scanner sc=new Scanner(System.in);
int vertexCount=sc.nextInt();
verList=new Vertex[vertexCount];

int i=0;
while(i<vertexCount){
verList[i]=new Vertex(sc.next(),null);
i++;
}

// extract adges
while(sc.hasNext()){
int v1=indexOf(sc.next());
int v2=indexOf(sc.next());

verList[v1].adjList=new Neighbor(v2,verList[v1].adjList);

}


}

int indexOf(String str){
for(int i=0;i<verList.length;i++){
if(str.equals(verList[i].name)){
return i;
}
}

return -1;
}


void print(){
for(int i=0;i<verList.length;i++){
System.out.print("||");
System.out.print(verList[i].name);
System.out.print(verList[i].d);
System.out.print(verList[i].f);
//System.out.print(verList[i].parentIndex);
System.out.print(verList[i].status);
System.out.print("||");
Neighbor temp=verList[i].adjList;
while(temp!=null){
System.out.print("||");
System.out.print("-->"+verList[temp.vertexNum].name);
System.out.print(verList[temp.vertexNum].d);
System.out.print(verList[temp.vertexNum].f);
//System.out.print(verList[temp.vertexNum].parentIndex);
System.out.print(verList[temp.vertexNum].status);
System.out.print("||");
temp=temp.link;
}

System.out.println();
}
}

void dfs(){

//LinkedList<String> stack=new LinkedList<String>();

for(int i=0;i<verList.length;i++){
verList[i].status="white";
verList[i].d=0;
verList[i].f=0;
//verList[i].parentIndex=0;
}

int time=0;
for(int i=0;i<verList.length;i++){
if(verList[i].status=="white"){
dfsVisit(i);
}
}
}// end of dfs

void dfsVisit(int index){
time+=1;
verList[index].status="gray";
verList[index].d=time;
//verList[i].parentIndex=-1;

// for each vertex v adjacent to verList[i]
Neighbor neighbor=verList[index].adjList;
while(neighbor!=null){

if(verList[neighbor.vertexNum].status=="white"){

dfsVisit(neighbor.vertexNum);

}
neighbor=neighbor.link;

}

verList[index].status="black";
time+=1;
verList[index].f=time;
}




}

class Main{
public static void main(String args[]){

MyGraph g=new MyGraph();

g.dfs();

g.print();



}
}

Breadth First Traversal for a Graph

import java.util.*;

class Vertex{

String name;

Neighbor adjList;

// for bfs operations , as per COREMAN book.

String status;

int parentIndex;

int distance;

Vertex(String name ,Neighbor adjList){

this.name=name;

this.adjList=adjList;

}

}

class Neighbor{

int vertexNum;

Neighbor link;

Neighbor(int vertexNum,Neighbor link){

this.vertexNum=vertexNum;

this.link=link;

}

}

class MyGraph{

Vertex verList[];

MyGraph(){

Scanner sc=new Scanner(System.in);

int vertexCount=sc.nextInt();

verList=new Vertex[vertexCount];

int i=0;

while(i<vertexCount){

verList[i]=new Vertex(sc.next(),null);

i++;

}

// extract adges

while(sc.hasNext()){

int v1=indexOf(sc.next());

int v2=indexOf(sc.next());

verList[v1].adjList=new Neighbor(v2,verList[v1].adjList);

}

}

int indexOf(String str){

for(int i=0;i<verList.length;i++){

if(str.equals(verList[i].name)){

return i;

}

}

return -1;

}

void print(){

for(int i=0;i<verList.length;i++){

System.out.print("||");

System.out.print(verList[i].name);

System.out.print(verList[i].parentIndex);

System.out.print(verList[i].distance);

System.out.print(verList[i].status);

System.out.print("||");

Neighbor temp=verList[i].adjList;

while(temp!=null){

System.out.print("||");

System.out.print("-->"+verList[temp.vertexNum].name);

System.out.print(verList[temp.vertexNum].parentIndex);

System.out.print(verList[temp.vertexNum].distance);

System.out.print(verList[temp.vertexNum].status);

System.out.print("||");

temp=temp.link;

}

System.out.println();

}

}

void enQueue(LinkedList<String> Q,String ele){

Q.add(ele);

}

String deQueue(LinkedList<String> Q){

return Q.removeFirst();

}

void bfs(String source){

for(int i=0;i<verList.length;i++){

verList[i].status="white";

verList[i].distance=0;

verList[i].parentIndex=0;

}

LinkedList<String> Q=new LinkedList<String>();

verList[indexOf(source)].status="gray";

verList[indexOf(source)].distance=0;

verList[indexOf(source)].parentIndex=-1;

enQueue(Q,source);

while(!Q.isEmpty()){

String ele=deQueue(Q);

// for each element adjcent to ele.

int eleIndex=indexOf(ele);

Neighbor neighbors=verList[eleIndex].adjList;

while(neighbors!=null){

if(verList[neighbors.vertexNum].status=="white"){

verList[neighbors.vertexNum].status="gray";

verList[neighbors.vertexNum].distance=verList[eleIndex].distance+1;

verList[neighbors.vertexNum].parentIndex=eleIndex;

enQueue(Q,verList[neighbors.vertexNum].name);

}

neighbors=neighbors.link;

}

verList[eleIndex].status="black";

}

}

}

class Main{

public static void main(String args[]){

MyGraph g=new MyGraph();

g.bfs("D");

g.print();

}

}

How the program works : 

To program works correctly , you should to following structure of the input.

First line is total number of nodes . // say you entered N.

next N lines are names of vertices

and after that edges.

i.e. : 

4

A

B

D

C

A D

A B

B D

D C

D A

means in our graph we have 4 nodes maned A B C D , and the edge from A to D , and A to B .....

One more thing , if the graph is UNDIRECTED and there is an edge from A to B then you have to add the edge from B to A explicitly (it is not implied).

The internal implementation of the graph is Linked List based (not matrix based). For implementing Queue ,  I used again a LinkedList , check enQueue() and deQueue() functions.

Please comment if something goes wrong while testing the program.

Happy Reading 

:) :) :) :) :)

Print all the duplicates in the input string.

The problem statement is given here

I took an array of 26 integers , each block or array represent a character. (arr[0] for a , arr[1] for b ... arr[25] for z ).

Now we scan the string character by character and increment the counter of the array according to the character appears. and at last print the characters and their count if the count is greater than 1.



import java.util.*;

class Main{
public static void main(String args[]){

Scanner s =new Scanner(System.in);
String st=s.next();

int arr[]=new int[26];
for(int i=0;i<=25;i++){
arr[i]=0;
}

for(int i=0;i<st.length();i++){
int j=(int)st.charAt(i);
arr[j-97]+=1;
}

for(int i=0;i<26;i++){
if(arr[i]>1){
System.out.println(((char) (i+97))+" count : "+arr[i]);
}

}


}
}

Write a program to print all permutations of a given string

Problem definition is available here

Here is a Java implementation.
Please let me know if , you feel something wrong about code.


import java.util.*;

class Main{

StringBuilder swap(StringBuilder str,int l,int r){
char templ=str.charAt(l);
char tempr=str.charAt(r);
str.setCharAt(l,tempr);
str.setCharAt(r,templ);
return str;
}

void permute(StringBuilder str,int l){

if(l==(str.length()-1)){
System.out.println(str);
}
else{
for(int i=l;i<str.length();i++){
swap(str,l,i);
permute(str,l+1);
swap(str,l,i);
}
}

}

public static void main(String args[]){

Scanner s =new Scanner(System.in);
String st=s.next();
StringBuilder str=new StringBuilder(st);
Main m =new Main();
m.permute(str,0);



}
}

Write a function to reverse a linked list

the problem statement is available at link

the classes I used in the below code are available here.

Iteratively :

import java.util.*;

class Main{


public static void main(String args[]){
MyLinkedList ll=new MyLinkedList();

ll.add(1);
ll.add(1);
ll.add(3);
ll.add(4);
ll.add(5);
ll.add(6);
ll.add(7);

System.out.println(ll);

Node temp1,temp2,temp3;
temp1=ll.head;
temp2=ll.head.getLink();
temp3=ll.head.getLink().getLink();

temp1.setLink(null);

while(temp3!=null){
temp2.setLink(temp1);
temp1=temp2;
temp2=temp3;
temp3=temp3.getLink();
}

temp2.setLink(temp1);
ll.head=temp2;



System.out.println(ll);

}
}