Project 2

1. SUBARRAY WITH GIVEN SUM

Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to a given number S.

Implement a method subArraySum(a[], s), where A is array of size n and s is the sum.

And return the starting and ending positions (0 indexing) of FIRST such occurring subarray from the left if sum equals to subarray, else print -1.

Code knowing that-

1 <= N <= 10^7
1 <= Ai <= 10^10

A.

In the brute force approach, we can use two loops and for every element in the array find the sub array, add elements up and check if they equal to the target sum. But this will be taking O(n^2) time complexity as we have to loop through n element and for each of those n elements loop through n-1 elements. Hence, this approach is not very efficient.

Another approach is to use two pointers and loop through the array once. Both left and right pointers start at 0. We keep adding up the elements and incrementing right pointer and checking if they are equal or greater than target sum. If they are greater, we decrement the first element's value from the sum and check again if sum is equal and we keep doing this while also incrementing the left pointer. When sum becomes equal we print out the left and right pointers with a space between them denoting the start and end index. This approach is better than first one as it takes only O(n) time complexity to loop through n elements in the array.

public class SubarrayWithSum {

private static void FindSubArrayWithSumS(int[] arr, int s) {
int sum = 0;
int left, right;
left = right = 0;
for(int i = 0; i<arr.length; i++){

if(s == 0){
break;
}

sum += arr[i];

while(sum > s){
sum -= arr[left];
left++;
}

if(sum == s){
System.out.println(left + " " + right);
break;
}
right++;
}

if(right == arr.length || left == arr.length){
System.out.println(-1);
}
}

public static void main(String[] args) {
int [] arr1 = {1,2,3,7,5};
int s1 = 12;
FindSubArrayWithSumS(arr1, s1);
int [] arr2 = {1,2,3,4,5,6,7,8,9,10};
int s2 = 15;
FindSubArrayWithSumS(arr2, s2);
}
}

Output :
1 3
0 4

2. PERMUTATIONS OF A GIVEN STRING

Given a string S. The task is to print all permutations of a given string. Implement perm(s) method where s is a string in capital letter. Print all permutations of a given string S with single space and all permutations should be in lexicographically increasing order.

Constraints:
1 ≤ size of string ≤ 5

