Project 2

Arrays and Strings

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 <= 107">107107
1 <= Ai <= 1010">10101010

Solution :

Code :

package Project2;

import java.util.Scanner;

class Q1 {
public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the array: ");
int n = sc.nextInt();
int[] a = new int[n];
System.out.println("Enter the elements of the array: ");
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
System.out.println("Enter the sum value: ");
int s = sc.nextInt();
int[] result = subArraySum(a, n, s);
if (result[0] == -1) {
System.out.println("No subarray with given sum found");
} else {
System.out.println("Subarray with given sum starts from index " + result[0] + " to index " + result[1]);
}
}

public static int[] subArraySum(int[] a, int n, int s) {
int curr_sum = a[0], start = 0, end = 0, i = 1;
while (i <= n) {
while (curr_sum > s && start < i - 1) {
curr_sum = curr_sum - a[start];
start++;
}
if (curr_sum == s) {
end = i - 1;
break;
}
if (i < n) {
curr_sum = curr_sum + a[i];
}
i++;
}
if (curr_sum == s) {
return new int[] { start, end };
} else {
return new int[] { -1, -1 };
}
}
}

Output :

Enter the size of the array:
5
Enter the elements of the array:
1 2 3 7 5
Enter the sum value:
12
Subarray with given sum starts from index 1 to index 3

----------------------------------

Enter the size of the array:
10
Enter the elements of the array:
1 2 3 4 5 6 7 8 9 10
Enter the sum value:
15
Subarray with given sum starts from index 0 to index 4

Explain :

This code uses a two pointer approach, where one pointer starts at the beginning of the array and the other at the end. The sum of elements between these two pointers is computed, and if the sum is less than the target sum s, the end pointer is incremented. If the sum is greater than the target sum, the start pointer is incremented. If the sum is equal to the target sum, the subarray has been found and the starting and ending positions are returned.

-----------------------------------------------------------------------------------------------------------------------------------------------

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

Solution :

Code :

/**
*
*/
package Project2;

/**
* @author Hemant Kumar Sharma
*
*/
import java.util.Scanner;

public class Q2_PermutationsOfString {
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) {
System.out.println(prefix);
} else {
for (int i = 0; i < n; i++) {
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
}
}
}

public static void permutation(String str) {
permutation("", str);
}

public static void main(String[] args) {
@SuppressWarnings("resource")
Scanner scanner = new Scanner(System.in);
System.out.print("Enter a string: ");
String str = scanner.nextLine();
permutation(str);
}
}

Output:

Enter a string: ABC
ABC
ACB
BAC
BCA
CAB
CBA

--------------------------

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

Expalion :

This code uses the backtracking algorithm to find all permutations of a given string. The basic idea is to find all possible combinations of characters by adding one character at a time to a growing prefix. To find all permutations of a string, we start with an empty prefix and iterate through each character in the string, adding it to the prefix and recursively finding all permutations of the remaining characters.

In the permutation method, the first parameter is the growing prefix and the second is the remaining characters in the string. If the length of the remaining string is zero, that means we have found a permutation and we print it. If the length of the remaining string is not zero, we loop through each character in the string and add it to the prefix, and then recursively find all permutations of the remaining characters.

In the main method, we read the input string from the user and call the permutation method with the input string as the parameter

-----------------------------------------------------------------------------------------------------------------------------------------------

Trees

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

Solution :

Code :

package Project2;

import java.util.Vector;

class Nodep {
int data;
Nodep left;
Nodep right;

Nodep(int d) {
this.data = d;
this.left = null;
this.right = null;
}
}

public class TwoTreeAreIdl {

/* Function to traverse the tree in pre-order */
public void preorder(Nodep root, Vector<Integer> v) {
if (root == null) {
return;
}
v.add(root.data);
if (root.left != null) {
preorder(root.left, v);
} else {
v.add(0);
}
if (root.right != null) {
preorder(root.right, v);
} else {
v.add(0);
}
}

/* Function to check if two trees are identical */
public boolean isIdentical(Nodep root1, Nodep root2) {
Vector<Integer> v = new Vector<Integer>();
Vector<Integer> x = new Vector<Integer>();
preorder(root1, v);
preorder(root2, x);
return v.equals(x);
}

public static void main(String[] args) {
Nodep root1 = new Nodep(1);
root1.left = new Nodep(9);
root1.right = new Nodep(8);
root1.left.left = new Nodep(7);

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

TwoTreeAreIdl main = new TwoTreeAreIdl();
// Function call
if (main.isIdentical(root1, root2)) {
System.out.println("Both the trees are identical.");
} else {
System.out.println("Given trees are not identical.");
}
}
}

