Project 2

1.

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 // edge case where sum = 0
if(s == 0){
break;
}

// keep adding elements to sum
sum += arr[i];

// while sum greater than s start subtracting from the beginning and moving the left moving to the right
while(sum > s){
sum -= arr[left];
left++;
}

// when sum becomes equal to our target sum, we return the indices
if(sum == s){
System.out.println(left + " " + right);
break;
}
right++;
}

// if no subarray sum equal to target sum was found
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);
}
}

2

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++){
//Swapping the string by fixing a character
str = swap(str,l,i);
//Recursively calling function permute() for rest of the characters
permute(str, l+1, r);
//Backtracking and swapping the characters again.
str = swap(str,l,i);
}
}
}

// function to convert string to characters and then swap them and re convert to string
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);
}
}

3

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

}
}

4

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

7

import java.util.HashMap;

public class FindFirstRepeatedChar {

void findFirstRepeatedChar(String s){
if(s.length() <= 0){
System.out.println("No string found");
}
HashMap hM = new HashMap();
for(int i = 0; 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 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);
}
}

8

import java.util.HashMap;

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

// If lengths of arrays are not equal
if (n != m){
return false;
}

// Store arr1[] elements and their counts in
// hash map
HashMap map = new HashMap();
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);
}
}

// Traverse arr2[] elements and check if all elements of arr2[] are present same number of times or not.
for (int i = 0; i < n; i++) {
// If there is an element in arr2[], but not in arr1[]
if (!map.containsKey(arr2[i])){
return false;
}
// If an element of arr2[] appears more times than it appears in arr1[]
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);
}
}
}

13

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

public class FirstNonRepeatingChar {
final static int MAX_CHAR = 26;

static void firstNonRepeatingChar(String str){
// create count array of size 26(assuming only lower case characters are present)
int[] charCount = new int[MAX_CHAR];

// Queue to store Characters
Queue q = new LinkedList();

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

// push each character in queue
if(charCount[ch - 'a'] == 0 ){
q.add(ch);
}

// increment the frequency count
charCount[ch - 'a']++;

// check for the non repeating character
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);
}
}

15

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

public class LongestCommonSubSeq {
public static int findLCS(String X, String Y, int m, int n, Map lookup)
{
// return if the end of either string is reached
if (m == 0 || n == 0) {
return 0;
}

// construct a unique map key from dynamic elements of the input
String key = m + "|" + n;

// if the subproblem is seen for the first time, solve it and store its result in a map
if (!lookup.containsKey(key))
{
// if the last character of `X` and `Y` matches
if (X.charAt(m - 1) == Y.charAt(n - 1)) {
lookup.put(key, findLCS(X, Y, m - 1, n - 1, lookup) + 1);
}
else {
// otherwise, if the last character of `X` and `Y` don't match
lookup.put(key, Integer.max(findLCS(X, Y, m, n-1, lookup), findLCS(X, Y, m - 1, n, lookup)));
}
}

// return the subproblem solution from the map
return lookup.get(key);
}

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

// create a map to store solutions to subproblems
Map lookup = new HashMap<>();

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

17

public class MaxSumOfIncreasingSubSequence {

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

/* Initialize msum_arr values for all indexes */
for (i = 0; i < n; i++){
msum_arr[i] = arr[i];
}

/* Compute maximum sum values in bottom up manner */
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];
}
}
}

/* Pick maximum of all msum_arr values */
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));
}
}