public class PermutationsOfString {
static void permute(String str, int l, int r)
{
if (l == r){
System.out.print(str + " ");
}
else{
for (int i = l; i <= r; i++){
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}

static String swap(String a, int i, int j){
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}

public static void main(String[] args){
String str1 = "ABC";
int n1 = str1.length();
permute(str1, 0, n1-1);

System.out.println();

String str2 = "ABSG";
int n2 = str2.length();
permute(str2, 0, n2-1);
}
}

Output :
ABC ACB BAC BCA CBA CAB

ABSG ABGS ASBG ASGB AGSB AGBS BASG BAGS BSAG BSGA BGSA BGAS SBAG SBGA SABG SAGB SGAB SGBA GBSA GBAS GSBA GSAB GASB GABS

3. DETERMINE IF TWO TREES ARE IDENTICAL

Given two binary trees, the task is to find if both of them are identical or not.

Complete the function isIdentical() that takes two roots as parameters and returns true or false.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the Tree).

Constraints:
1 <= Number of nodes <= 1000
1 <=Data of a node <= 1000

public class IdenticalTrees {
Node root1, root2;
static boolean isIdentical(Node root1, Node root2){
if(root1 == null && root2 == null){
return true;
}
if(root1 != null && root2 != null){
return ( root1.key == root2.key && isIdentical(root1.left, root2.left) && isIdentical(root1.right, root2.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.right = new Node(8);
tree.root1.left.left = new Node(7);

tree.root2 = new Node(1);
tree.root2.left = new Node(9);
tree.root2.right = new Node(8);
tree.root2.left.left = new Node(7);

boolean result = isIdentical(tree.root1, tree.root2);
String msg = result ? "Trees are identical" : "Trees are not identical";
System.out.println(msg);

}
}

Output :
Trees are identical

4.COUNT LEAVES IN BINARY TREE

Given a Binary Tree of size N , You have to count leaves in it. For example, there are two leaves in following tree
1
/ \
10 39
/
5

Argument is a string representing the tree as described below:

The values in the string are in the order of level order traversal of the tree where, numbers denote node values, and a character “N” denotes NULL child.

import java.util.*;

class CountLeaves
{

static class Node
{
int data;
Node left, right;
}

static int getLeafCount(Node node)
{

if (node == null)
{
return 0;
}

Queue<Node> q = new LinkedList<>();

int count = 0;
q.add(node);
while (!q.isEmpty())
{
Node temp = q.peek();
q.poll();

if (temp.left != null)
{
q.add(temp.left);
}
if (temp.right != null)
{
q.add(temp.right);
}
if (temp.left == null &&
temp.right == null)
{
count++;
}
}
return count;
}

static Node newNode(int data)
{
Node node = new Node();
node.data = data;
node.left = node.right = null;
return (node);
}

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

Node root = newNode(1);
root.left = newNode(10);
root.right = newNode(39);
root.left.left = newNode(5);


System.out.println(getLeafCount(root));
}
}
}

Output:

39

5. LOWEST COMMON ANCESTOR IN A BINARY TREE

Given a Binary Tree with all unique values and two nodes value n1 and n2. The task is to find the lowest common ancestor of the given two nodes. We may assume that either both n1 and n2 are present in the tree or none of them is present.

Complete the function lca() that takes nodes, n1, and n2 as parameters and returns LCA node as output.

Expected Time Complexity: O(N).
Expected Space Complexity : O(H) where H is the height of the tree.

Constraints:
1 <= Number of nodes <= 100
1 <= Data of a node <= 1000

public class LCAOfBT {
Node root;

Node findLCA(int n1, int n2)
{
return findLCA(root, n1, n2);
}

Node findLCA(Node node, int n1, int n2)
{

if (node == null)
return null;

if (node.key == n1 || node.key == n2)
return node;

Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);

if (left_lca!=null && right_lca!=null)
return node;

return (left_lca != null) ? left_lca : right_lca;
}

public static void main(String args[])
{
LCAOfBT tree = new LCAOfBT();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.println("LCA(4, 5) = " + tree.findLCA(4, 5).key);
System.out.println("LCA(4, 6) = " + tree.findLCA(4, 6).key);
System.out.println("LCA(3, 4) = " + tree.findLCA(3, 4).key);
System.out.println("LCA(2, 4) = " + tree.findLCA(2, 4).key);
}
}

Output :
LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2

6. LINKED LIST OF 0S, 1S AND 2S, SORT IT.

Given a linked list of N nodes where nodes can contain values 0s, 1s, and 2s only. The task is to segregate 0s, 1s, and 2s linked list such that all zeros segregate to head side, 2s at the end of the linked list, and 1s in the mid of 0s and 2s.

complete the function segregate() which segregates the nodes in the linked list as asked in the problem statement and returns the head of the modified linked list. The printing is done automatically by the driver code.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 10^3

public class SortLLOf1s2s0s {
Node head;

public Node addToEnd(Node head, int data){
Node temp = head;
Node n = new Node(data);
if(head==null){
head = n;
return n;
}
while(head.next!=null){
head = head.next;
}
head.next = n;
return temp;
}

public Node sortList(Node head){
if(head==null || head.next==null){
return head;
}

Node head0 = new Node(0);
Node head1 = new Node(0);
Node head2 = new Node(0);

Node List0 = head0, List1 = head1, List2 = head2;

Node temp = head;
while (temp!=null)
{
if (temp.data == 0){
List0.next = temp;
List0 = List0.next;
temp = temp.next;
}
else if (temp.data == 1){
List1.next = temp;
List1 = List1.next;
temp = temp.next;
}
else{
List2.next = temp;
List2 = List2.next;
temp = temp.next;
}
}

List0.next = (head1.next!=null) ? (head1.next) : (head2.next);
List1.next = head2.next;
List2.next = null;

head = head0.next;
return head;
}

public void printList(Node head){
while(head!=null){
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}

public static void main(String[] args) {
SortLLOf1s2s0s list = new SortLLOf1s2s0s();
Node head = null;
head = list.addToEnd(head, 1);
head = list.addToEnd(head, 0);
head = list.addToEnd(head, 2);
head = list.addToEnd(head, 2);
head = list.addToEnd(head, 1);
head = list.addToEnd(head, 2);
head = list.addToEnd(head, 1);
head = list.addToEnd(head, 1);
head = list.addToEnd(head, 0);
head = list.addToEnd(head, 2);
list.printList(head);

head = list.sortList(head);

list.printList(head);

}
}

Output :
1 0 2 2 1 2 1 1 0 2
0 0 1 1 1 1 2 2 2 2

7. FIND FIRST REPEATED CHARACTER

Given a string S. The task is to find the first repeated character in it. We need to find the character that occurs more than once and whose index of second occurrence is smallest.
S contains only lowercase letters.

Argument is a string S.

print the first repeating character in the string. If no such character exist print -1.

Constraints:
1 <= |S| <= 10^4

import java.util.HashMap;

public class FindFirstRepeatedChar {

void findFirstRepeatedChar(String s){
if(s.length() <= 0){
System.out.println("No string found");
}
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
for(int i = 0; i<s.length(); i++){
int counter = 0;
if(hM.containsKey(s.indexOf(s.charAt(i)))){
counter = hM.get(s.indexOf(s.charAt(i)));
}
hM.put(s.indexOf(s.charAt(i)), counter+1);
}
for(int i = 0; i<s.length();){
if(hM.get(s.indexOf(s.charAt(i))) > 1){
System.out.println(s.charAt(i));
break;
}
else if(hM.get(s.indexOf(s.charAt(i))) == 1){
i++;
if(i == s.length()){
System.out.println(-1);
}
}
}
}

public static void main(String[] args) {
FindFirstRepeatedChar str = new FindFirstRepeatedChar();
String s1 = "skilllync";
str.findFirstRepeatedChar(s1);
String s2 = "helloworld";
str.findFirstRepeatedChar(s2);
}
}

Output :
l
l

8. CHECK IF TWO ARRAYS ARE EQUAL OR NOT

Complete the function which takes two arrays A and B of equal size. Find if given arrays are equal or not. Two arrays are said to be equal if both of them contain same set of elements, arrangements (or permutation) of elements may be different though. If there are repetitions, then counts of repeated elements must also be same for two array to be equal.

Print 1 if the arrays are equal else print 0.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Constraints:
1 <= N <= 10^7
1 <= A[],B[] <= 10^18

import java.util.HashMap;

public class CheckIf2ArraysAreEqual {
static boolean areEqual(int [] arr1, int [] arr2){
int n = arr1.length;
int m = arr2.length;

if (n != m){
return false;
}

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int count = 0;
for (int i = 0; i < n; i++) {
if (map.get(arr1[i]) == null){
map.put(arr1[i], 1);
}
else {
count = map.get(arr1[i]);
count++;
map.put(arr1[i], count);
}
}

for (int i = 0; i < n; i++) {

if (!map.containsKey(arr2[i])){
return false;
}

if (map.get(arr2[i]) == 0){
return false;
}
count = map.get(arr2[i]);
--count;
map.put(arr2[i], count);
}

return true;
}

public static void main(String[] args) {
int [] arr1 = {1,2,5,4,0};
int [] arr2 = {2,4,5,0,1};
if(areEqual(arr1, arr2)){
System.out.println(1);
}else{
System.out.println(0);
}

int [] arr3 = {1,2,5};
int [] arr4 = {2,4,15};
if(areEqual(arr3, arr4)){
System.out.println(1);
}else{
System.out.println(0);
}
}
}

Output :
1
0

9. RELATIVE SORTING

Given two arrays A1[] and A2[] of size N and M respectively. The task is to sort A1 in such a way that the relative order among the elements will be same as those in A2. For the elements not present in A2, append them at last in sorted order. It is also given that the number of elements in A2[] are smaller than or equal to number of elements in A1[] andA2[] has all distinct elements.

Expected time complexity is O(N log(N)).

Length of arrays N and M and next two line contains N and M elements respectively.

Output:
Print the relatively sorted array.

Constraints:
1 ≤ A1[], A2[] <= 10^6

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class RelativeSorting {

void sortRelatively(int [] arr1, int [] arr2){

Arrays.sort(arr1); //O(nLogn)
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
for(int i = 0; i<arr1.length; i++){
int counter = 0;

if(hM.containsKey(arr1[i])){
counter = hM.get(arr1[i]);
}
hM.put(arr1[i], counter+1);
}

ArrayList output = new ArrayList();
for(int j = 0; j<arr2.length; j++){ //O(n)
if(hM.containsKey(arr2[j])){
output.addAll(Collections.nCopies(hM.get(arr2[j]), arr2[j]));
hM.remove(arr2[j]);
}
}

Output :
2 2 1 1 8 8 3 5 6 7 9
2 2 6 6 4 5 7 8

10. SHORTEST SOURCE TO DESTINATION PATH

Given a boolean 2D matrix (0-based index), find whether there is path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable. You may move in only four direction ie up, down, left and right. The path can only be created out of a cell if its value is 1.

Complete the function for implementing this. Arguments are two integers n and m denoting the size of the matrix, an n*m matrix and two integers x and y denoting the index of the destination. Print the min no of steps needed to reach the destination.

Constraints:
1<=n,m<=20

import java.util.ArrayDeque;
import java.util.Queue;

class Node
{
int x, y, dist;

Node(int x, int y, int dist)
{
this.x = x;
this.y = y;
this.dist = dist;
}
}

public class ShortestSourceToDestinationPath {
private static final int M = 3;
private static final int N = 4;
private static final int[] row = { -1, 0, 0, 1 };
private static final int[] col = { 0, -1, 1, 0 };
private static boolean isValid(int mat[][], boolean visited[][], int row, int col)
{
return (row >= 0) && (row < M) && (col >= 0) && (col < N) && mat[row][col] == 1 && !visited[row][col];
}

private static void BFS(int mat[][], int i, int j, int x, int y)
{
boolean[][] visited = new boolean[M][N];

Queue q = new ArrayDeque<>();

visited[i][j] = true;
q.add(new Node(i, j, 0));

int min_dist = Integer.MAX_VALUE;

while (!q.isEmpty())
{

Node node = q.poll();

i = node.x;
j = node.y;
int dist = node.dist;

if (i == x && j == y)
{
min_dist = dist;
break;
}

for (int k = 0; k < 4; k++)
{

if (isValid(mat, visited, i + row[k], j + col[k]))
{

visited[i + row[k]][j + col[k]] = true;
q.add(new Node(i + row[k], j + col[k], dist + 1));
}
}
}

if (min_dist != Integer.MAX_VALUE)
{
System.out.println(min_dist);
}
else {
System.out.print(-1);
}
}

public static void main(String[] args)
{
int[][] mat =
{
{ 1, 0, 0, 0},
{ 1, 1, 0, 1},
{ 0, 1, 1, 1}
};

BFS(mat, 0, 0, 2, 3);
}
}

Output :
5

11. MINIMUM COST PATH

Given a square grid of size N, each cell of which contains integer cost which represents a cost to traverse through that cell, we need to find a path from top left cell to bottom right cell by which total cost incurred is minimum. You can move in 4 directions : up, down, left and right. It is assumed that negative cost cycles do not exist in input matrix.

N denoting the size of the grid N*N integer matrix depicting the cost of respective cell from (0,0) to (N,N).

output a single integer depicting the minimum cost to reach the destination.

Constraints:
1 <= N <= 100
1 <= grid[i][j] <= 104

import java.io.*;
import java.util.*;

public class MinimumCostPath {

static int[] row = { -1, 0, 1, 0 };
static int[] col = { 0, 1, 0, -1 };

static class Node
{
int x;
int y;
int distance;

Node(int x, int y, int distance)
{
this.x = x;
this.y = y;
this.distance = distance;
}
}

static class distanceComparator implements Comparator
{
public int compare(Node a, Node b)
{
if (a.distance < b.distance)
{
return -1;
}
else if (a.distance > b.distance)
{
return 1;
}
else {
return 0;
}
}
}

static boolean isValid(int i, int j, int M, int N)
{
return (i >= 0 && i < M && j >= 0 && j < N);
}

static int shortestPath(int[][] grid, int M, int N)
{
int[][] dist = new int[M][N];

for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
dist[i][j] = Integer.MAX_VALUE;
}
}

dist[0][0] = grid[0][0];

PriorityQueue pq = new PriorityQueue(M * N, new distanceComparator());

pq.add(new Node(0, 0, dist[0][0]));
while (!pq.isEmpty()){

Node curr = pq.poll();
for(int i = 0; i < 4; i++){

int R = curr.x + row[i];
int C = curr.y + col[i];

if (isValid(R, C, M, N)){

if (dist[R][C] > dist[curr.x][curr.y] + grid[R][C]){

if (dist[R][C] != Integer.MAX_VALUE)
{
Node adj = new Node(R, C, dist[R][C]);
pq.remove(adj);
}

dist[R][C] = dist[curr.x][curr.y] + grid[R][C];

pq.add(new Node(R, C, dist[R][C]));
}
}
}
}
return dist[M - 1][N - 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, 5, 5));

int[][] grid2 = {{ 42, 93},
{ 7, 14}};

System.out.println(shortestPath(grid2, 2, 2));
}
}

Output :
327
63

12. CIRCLE OF STRINGS

Given an array of strings A[], determine if the strings can be chained together to form a circle. A string X can be chained together with another string Y if the last character of X is same as first character of Y. If every string of the array can be chained, it will form a circle.

For eg for the array arr[] = {“great", “skill", “trains", “lync"} the answer will be Yes as the given strings can be chained as “great", “trains", “skill" and “lync"

Input: array A[].

Output: If chain can be formed, then print 1, else print 0.

Constraints
0 <= size of A <= 30
0 <= A[i] <= 10

import java.util.ArrayList;

public class CircleOfStrings {
public static boolean possibleOrderAmongString(String s[], int n)
{
int m = 26;
boolean mark[] = new boolean[m];
int in[] = new int[26];
int out[] = new int[26];

ArrayList adj = new ArrayList();
for(int i = 0; i < m; i++)
adj.add(new ArrayList<>());

for(int i = 0; i < n; i++)
{

int f = (int)(s[i].charAt(0) - 'a');
int l = (int)(s[i].charAt(s[i].length() - 1) - 'a');

mark[f] = mark[l] = true;

in[l]++;
out[f]++;

adj.get(f).add(l);
}

for(int i = 0; i < m; i++)
{
if (in[i] != out[i]){
return false;
}
}
return isConnected(adj, mark, s[0].charAt(0) - 'a');
}

public static boolean isConnected(ArrayList adj, boolean mark[], int src)
{
boolean visited[] = new boolean[26];

dfs(adj, visited, src);
for(int i = 0; i < 26; i++)
{

if (mark[i] && !visited[i]){
return false;
}
}

return true;
}

public static void dfs(ArrayList adj, boolean visited[], int src)
{
visited[src] = true;
for(int i = 0; i < adj.get(src).size(); i++){
if (!visited[adj.get(src).get(i)]){
dfs(adj, visited, adj.get(src).get(i));
}
}
}

public static void main(String[] args)
{
String s[] = { "ab", "bc", "cd", "da" };
int n = s.length;
System.out.println(possibleOrderAmongString(s, n) ? 1 : 0);

String s1[] = { "abc", "bcd", "cdf" };
int n1 = s1.length;
System.out.println(possibleOrderAmongString(s1, n1) ? 1 : 0);
}
}

Output :
1
0

13. FIRST NON-REPEATING CHARACTER IN A STREAM

Given an input stream of N characters consisting only of lower case alphabets. The task is to find the first non repeating character, each time a character is inserted to the stream.

If no non repeating element is found print -1.

Argument is x character array which are inserted to the stream.

Output:

For each test case in a new line print the first non repeating elements separated by spaces present in the stream at every instinct when a character is added to the stream, if no such element is present print -1.

Constraints:
1 <= N <= 500

import java.util.LinkedList;
import java.util.Queue;

public class FirstNonRepeatingChar {
final static int MAX_CHAR = 26;

static void firstNonRepeatingChar(String str){

int[] charCount = new int[MAX_CHAR];

Queue q = new LinkedList();

for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);

if(charCount[ch - 'a'] == 0 ){
q.add(ch);
}

charCount[ch - 'a']++;

while (!q.isEmpty()) {
if (charCount[q.peek() - 'a'] > 1)
q.remove();
else {
System.out.print(q.peek() + " ");
break;
}
}
if (q.isEmpty())
System.out.print(-1 + " ");
}
System.out.println();
}
public static void main(String[] args) {
String str = "aabc";
firstNonRepeatingChar(str);
String str1 = "aac";
firstNonRepeatingChar(str1);
}
}