Output :

Both the trees are identical.

-----------------------------------------------------------------------------------------------------------------------------------------------

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.

For example:

COUNT LEAVES IN BINARY TREE

For the above tree, the string will be: 5 2 3 1 N 7 4 N 8 N 6 N N Complete the function countLeaves() that takes the tree string as parameter and returns the count of leaves in tree.

Constraints:
1<= N <= 104">104104

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).
H is the height of the tree.

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

-----------------------------------------------------------------------------------------------------------------------------------------------

Sorting

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 <= 103">103103

Solution :

Code:

package Project2;

class Node {
int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

public class SortingLinklist {
Node head;

void push(int new_data) {
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}

Node segregate(Node head) {
Node zeroDummy = new Node(0);
Node oneDummy = new Node(0);
Node twoDummy = new Node(0);
Node zeroTail = zeroDummy, oneTail = oneDummy, twoTail = twoDummy;

Node curr = head;
while (curr != null) {
if (curr.data == 0) {
zeroTail.next = curr;
zeroTail = curr;
} else if (curr.data == 1) {
oneTail.next = curr;
oneTail = curr;
} else {
twoTail.next = curr;
twoTail = curr;
}
curr = curr.next;
}

zeroTail.next = (oneDummy.next != null) ? (oneDummy.next) : (twoDummy.next);
oneTail.next = twoDummy.next;
twoTail.next = null;

return zeroDummy.next;
}

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

public static void main(String args[]) {
SortingLinklist llist = new SortingLinklist();
llist.push(1);
llist.push(2);
llist.push(2);
llist.push(1);
llist.push(2);
llist.push(0);
llist.push(2);
llist.push(2);

System.out.println("Linked List before segregation ");
llist.printList();

llist.head = llist.segregate(llist.head);

System.out.println("Linked List after segregation ");
llist.printList();
}
}

Output :

Linked List before segregation
2 2 0 2 1 2 2 1
Linked List after segregation
0 1 1 2 2 2 2 2

Explain :

In this code, we first count the number of 0s, 1s, and 2s in the linked list. and we first create three dummy nodes zeroDummy, oneDummy, and twoDummy, which will be used to store the 0s, 1s, and 2s respectively. We also create three pointers zeroTail, oneTail, and twoTail, which will keep track of the tail of the three linked lists.Next, we loop through the linked list, and based on the data value of each node, we append it to the appropriate linked list. For nodes with data value 0, we append it to the linked list zeroDummy, for nodes with data value 1, we append Then we iterate through the linked list, setting the data of each node to 0, 1, or 2 depending on the counts of 0s, 1s, and 2s. Finally, we return the head of the modified linked list. The time complexity of this code is O(n), where n is the number of nodes in the linked list. The auxiliary space used is O(1).

-----------------------------------------------------------------------------------------------------------------------------------------------

Searching

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| <=104">104104

Solution :

Code:

package Project2;

import java.util.Scanner;

public class Searching_FirstRepeatedCharacter {
Scanner in = new Scanner(System.in);

public static void main(String[] args) {
Searching_FirstRepeatedCharacter frc = new Searching_FirstRepeatedCharacter();
frc.mainLoop();
}

void mainLoop() {
String str = " ";
System.out.println("Please enter a string: ");
str = in.next();
str = str.toLowerCase();
for (int i = 0; i < str.length(); i++) {
char character = str.charAt(i);
int firstIndex = str.indexOf(character);
int lastIndex = str.lastIndexOf(character);
if (firstIndex != lastIndex) {
System.out.println("The character '" + character + "' is repeated");
break;
}
}
}
}

Output :

Please enter a string:
Skilllync
The character 'l' is repeated

------------

Please enter a string:
helloworld
The character 'l' is repeated

-----------------------------------------------------------------------------------------------------------------------------------------------

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 <= 107">107107
1 <= A[],B[] <= 1018">10181018

Solution:

Code:

package Project2;

import java.util.Scanner;

public class FindTwo_Array_EqualOrNot {
public static void main(String args[]) {
int[] a1 = new int[50];
int[] a2 = new int[50];
System.out.println("enter size of array 1 : ");
@SuppressWarnings("resource")
Scanner sc = new Scanner(System.in);
int size1 = sc.nextInt();
System.out.println("enter element : ");
for (int i = 0; i < size1; i++)
a1[i] = sc.nextInt();
System.out.println("enter size of array2 : ");
int size2 = sc.nextInt();
System.out.println("enter element : ");
for (int i = 0; i < size2; i++)
a2[i] = sc.nextInt();
if (a1 == a2)
System.out.println(">>>>> 1");
else
System.out.println(">>>>> 0");
}
}

Output :

enter size of array 1 :
5
enter element :
1
2
5
4
0
enter size of array2 :
5
enter element :
2
4
5
0
1
>>>>> 0

-----------

enter size of array 1 :
3
enter element :
1
2
5
enter size of array2 :
3
enter element :
2
4
15
>>>>> 0

Explain :

This program uses a Scanner to read input from the user, allowing them to specify the size and elements of two arrays. The program then checks if the arrays are equal by comparing their sizes and the values of their elements. If the arrays have the same size and all their elements are equal, the program outputs "Arrays are equal." Otherwise, it outputs "Arrays are not equal."

-----------------------------------------------------------------------------------------------------------------------------------------------

Hashing

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[] <= 106">106106

Explain :

Code :

package Project2;

import java.util.Arrays;

public class RelativeSorting {

static int first(int arr[], int low, int high, int x, int n) {
if (high >= low) {
/* (low + high)/2; */
int mid = low + (high - low) / 2;

if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
return mid;
if (x > arr[mid])
return first(arr, (mid + 1), high, x, n);
return first(arr, low, (mid - 1), x, n);
}
return -1;
}

static void sortAccording(int A1[], int A2[], int m, int n) {
int temp[] = new int[m], visited[] = new int[m];
for (int i = 0; i < m; i++) {
temp[i] = A1[i];
visited[i] = 0;
}

// Sort elements in temp
Arrays.sort(temp);

// for index of output which is sorted A1[]
int ind = 0;

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

int f = first(temp, 0, m - 1, A2[i], m);

if (f == -1)
continue;

// Copy all occurrences of A2[i] to A1[]
for (int j = f; (j < m && temp[j] == A2[i]); j++) {
A1[ind++] = temp[j];
visited[j] = 1;
}
}

// Now copy all items of temp[] which are
// not present in A2[]
for (int i = 0; i < m; i++)
if (visited[i] == 0)
A1[ind++] = temp[i];
}

static void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}

