Project 2
1)Subarray With GivenArray:
package Project1;
public class SubarraySum {
int SubArray(int arr[],int len,int sum) {
int current=arr[0],intial=0;
for(int i=1;i<=len;i++) {
while(current>sum && intial<i-1) {
current-=arr[intial];
intial++;
}
if(current==sum) {
int k=i-1;
System.out.println("Index found between "+intial+" and "+k);
return 1;
}
if(i<len)
current=current+arr[i];
}
return 0;
}
public static void main(String[] args) {
SubarraySum ss=new SubarraySum();
int arr[]= {1,2,3,4,5,6,7,8,9,10};
int len=arr.length;
int sum=15;
ss.SubArray(arr, len, sum);
}
}
2)Permutation:
package Project1;
import java.util.Scanner;
public class StringPermutation {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str;
String ans="";
System.out.println("Enter The String to permute:");
str=sc.next();
System.out.println("permutation:");
permutation(str,ans);
sc.close();
}
private static void permutation(String str, String ans) {
if(str.length()==0) {
System.out.println(ans+" ");
return;
}
for(int i=0;i<str.length();i++) {
char ch=str.charAt(i);
String l=str.substring(0,i);
String r=str.substring(i+1);
String rem=l+r;
permutation(rem,ans+ch);
}
}
}
3)Tree are Identical:
package Project1;
class node{
int data;
node Left,Right;
node(int item){
data=item;
Left=Right=null;
}
}
public class IdenticalTrees {
node root1,root2;
boolean sametrees(node a,node b) {
if(a==null && b==null)
return true;
if(a!=null&&b!=null)
return(a.data==b.data && sametrees(a.Left,b.Left) && sametrees(a.Right,b.Right));
return false;
}
public static void main(String[] args) {
IdenticalTrees tree=new IdenticalTrees();
tree.root1=new node(1);
tree.root1.Left=new node(9);
tree.root1.Left.Left=new node(7);
tree.root1.Right=new node(8);
tree.root2=new node(1);
tree.root2.Left=new node(9);
tree.root2.Left.Left=new node(7);
tree.root2.Right=new node(8);
if(tree.sametrees(tree.root1, tree.root2))
System.out.println("The Both trees are Identical.");
else
System.out.println("both the trees are non-Identical");
}
}
4)Leaf count
package Project1;
class BNode{
int data;
BNode left,right;
public BNode(int item) {
data=item;
left=right=null;
}
}
public class CountLeaves {
BNode root;
int LeafCount() {
return LeafCount(root);
}
int LeafCount(BNode node) {
if(node==null)
return 0;
if(node.left==null && node.right==null)
return 1;
else
return LeafCount(node.left)+LeafCount(node.right);
}
public static void main(String[] args) {
CountLeaves tree=new CountLeaves();
tree.root=new BNode(5);
tree.root.left=new BNode(2);
tree.root.left.left=new BNode(1);
tree.root.left.left.left=new BNode(0);
tree.root.left.right=new BNode(0);
tree.root.left.left.right=new BNode(8);
tree.root.right=new BNode(3);
tree.root.right.left=new BNode(7);
tree.root.right.left.left=new BNode(0);
tree.root.right.left.right=new BNode(6);
tree.root.right.right=new BNode(4);
tree.root.right.right.right=new BNode(0);
tree.root.right.right.left=new BNode(0);
System.out.println("Leaf count:"+tree.LeafCount());
}
}
5)Ancestor
package Project1;
class BNode{
int data;
BNode left,right;
public BNode(int item) {
data=item;
left=right=null;
}
}
public class LowestCommonAncestor {
BNode root;
BNode LeastAncestor(int n1,int n2) {
return LeastAncestor(root,n1,n2);
}
BNode LeastAncestor(BNode node,int n1,int n2) {
if (node == null)
return null;
if (node.data == n1 || node.data == n2)
return node;
BNode left_la = LeastAncestor(node.left, n1, n2);
BNode right_la = LeastAncestor(node.right, n1, n2);
if (left_la!=null && right_la!=null)
return node;
return (left_la != null) ? left_la : right_la;
}
public static void main(String[] args) {
LowestCommonAncestor tree=new LowestCommonAncestor();
tree.root=new BNode(1);
tree.root.left=new BNode(2);
tree.root.right=new BNode(3);
tree.root.left.left=new BNode(4);
tree.root.left.right=new BNode(5);
tree.root.right.left=new BNode(6);
tree.root.right.right=new BNode(7);
System.out.println("Ancestor are:"+tree.LeastAncestor(1,7).data);
}
}
6)Linked list 0S 1S 2S:
package Project1;
class SNode
{
int data;
SNode next;
SNode(int data)
{
this.data=data;
}
}
public class LinkedListSeg {
public static SNode sortList(SNode head)
{
if(head==null || head.next==null)
{
return head;
}
SNode n1 = new SNode(0);
SNode n2 = new SNode(0);
SNode n3 = new SNode(0);
SNode f1 = n1, one = n2, two = n3;
SNode curr = head;
while (curr!=null)
{
if (curr.data == 0)
{
f1.next = curr;
f1 = f1.next;
curr = curr.next;
}
else if (curr.data == 1)
{
one.next = curr;
one = one.next;
curr = curr.next;
}
else
{
two.next = curr;
two = two.next;
curr = curr.next;
}
}
f1.next = (n2.next!=null)? (n2.next) : (n3.next);
one.next = n3.next;
two.next = null;
head = n1.next;
return head;
}
public static SNode newSNode(int data)
{
SNode newSNode = new SNode(data);
newSNode.next = null;
return newSNode;
}
public static void Linkedsort(SNode SNode)
{
while (SNode != null)
{
System.out.print(SNode.data+" ");
SNode = SNode.next;
}
}
public static void main(String args[]) {
SNode head = new SNode(1);
head.next = new SNode(2);
head.next.next = new SNode(2);
head.next.next.next = new SNode(1);
head.next.next.next.next=new SNode(2);
head.next.next.next.next.next=new SNode(0);
head.next.next.next.next.next.next=new SNode(2);
head.next.next.next.next.next.next.next=new SNode(2);
System.out.println("Linked List Before segregation");
Linkedsort(head);
head = sortList(head);
System.out.println("\nLinked List After segregation");
Linkedsort(head);
}
}
7)First Repeated char:
package Project1;
import java.util.HashSet;
public class FirstRepeatedChar {
static char Repeat(char arr[]) {
HashSet<Character> h=new HashSet<>();
for(int i=0;i<=arr.length-1;i++) {
char c=arr[i];
if(h.contains(c))
return c;
else
h.add(c);
}
return 0;
}
public static void main(String[] args) {
String str="skilllync";
char[] arr=str.toCharArray();
System.out.println(Repeat(arr));
}
}
8)Equal array or not
package Project1;
import java.util.Arrays;
public class ArrayEquals {
static boolean Equal(int arr1[],int arr2[]) {
int len1=arr1.length;
int len2=arr2.length;
if(len1!=len2)
return false;
Arrays.sort(arr1);
Arrays.sort(arr2);
for(int i=0;i<len1;i++)
if(arr1[i]!=arr2[i])
return false;
return true;
}
public static void main(String[] args) {
int arr1[]= {1,2,5,4,0};
int arr2[]= {2,4,5,0,1};
if(Equal(arr1,arr2))
System.out.println(1);
else
System.out.println(0);
}
}
9)Relative Sorting:
package Project1;
import java.util.Arrays;
public class RelativeSorting {
public static void main(String[] args) {
int arr1[]= {2,1,2,5,7,1,9,3,6,8,8};
int arr2[]= {2,1,8,3};
int lenm=arr1.length;
int lenn=arr2.length;
System.out.println("Relative Array:");
RelArray(arr1,arr2,lenm,lenn);
printArray(arr1,lenm);
}
private static void printArray(int[] arr1, int lenm) {
for(int i=0;i<lenm;i++)
System.out.println(arr1[i]+" ");
System.out.println();
}
private static void RelArray(int[] arr1, int[] arr2, int lenm, int lenn) {
int temp[]=new int[lenm];
int placed[]=new int[lenm];
for(int i=0;i<lenm;i++) {
temp[i]=arr1[i];
placed[i]=0;
}
Arrays.sort(temp);
int index=0;
for(int i=0;i>lenn;i++) {
int f = first(temp, 0, lenm - 1, arr2[i], lenm);
if (f == -1)
continue;
for (int j = f; (j < lenm && temp[j] == arr2[i]);j++) {
arr1[index++] = temp[j];
placed[j] = 1;
}
}
for (int i = 0; i < lenm; i++)
if (placed[i] == 0)
arr1[index++] = temp[i];
}
private static int first(int[] temp, int i, int j, int k, int lenm) {
if(j>=i) {
int mid=j+(i-j)/2;
if((mid==0)||k>temp[mid-1]&&temp[mid]==k)
return mid;
if(k>temp[mid])
return first(temp,(mid+1),i,k,lenm);
return first(temp,j,(mid-1),k,lenm);
}
return 0;
}
}
10) SHORTEST SOURCE TO DESTINATION PATH:
class Pair{
int i, j;
Pair(int i,int j){
this.i = i; this.j = j;
}
}
class Solution {
int shortestDistance(int N, int M, int A[][], int X, int Y) {
ArrayDeque<Pair> q = new ArrayDeque<>();
if(A[0][0] == 0){
return -1;
}
q.add(new Pair(0,0));
A[0][0] = 0;
int[] di = {-1,0,0,1};
int[] dj = {0,-1,1,0};
int dist = 0;
while(!q.isEmpty()){
int n = q.size();
while(n-- > 0){
Pair p = q.poll();
int i = p.i, j = p.j;
if(i == X && j == Y){
return dist;
}
for(int dir =0; dir < 4; ++dir){
int newI= i+di[dir];
int newJ = j+dj[dir];
if(newI>=0 && newI<N && newJ>=0 && newJ<M && A[newI][newJ]!=0){
A[newI][newJ] = 0;
q.add(new Pair(newI,newJ));
}
}
}
dist += 1;
}
return -1;
}
};
11)Minimum Cost Path:
package Project1;
import java.io.*;
import java.util.*;
class MinimumCost{
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, 1, 0, -1 };
static int ROW = 5;
static int COL = 5;
static class Cell
{
int x;
int y;
int distance;
Cell(int x, int y, int distance)
{
this.x = x;
this.y = y;
this.distance = distance;
}
}
static class distanceComparator
implements Comparator<Cell>
{
public int compare(Cell a, Cell b)
{
if (a.distance < b.distance)
{
return -1;
}
else if (a.distance > b.distance)
{
return 1;
}
else {return 0;}
}
}
static boolean isInsideGrid(int i, int j)
{
return (i >= 0 && i < ROW &&
j >= 0 && j < COL);
}
static int shortestPath(int[][] grid, int row,
int col)
{
int[][] dist = new int[row][col];
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
dist[i][j] = Integer.MAX_VALUE;
}
}
dist[0][0] = grid[0][0];
PriorityQueue<Cell> pq = new PriorityQueue<Cell>(row * col, new distanceComparator());
pq.add(new Cell(0, 0, dist[0][0]));
while (!pq.isEmpty())
{
Cell curr = pq.poll();
for(int i = 0; i < 4; i++)
{
int rows = curr.x + dx[i];
int cols = curr.y + dy[i];
if (isInsideGrid(rows, cols))
{
if (dist[rows][cols] >
dist[curr.x][curr.y] +
grid[rows][cols])
{
if (dist[rows][cols] != Integer.MAX_VALUE)
{
Cell adj = new Cell(rows, cols,
dist[rows][cols]);
pq.remove(adj);
}
dist[rows][cols] = dist[curr.x][curr.y] +
grid[rows][cols];
pq.add(new Cell(rows, cols,
dist[rows][cols]));
}
}
}
}
return dist[row - 1][col - 1];
}
public static void main(String[] args)
throws IOException
{
int[][] grid = { { 31, 100, 65, 12, 18 },
{ 10, 13, 47, 157, 6 },
{ 100, 113, 174, 11, 33 },
{ 88, 124, 41, 20, 140 },
{ 99, 32, 111, 41, 20 } };
System.out.println(shortestPath(grid, ROW, COL));
}
}
12)
package Project1;
import java.util.ArrayList;
import java.util.List;
class ChainedArray{
static final int CHARS = 26;
int V;
List<List<Integer>> adj;
int[] in;
ChainedArray(int V)
{
this.V = V;
in = new int[V];
adj = new ArrayList<>(CHARS);
for(int i = 0; i < CHARS; i++)
{
adj.add(i, new ArrayList<>());
}
}
void addEdge(int v, int w)
{
adj.get(v).add(w);
in[w]++;
}
boolean isEulerianCycle()
{
if (!isSC())
return false;
for(int i = 0; i < V; i++)
if (adj.get(i).size() != in[i])
return false;
return true;
}
boolean isSC()
{
boolean[] visited = new boolean[V];
for(int i = 0; i < V; i++)
visited[i] = false;
int n;
for(n = 0; n < V; n++)
if (adj.get(n).size() > 0)
break;
DFSUtil(n, visited);
for(int i = 0; i < V; i++)
if (adj.get(i).size() > 0 && !visited[i])
return false;
ChainedArray gr = getTranspose();
for(int i = 0; i < V; i++)
visited[i] = false;
gr.DFSUtil(n, visited);
for(int i = 0; i < V; i++)
if (adj.get(i).size() > 0 && !visited[i])
return false;
return true;
}
void DFSUtil(int v, boolean[] visited)
{
visited[v] = true;
for(Integer i : adj.get(v))
if (!visited[i])
{
DFSUtil(i, visited);
}
}
ChainedArray getTranspose()
{
ChainedArray g = new ChainedArray(V);
for(int v = 0; v < V; v++)
{
for(Integer i : adj.get(v))
{
g.adj.get(i).add(v);
g.in[v]++;
}
}
return g;
}
static boolean canBeChained(String[] arr, int n)
{
ChainedArray g = new ChainedArray(CHARS);
for(int i = 0; i < n; i++)
{
String s = arr[i];
g.addEdge(s.charAt(0) - 'a',
s.charAt(s.length() - 1) - 'a');
}
return g.isEulerianCycle();
}
public static void main(String[] args) throws Exception
{
String[] arr1 = { "great", "skill", "trains", "lync"};
int n1 = arr1.length;
System.out.println((canBeChained(arr1, n1) ?1 :0));
}
}
13)
package Project1;
import java.util.ArrayList;
import java.util.List;
public class NonRepeated{
final static int MAX_CHAR = 256;
static void findFirst()
{
List<Character> h = new ArrayList<Character>();
boolean[] repeated = new boolean[MAX_CHAR];
String str1 = "aabc";
for (int i = 0; i < str1.length(); i++) {
char x = str1.charAt(i);
if (!repeated[x]) {
if (!(h.contains(x))) {
h.add(x);
}
else
{
h.remove((Character)x);
repeated[x]= true;
}
}
if (h.size() != 0) {
System.out.print(0);
System.out.println(h.get(0));
}
}
}
public static void main(String[] args)
{
findFirst();
}
}
14)
package Project1;
import java.io.*;
import java.util.*;
class KeyComparator implements Comparator<Key> {
public int compare(Key k1, Key k2)
{
if (k1.f < k2.f)
return 1;
else if (k1.f > k2.f)
return -1;
return 0;
}
}
class Key {
int f;
char ch;
Key(int val, char c)
{
f = val;
ch = c;
}
}
class RearrangeString {
static int MAX_CHAR = 26;
static void rearrangeString(String str)
{
int n = str.length();
int[] count = new int[MAX_CHAR];
for (int i = 0; i < n; i++)
count[str.charAt(i) - 'a']++;
PriorityQueue<Key> pq= new PriorityQueue<>(new KeyComparator());
for (char c = 'a'; c <= 'z'; c++) {
int val = c - 'a';
if (count[val] > 0)
pq.add(new Key(count[val], c));
}
str = "";
Key prev = new Key(-1, '#');
while (pq.size() != 0) {
Key k = pq.peek();
pq.poll();
str = str + k.ch;
if (prev.f > 0)
pq.add(prev);
(k.f)--;
prev = k;
}
if (n != str.length())
System.out.println(0);
else
System.out.println(1);
}
public static void main(String args[])
{
String str = "bbbabaaacd";
rearrangeString(str);
}
}
15)
package Project1;
public class LongestCommonSeq
{
int lcs( char[] X, char[] Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
int max(int a, int b)
{
return (a > b)? a : b;
}
public static void main(String[] args)
{
LongestCommonSeq lcs = new LongestCommonSeq();
String s1 = "ABCBDAB";
String s2 = "BDCABA";
char[] X=s1.toCharArray();
char[] Y=s2.toCharArray();
int m = X.length;
int n = Y.length;
System.out.println("Length is" + " " +lcs.lcs( X, Y, m, n ) );
}
}
16)Findhops:
package Project1;
import java.util.*;
public class FindHops {
public static int findStep(int n)
{
if ( n == 0)
return 1;
else if (n < 0)
return 0;
else
return findStep(n - 3) + findStep(n - 2)
+ findStep(n - 1);
}
public static void main(String argc[])
{
int n = 5;
System.out.println(findStep(n));
}
}
17) Minimize and sum of product:
package Project1;
import java.util.*;
class SumofArray {
static long minValue(int A[], int B[], int n)
{
Arrays.sort(A);
Arrays.sort(B);
long result = 0;
for (int i = 0; i < n; i++)
result += (A[i] * B[n - i - 1]);
return result;
}
public static void main(String[] args)
{
int A[] = { 3, 1, 1 };
int B[] = { 6, 5, 4 };
int n = A.length;
System.out.println(minValue(A, B, n));
}
}
18)
package Project1;
class LargeNumber
{
static void findLargest(int m, int s)
{
if (s == 0)
{
System.out.print(m == 1 ? "Largest number is" : "Not possible");
return ;
}
if (s > 9*m)
{
System.out.println("Not possible");
return ;
}
int[] res = new int[m];
for (int i=0; i<m; i++)
{
if (s >= 9)
{
res[i] = 9;
s -= 9;
}
else
{
res[i] = s;
s = 0;
}
}
System.out.print("Largest number is ");
for (int i=0; i<m; i++)
System.out.print(res[i]);
}
public static void main (String[] args)
{
int s = 9, m = 2;
findLargest(m, s);
}
}
19)
19) package Project1;
public class SmallestWindow {
static final int no_of_chars = 256;
static String SubString(String str, String pat)
{
int len1 = str.length();
int len2 = pat.length();
if (len1 < len2) {
System.out.println("No such window exists");
return "";
}
int hash_pat[] = new int[no_of_chars];
int hash_str[] = new int[no_of_chars];
for (int i = 0; i < len2; i++)
hash_pat[pat.charAt(i)]++;
int start = 0, start_index = -1,
min_len = Integer.MAX_VALUE;
int count = 0;
for (int j = 0; j < len1; j++) {
hash_str[str.charAt(j)]++;
if (hash_str[str.charAt(j)]
<= hash_pat[str.charAt(j)])
count++;
if (count == len2) {
while (hash_str[str.charAt(start)]
> hash_pat[str.charAt(start)]
|| hash_pat[str.charAt(start)]
== 0) {
if (hash_str[str.charAt(start)]
> hash_pat[str.charAt(start)])
hash_str[str.charAt(start)]--;
start++;
}
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}
if (start_index == -1) {
System.out.println("No such window exists");
return "";
}
return str.substring(start_index,start_index + min_len);
}
public static void main(String[] args)
{
String str = "this is a test string";
String pat = "tist";
System.out.print("Smallest window is : "
+ SubString(str, pat));
}
}