Output :
a -1 b b
a -1 c

14. REARRANGE CHARACTERS

Given a string S with repeated characters (only lowercase). The task is to rearrange characters in a string such that no two adjacent characters are same. It may be assumed that the string has only lowercase English alphabets.

Complete the function which takes the argument as a string of lowercase English alphabets and prints 1 if the generated string doesn't contain any same adjacent characters, else if no such string is possible to be made print 0

Constraints:
1 <= length of string <= 104

import java.util.Comparator;
import java.util.PriorityQueue;

class Key {
int freq;
char ch;
Key(int val, char c)
{
freq = val;
ch = c;
}
}

class KeyComparator implements Comparator {

public int compare(Key k1, Key k2)
{
if (k1.freq < k2.freq)
return 1;
else if (k1.freq > k2.freq)
return -1;
return 0;
}
}

public class RearrangeChars {
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 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.freq > 0)
pq.add(prev);

(k.freq)--;
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);
String str2 = "bbbbb";
rearrangeString(str2);
}
}

Output :
1
0

15. LONGEST COMMON SUBSEQUENCE

Given two strings: string X of length m and string Y of length n find the longest common subsequence

The longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.

For example, if X = “ABCBDAB” and Y = “BDCABA”, the LCS(X, Y) = {“BCBA”, “BDAB”, “BCAB”}.