// Driver program to test above function.
public static void main(String args[]) {
// int A1[] = { 2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8 };
// int A2[] = { 2, 1, 8, 3 };
int A1[] = { 2, 6, 7, 5, 2, 6, 8, 4 };
int A2[] = { 2, 6, 4, 5 };
int m = A1.length;
int n = A2.length;
System.out.println("Sorted array is ");
sortAccording(A1, A2, m, n);
printArray(A1, m);
}
}

Output :

Sorted array is
2 2 1 1 8 8 3 5 6 7 9

--------------------

Sorted array is
2 2 6 6 4 5 7 8

Explain:

This program allowing them to specify the size and elements of two arrays. The program then uses a HashMap to store the elements of the second array and their corresponding indices. The first array is sorted relative to the order of elements in the second array by adding elements that are present in the HashMap to a temporary ArrayList, then sorting that : Sort A1[0..m-1] according to the order , defined by A2[0..n-1]., The temp array is used to store a copy of A1[] and visited[] is used to mark the visited elements in temp[].and Consider all elements of A2[], find them in temp[] and copy to A1[] in order. Find index of the first occurrence of A2[i] in temp Utility function to print an array

-----------------------------------------------------------------------------------------------------------------------------------------------

Graph

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

Solution for Graph SHORTEST SOURCE TO DESTINATION PATH :

Code :

package Project2;

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

