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);

}
}

Nth node from the end of a Linked List

the problem statement is available at link

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


import java.util.*;

class Main{


public static void main(String args[]){
MyLinkedList ll=new MyLinkedList();
Scanner s=new Scanner(System.in);
int Nth=s.nextInt();

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 ptr1,ptr2;
ptr1=ll.head;
ptr2=ll.head;

while(Nth!=0){
ptr2=ptr2.getLink();
Nth-=1;
}

while(ptr2!=null){
ptr1=ptr1.getLink();
ptr2=ptr2.getLink();
}



System.out.println(ptr1.getData());

}
}

Write a function to print the middle of a given linked list

Question is available here : Write a C function to print the middle of a given linked list

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

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 ptr1,ptr2;

ptr1=ll.head;

ptr2=ll.head.getLink().getLink();

while(ptr2!=null){

if(ptr2.getLink()==null){

ptr1=ptr1.getLink();

break;

}

else{

ptr1=ptr1.getLink();

ptr2=ptr2.getLink().getLink();

}

}

System.out.println(ptr1.getData());

}

}

Singly linked list basic code

I develope the linked list presuming that I need to change the `link` and `data` fields of Node class frequently to solve the questions available on geeksForGeeks.

The advisable way to implement the linkedlist class as a Java Professional is given here and here .



class Node{
private Object data;
private Node link;


Node(){
this.data=0;
this.link=null;
}

Node(Object data){
this.data=data;
this.link=null;
}

Node(Object data,Node link){
this.data=data;
this.link=link;
}

void setData(Object data){
this.data=data;
}
void setLink(Node link){
this.link=link;
}

Object getData(){
return data;
}
Node getLink(){
return link;
}


}

class MyLinkedList{

public Node head;


MyLinkedList(){
head=null;
}

public void add(Object data){
Node p=new Node(data,null);
if(head==null){
head=p;
}
else{
(linkToLastNode()).setLink(p);
}

}

public void addFirst(Object data){
Node p=new Node(data,head);
if(head==null){
head=p;
}
else{

head =p;
}

}

public Object deleteFirst(){
Object data=head.getData();
head=head.getLink();
return data;
}


private Node linkToLastNode(){
if(head==null){
return null;
}
else{
Node temp=head;
while((temp.getLink())!=null){
temp=temp.getLink();
}
return temp;
}
}

public String toString(){
Node temp= head;
if(temp==null){
return "";
}
else{
StringBuilder sb=new StringBuilder(" ") ;
while(temp!=null){
sb.append(temp.getData());
sb.append(" ");
temp=temp.getLink();
}
return sb.toString();
}
}


}