import java.util.HashMap;
import java.util.Map;

public class LongestCommonSubSeq {
public static int findLCS(String X, String Y, int m, int n, Map<String, Integer> lookup)
{

if (m == 0 || n == 0) {
return 0;
}

String key = m + "|" + n;

if (!lookup.containsKey(key))
{

if (X.charAt(m - 1) == Y.charAt(n - 1)) {
lookup.put(key, findLCS(X, Y, m - 1, n - 1, lookup) + 1);
}
else {

lookup.put(key, Integer.max(findLCS(X, Y, m, n-1, lookup), findLCS(X, Y, m - 1, n, lookup)));
}
}

return lookup.get(key);
}

public static void main(String[] args)
{
String X = "ABCBDAB", Y = "BDCABA";

Map<String, Integer> lookup = new HashMap<>();

System.out.println("The length of the LCS is " + findLCS(X, Y, X.length(), Y.length(), lookup));
}
}

Output :
The length of LCS is 4

16. MAXIMUM SUM OF INCREASING SUBSEQUENCES

Given an array A of N positive integers. Find the sum of maximum sum increasing subsequence of the given array.

Complete the function which takes the array and prints the required answer.

Constraints:
1 ≤ N ≤ 106
1 ≤ Ai ≤ 106

public class MaxSumOfIncreasingSubSequence {

static int maxSumIS(int arr[], int n)
{
int i, j, max = 0;
int msum_arr[] = new int[n];

for (i = 0; i < n; i++){
msum_arr[i] = arr[i];
}

for (i = 1; i < n; i++){
for (j = 0; j < i; j++){
if (arr[i] > arr[j] && msum_arr[i] < msum_arr[j] + arr[i]){
msum_arr[i] = msum_arr[j] + arr[i];
}
}
}

for (i = 0; i < n; i++){
if (max < msum_arr[i]){
max = msum_arr[i];
}
}

return max;
}

public static void main(String args[]){
int arr[] = {1, 101, 2, 3, 100, 4, 5};
int n = arr.length;
System.out.println(maxSumIS(arr, n));

int arr2[] = {10, 5, 4, 3};
int n2 = arr2.length;
System.out.println(maxSumIS(arr2, n2));
}
}