public class ShortestSourceToDestination {
static final int ROW = 20;
static final int COL = 20;
static int row[] = { -1, 0, 0, 1 };
static int col[] = { 0, -1, 1, 0 };

static boolean isValid(int mat[][], boolean visited[][], int x, int y) {
return (x >= 0) && (x < ROW) && (y >= 0) && (y < COL) && mat[x][y] == 1 && !visited[x][y];
}

static int BFS(int mat[][], int x, int y, int destX, int destY) {
boolean visited[][] = new boolean[ROW][COL];

visited[0][0] = true;

Queue queue = new LinkedList<>();
queue.add(new Nodes(0, 0, 0));

while (!queue.isEmpty()) {
Nodes node = queue.poll();

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

if (i == destX && j == destY)
return dist;

for (int k = 0; k < 4; k++) {
int x1 = i + row[k];
int y1 = j + col[k];

if (isValid(mat, visited, x1, y1)) {
visited[x1][y1] = true;
queue.add(new Nodes(x1, y1, dist + 1));
}
}
}
return -1;
}

@SuppressWarnings("resource")
public static void main(String args[]) {
System.out.println("Enter Matrix Row & column : ");
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println("Enter Matrix elements : ");
int m = sc.nextInt();
int mat[][] = new int[ROW][COL];

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mat[i][j] = sc.nextInt();
}
}
System.out.println("Enter Destination Point : ");
int x = sc.nextInt();
int y = sc.nextInt();

System.out.println("Minimum number of steps required to reach the destination: " + BFS(mat, 0, 0, x, y));
}
}

class Nodes {
int x, y, dist;

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

Output :

Enter Matrix Row & column :
3 4
Enter Matrix elements :
1 0 0 0 1 1 0 1 0 1 1 1
Enter Destination Point :
2 3
Minimum number of steps required to reach the destination: 5

----------------------------

Enter Matrix Row & column :
3 4
Enter Matrix elements :
1 1 1 1 0 0 0 1 0 0 0 1
Enter Destination Point :
0 3
Minimum number of steps required to reach the destination: 3

Explain :

This code implements a Breadth First Search (BFS) algorithm to find the shortest path from the source (0, 0) to the destination (x, y) in the given matrix. The BFS function takes in the matrix, its dimensions n and m, the destination coordinates x and y, and returns the minimum number of steps needed to reach the destination. The algorithm starts by adding the source cell (0, 0) to a queue and marking it as visited. It then repeatedly pops the first cell from the queue, checks if it's the destination, and adds all its unvisited neighbors to the queue. The distance of each neighbor is calculated as the distance of the current cell plus one. The algorithm continues until the destination is found or the queue becomes empty, in which case the destination is unreachable.

-----------------------------------------------------------------------------------------------------------------------------------------------

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 an 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

Solution :

Code :

package Project2;

import java.io.IOException;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MinimumCostPath {

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];
}

// Driver code
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));
}
}

Output :

327

Explain :

* Custom class for representing
*row-index, column-index &
*distance of each cell

* Custom comparator for inserting cells into Priority Queue

* Utility method to check whether current cell is inside grid or not

* Method to return shortest path from
top-corner to bottom-corner in 2D grid

* Initializing distance array by INT_MAX

* Initialized source distance as initial grid position value

*Insert source cell to priority queue

* If Cell is already been reached once,
remove it from priority queue and Insert cell with updated distance

* and then when we excuate { { 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 } }; then get output are 327

-----------------------------------------------------------------------------------------------------------------------------------------------

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

-----------------------------------------------------------------------------------------------------------------------------------------------

Stacks queues

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

-----------------------------------------------------------------------------------------------------------------------------------------------

Heap

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

-----------------------------------------------------------------------------------------------------------------------------------------------

Dynamic programming

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”}.

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

Testcase 1: All the increasing subsequences are : (1,101); (1,2,3,100); (1,2,3,4,5). Out of these (1, 2, 3, 100) has maximum sum,i.e., 106.

-----------------------------------------------------------------------------------------------------------------------------------------------

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

-----------------------------------------------------------------------------------------------------------------------------------------------

Greedy

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

-----------------------------------------------------------------------------------------------------------------------------------------------

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 <= 107">107107
1 <= A[], B[] <= 1018">10181018

-----------------------------------------------------------------------------------------------------------------------------------------------

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)

Solution :

Code :

Output :

Explain :

-----------------------------------------------------------------------------------------------------------------------------------------------

Two pointer & sliding window

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

Solutrion for Two pointer & sliding window LONGEST DISTINCT CHARACTERS IN STRING :

Code:

package Project2;

import java.util.HashMap;
import java.util.Scanner;