Output :
106
10

17. COUNT NUMBER OF HOPS

A frog jumps either 1, 2 or 3 steps to go to top. In how many ways can it reach the top.

Complete the function which takes input N denoting the total number of steps and prints the number of ways to reach the top.

Constraints:
1 ≤ N ≤ 50

public class CountNumberOfHops {

static int printCountDP(int steps){

int [] ways = new int[3];
int n = steps;

ways[0] = 1;
ways[1] = 1;
ways[2] = 2;

for(int i=3 ; i<=n ; i++){
ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3];
}

return ways[n%3];
}

public static void main(String arg[]){
int steps1 = 1;
System.out.println(printCountDP(steps1));
int steps2 = 5;
System.out.println(printCountDP(steps2));
}
}

Output :
1
13

18. N MEETINGS IN ONE ROOM

There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is start time of meeting i and F[i] is finish time of meeting i.

What is the maximum number of meetings that can be accommodated in the meeting room?

Complete the function which takes the array containing the starting time of all the meetings S [ i ] and the array containing the finishing time of all the meetings F [ i ].

Print the order in which the meetings take place separated by a space.

Constraints:
1 ≤ N ≤ 100
1 ≤ S[ i ], F[ i ] ≤ 100000

import java.util.Arrays;
import java.util.Comparator;