public class LongestDistinctSubstring {
@SuppressWarnings("resource")
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the string: ");
String str = sc.nextLine();

int result = findLongestDistinctSubstring(str);
System.out.println("The length of the longest substring with distinct characters is: " + result);
}

public static int findLongestDistinctSubstring(String str) {
int len = str.length();

// Create a hashmap to store the last index of each character in the string
HashMap<Character, Integer> charLastIndex = new HashMap<>();

int start = 0, maxLength = 0;
for (int end = 0; end < len; end++) {
char ch = str.charAt(end);

if (charLastIndex.containsKey(ch) && charLastIndex.get(ch) >= start) {
start = charLastIndex.get(ch) + 1;
}

charLastIndex.put(ch, end);
maxLength = Math.max(maxLength, end - start + 1);
}

return maxLength;
}
}

Output:

Enter the string: abababcdefababcdab
The length of the longest substring with distinct characters is: 6

Explain :

This program takes a string as input from the user, and returns the length of the longest substring with distinct characters in the string.

-----------------------------------------------------------------------------------------------------------------------------------------------

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

Solution for SMALLEST WINDOW IN A STRING CONTAINING ALL THE CHARACTERS OF ANOTHER STRING

Code :

package Project2;

import java.util.HashMap;
import java.util.Scanner;

public class SmallestWindowString {
@SuppressWarnings("resource")
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the main string: ");
String mainString = sc.nextLine();
System.out.print("Enter the string to find in the main string: ");
String subString = sc.nextLine();

String result = findSmallestWindow(mainString, subString);
System.out
.println("The smallest window in the main string containing all the characters of the input string is: "
+ result);
}

public static String findSmallestWindow(String mainString, String subString) {
int len1 = mainString.length();
int len2 = subString.length();

// Edge case: If the main string is shorter than the input string, return an
// empty string
if (len1 < len2) {
return "";
}

// Create a hashmap to store the frequency of each character in the input string
HashMap<Character, Integer> charFrequency = new HashMap<>();
for (int i = 0; i < len2; i++) {
char ch = subString.charAt(i);
charFrequency.put(ch, charFrequency.getOrDefault(ch, 0) + 1);
}

int start = 0, startIndex = -1, minLength = Integer.MAX_VALUE, count = 0;
for (int end = 0; end < len1; end++) {
char ch = mainString.charAt(end);

if (charFrequency.containsKey(ch)) {
charFrequency.put(ch, charFrequency.get(ch) - 1);
if (charFrequency.get(ch) >= 0) {
count++;
}
}

while (count == len2) {
if (end - start + 1 < minLength) {
startIndex = start;
minLength = end - start + 1;
}

char c = mainString.charAt(start);
if (charFrequency.containsKey(c)) {
charFrequency.put(c, charFrequency.get(c) + 1);
if (charFrequency.get(c) > 0) {
count--;
}
}
start++;
}
}

if (startIndex == -1) {
return "";
}

return mainString.substring(startIndex, startIndex + minLength);
}
}

Output :

Enter the main string: Timetoprictice
Enter the string to find in the main string: toc
The smallest window in the main string containing all the characters of the input string is: topric

-------------------------------------------

Enter the main string: zoomlazapzo
Enter the string to find in the main string: oza
The smallest window in the main string containing all the characters of the input string is: apzo

Expalain :

This program takes two strings as input from the user, and returns the smallest window in the main string containing all the characters of the input string. If no such window exists, it returns an empty string.

-----------------------------------------------------------------------------------------------------------------------------------------------

Bit Manipulation

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 <= 1018">10181018

Solution for Bit Manipulation POWER OF 2

Code :

package Project2;

import java.util.Scanner;

public class PowerOfTwo {
@SuppressWarnings("resource")
public static void main(String[] args) {
System.out.println("Enter Number : ");
Scanner scan = new Scanner(System.in);
long n = scan.nextLong();
if ((n & (n - 1)) == 0) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}

Output :

Enter Number :
1
YES

-----------------

Enter Number :
98
NO

Explain :

• n & (n-1) == 0 is used to check if n is a power of 2.
• For example, if n = 4, then n - 1 = 3, and 4 & 3 = 0, which means 4 is a power of 2.
• If n is not a power of 2, then n & (n-1) will not equal 0. For example, if n = 5, then n - 1 = 4, and 5 & 4 = 1, which means 5 is not a power of 2.

-----------------------------------------------------------------------------------------------------------------------------------------------