class Comparison {
static void compare(Integer arr[], int n)
{
Arrays.sort(arr, new Comparator()
{
@Override
public int compare(Integer s1, Integer s2)
{
return s1 - s2;
}
}
}
}

public class NMeetingsINOneRoom {

static void findMaxMeetings(Integer [] start, Integer [] finish, int n){
Comparison.compare(finish, n);
Integer i, j;
i = 0;
System.out.println("Following meetings are possible :");
System.out.print(i+1 + " ");

for(j = 1; j<n; j++){
if(start[j] >= finish[i]){
System.out.print(j+1 + " ");
i = j;
}
}
}

public static void main(String[] args) {
Integer [] start = {1,3,0,5,8,5};
Integer [] finish = {2,4,6,7,9,9};
Integer n = finish.length;
findMaxMeetings(start, finish, n);
}
}

Output :
1 2 4 5

19. MINIMISE THE SUM OF PRODUCT

You are given two arrays, A and B, of equal size N. The task is to find the minimum value of A[0] * B[0] + A[1] * B[1] +…+ A[N-1] * B[N-1], where shuffling of elements of arrays A and B is allowed.

Argument is the array A[] and array B[] and print the minimum sum.

Constraints:
1 <= Size of Arrays <= 10^7
1 <= A[], B[] <= 10^18

import java.util.Arrays;

public class MinimiseSumOfProducts {

static long minimiseSum(int [] arr1, int [] arr2, int n){
Arrays.sort(arr1);
Arrays.sort(arr2);

long result = 0;
for (int i = 0; i < n; i++)
result += (arr1[i] * arr2[n - i - 1]);

return result;
}

public static void main(String[] args)
{
int arr1[] = {3,1,1 };
int arr2[] = {6,5,4};
int n1 = arr1.length;

System.out.println(minimiseSum(arr1, arr2, n1));

int arr3[] = {6,1,9,5,4 };
int arr4[] = {3,4,8,2,4};
int n2 = arr3.length;

System.out.println(minimiseSum(arr3, arr4, n2));
}
}

Output :
23
80

20. LARGEST NUMBER POSSIBLE

Given two numbers 'N' and 'S' , find the largest number that can be formed with 'N' digits and whose sum of digits should be equals to 'S'.

Input: integers N and S, where N is the number of digits and S is the sum.

Print the largest number that is possible. If their is no such number, then print -1

Constraints:
1 <= N <= 50
0 <= S <= 500

Expected Time Complexity: O(n)

public class LargestNumberPossible {

static void largestNum(int N, int S){

if (S == 0)
{
System.out.print(N == 1 ? 0 : -1);
return ;
}

if (S > 9*N)
{
System.out.println(-1);
return ;
}

int [] res = new int [N];
for(int i = 0; i<N; i++){
if(S >= 9){
res[i] = 9;
S -= 9;
}
else{
res[i] = S;
S = 0;
}
}
for (int i=0; i<N; i++)
System.out.print(res[i] + "");
System.out.println();
}

public static void main(String[] args) {
largestNum(2, 9);
largestNum(3, 20);
}
}

Output :
90
992

21. LONGEST DISTINCT CHARACTERS IN STRING

Given a string S, find length of the longest substring with all distinct characters. For example, for input "abca", the output is 3 as "abc" is the longest substring with all distinct characters.

Input: String s.

Print length of smallest substring with maximum number of distinct characters.

Constraints:
1 ≤ size of str ≤ 10000

import java.util.HashMap;

public class LongestDistinctCharacters {

private static int findLongestDistinctCharacters(String s) {

HashMap<Character, Integer> seen = new HashMap<>();
int maximum_length = 0;

int start = 0;

for(int end = 0; end < s.length(); end++){

if(seen.containsKey(s.charAt(end))){

start = Math.max(start, seen.get(s.charAt(end)) + 1);
}

seen.put(s.charAt(end), end);

maximum_length = Math.max(maximum_length, end-start + 1);
}
return maximum_length;
}



public static void main(String[] args) {
String s = "abababcdefababcdab";
System.out.println(findLongestDistinctCharacters(s));
}
}

Output :
6

22. SMALLEST WINDOW IN A STRING CONTAINING ALL THE CHARACTERS OF ANOTHER STRING

Given a string S and text T. Output the smallest window in the string S having all characters of the text T. Both the string S and text T contains lowercase english alphabets.

Input: a string S and text T.

Output the smallest window of the string containing all the characters of the text. If such window doesn`t exist or this task can not be done then print -1.

Constraints:
1 <= |N|, |X| <= 1000

public class SmallestWindowWithCharsInString {
static final int no_of_chars = 256;

static String findSmallestWindowContainingT(String str, String pat){
int len1 = str.length();
int len2 = pat.length();

if (len1 < len2) {
System.out.println(-1);
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(-1);
return "";
}

return str.substring(start_index, start_index + min_len);
}

public static void main(String[] args)
{
String str1 = "timetopractise";
String pat1 = "toc";
System.out.print(findSmallestWindowContainingT(str1, pat1));

System.out.println();

String str2 = "zoomlazapzo";
String pat2 = "oza";
System.out.print(findSmallestWindowContainingT(str2, pat2));
}
}

Output :
toprac
apzo

23. POWER OF 2

Given a positive integer N. The task is to check if N is a power of 2. That is N is 2x for some x.

Input: a single positive integer N.

Output: Print YES if it is a power of 2 else NO

Constraints:
1 <= T <= 100
0 <= N <= 10^18

public class PowerOfTwo {
static boolean isPowerOfTwo (int x){

return x!=0 && ((x&(x-1)) == 0);

}

public static void main(String[] args)
{
System.out.println(isPowerOfTwo(1) ? "Yes" : "No");
System.out.println(isPowerOfTwo(98) ? "Yes" : "No");
}
}

Output :
Yes
No