Challenge

Project 2

SShivam Kumar19 Oct 2022

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

Ans:-

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++){
// 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);
}
}

Output :
1 3
0 4

Time Complexity : O(n) as we are looping through n elments of the array
Space Complexity : O(1) as we are not using any extra space

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

Ans:-

We can solve this problem by using backtracking approach:-

Procedure:-

a) We fix a character in the first position and swap the rest of the character with the first character. Like in ABC, in the first iteration three string are formed : ABC, BAC, CBA by swapping A with A, B and C respectively.
b) We repeat step 1 for rest of the characters like fixing second character B and so on.
c) Now we swap again to go back to the previous position. Eg : from ABC, we formed ABC by fixing B again, and we backtrack to the previous position and swap B with C. So now we got ABC and ACB.
d) Thus, we repeat the above for BAC and CBA to get all permutations.

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

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.

Time Complexity : O(n * n!) as it there are n! permutations which it takes O(n) time to print each permutation
Space Complexity : O(n) as we create a char array with length of characters of string.

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

Ans:-

Two trees are identical when they have same data and arrangement of data is also same. To identify if two trees are identical, we need to traverse both trees simultaneously, and while traversing we need to compare data and children of the trees.

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

Time Complexity : O(m). Complexity will be according to the tree with lesser number of nodes. Let number of nodes in two trees be n and m then complexity of isIdentical() will be O(n) where n < m.
Space Complexity : O(H) if we take into consideration the implicit stack for the various recursion calls to the subtrees of H height.

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.

Ans:-

class Count_leav {
//node class that defines BST node
class Node {
int key;
Node left, right;

public Node(int data){
key = data;
left = right = null;
}
}
// BST root node
Node root;

// Constructor for BST =>initial empty tree
BST_class(){
root = null;
}
//delete a node from BST
void deleteKey(int key) {
root = delete_Recursive(root, key);
}

//recursive delete function
Node delete_Recursive(Node root, int key) {
//tree is empty
if (root == null) return root;

//traverse the tree
if (key < root.key) //traverse left subtree
root.left = delete_Recursive(root.left, key);
else if (key > root.key) //traverse right subtree
root.right = delete_Recursive(root.right, key);
else {
// node contains only one child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;

// node has two children;
//get inorder successor (min value in the right subtree)
root.key = minValue(root.right);

// Delete the inorder successor
root.right = delete_Recursive(root.right, root.key);
}
return root;
}

int minValue(Node root) {
//initially minval = root
int minval = root.key;
//find minval
while (root.left != null) {
minval = root.left.key;
root = root.left;
}
return minval;
}

// insert a node in BST
void insert(int key) {
root = insert_Recursive(root, key);
}

//recursive insert function
Node insert_Recursive(Node root, int key) {
//tree is empty
if (root == null) {
root = new Node(key);
return root;
}
//traverse the tree
if (key < root.key) //insert in the left subtree
root.left = insert_Recursive(root.left, key);
else if (key > root.key) //insert in the right subtree
root.right = insert_Recursive(root.right, key);
// return pointer
return root;
}

// method for inorder traversal of BST
void inorder() {
inorder_Recursive(root);
}

// recursively traverse the BST
void inorder_Recursive(Node root) {
if (root != null) {
inorder_Recursive(root.left);
System.out.print(root.key + " ");
inorder_Recursive(root.right);
}
}

boolean search(int key) {
root = search_Recursive(root, key);
if (root!= null)
return true;
else
return false;
}

//recursive insert function
Node search_Recursive(Node root, int key) {
// Base Cases: root is null or key is present at root
if (root==null || root.key==key)
return root;
// val is greater than root's key
if (root.key > key)
return search_Recursive(root.left, key);
// val is less than root's key
return search_Recursive(root.right, key);
}
}
class Main{
public static void main(String[] args) {
//create a BST object
BST_class bst = new BST_class();
/* BST tree example

//insert data into BST
bst.insert(5);
bst.insert(2);
bst.insert(1);
bst.insert(N);
bst.insert(8);
bst.insert(3);

bst.insert(7);
bst.insert(9);
bst.insert(6);

bst.insert(4);
bst.insert(N);
bst.insert(N);
//print the BST
System.out.println("The BST Created with input data(Left-root-right):");
bst.inorder();

//delete leaf node
System.out.println("\nThe BST after Delete 12(leaf node):");
bst.deleteKey(12);
bst.inorder();
//delete the node with one child
System.out.println("\nThe BST after Delete 90 (node with 1 child):");
bst.deleteKey(90);
bst.inorder();

//delete node with two children
System.out.println("\nThe BST after Delete 45 (Node with two children):");
bst.deleteKey(45);
bst.inorder();
//search a key in the BST
boolean ret_val = bst.search (50);
System.out.println("\nKey 50 found in BST:" + ret_val );
ret_val = bst.search (12);
System.out.println("\nKey 12 found in BST:" + ret_val );
}
}

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

Ans:-

The idea is to traverse the tree starting from the root. If any of the given keys (n1 and n2) matches with the root, then the root is LCA (assuming that both keys are present). If the root doesn’t match with any of the keys, we recur for the left and right subtree and call LCA again. The node which has one key present in its left subtree and the other key present in the right subtree will be the LCA. If both keys lie in the left subtree, then the left subtree has LCA also, otherwise, LCA lies in the right subtree.

public class LCAOfBT {
Node root;

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

// This function returns pointer to LCA of two given
// values n1 and n2. This function assumes that n1 and
// n2 are present in Binary Tree
Node findLCA(Node node, int n1, int n2)
{
// Base case
if (node == null)
return null;

// If either n1 or n2 matches with root's key, report
// the presence by returning root (Note that if a key is
// ancestor of other, then the ancestor key becomes LCA
if (node.key == n1 || node.key == n2)
return node;

// Look for keys in left and right subtrees
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);

// If both of the above calls return Non-NULL, then one key
// is present in once subtree and other is present in other,
// So this node is the LCA
if (left_lca!=null && right_lca!=null)
return node;

// Otherwise check if left subtree or right subtree is LCA
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

Time Complexity : O(n) as we have to traverse n nodes in a tree
Space Complexity : O(H) if we take into consideration the implicit stack for the various recursion calls to the subtrees of H height.

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

Ans:-

We can solve this problem by two approaches. In the first appraoch, we traverse the list and count the number of 0s, 1s and 2s. Let's assume the counts to be n1, n2 and n3 respectively. Next, we traverse the list once more and fill the first n1 nodes with 0, then n2 nodes with 1 and n3 nodes with 2. The time complexity for this approach would be O(n) and space complexity would be O(1) but this method would not work if the values are associated with some data. For eg : let's say the 3 values represent 3 different colours and different types of objects are assiciated with the colours and we need to sort the objects based on that.

So a better approach would be to sort the list by changing the links between the different nodes. In this method, we iterate through the linked list while maintaining 3 pointers named List0, List1 and List2 to point to current ending nodes of linked lists containing 0, 1, and 2 respectively. For every traversed node, we attach it to the end of its corresponding list. Finally, we link all three lists. To avoid many null checks, we use three dummy pointers head0, head1 and head2 that work as dummy headers of three lists.

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

// Create three dummy nodes to point to beginning of three linked lists. These dummy nodes are created to avoid many null checks.
Node head0 = new Node(0);
Node head1 = new Node(0);
Node head2 = new Node(0);

// Initialize current pointers for three lists and whole list.
Node List0 = head0, List1 = head1, List2 = head2;

// Traverse list
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;
}
}

// Attach three lists
List0.next = (head1.next!=null) ? (head1.next) : (head2.next);
List1.next = head2.next;
List2.next = null;

// Updated head
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

Time Complexity : O(n) since we need to traverse n nodes in the list
Space Complexity : O(1) as we do not utilise any extra space

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

Ans:-

In the brute force approach, we can run two nested loops. We start traversing from left side and for every character, we check if it repeats or not. If the character repeats, increment count of repeating characters. When the count becomes greater than 1, return the character. Time Complexity of this solution is O(n2) which is not going to be efficient.

Another approach is to use Sorting to solve the problem in O(nLog n) time. First we convert the string into array of its characters. Next, we first copy the given array to an auxiliary array temp[]. We sort the temp array using a O(nLogn) time complexity sorting algorithm. Lastly, we loop through the input array from left to right. For every element, count its occurrences in temp[] using binary search. As soon as we find a character that occurs more than once, we return the character. This step can be done in O(NLog N) time.

A better approach than both the above solutions would be to use hashing technique. We create a empty hash table. Next, we loop through the string and for every character we store its index and its count as key and value respectively. Then we loop through the table again and check if any of the values are greater than 1, then we return it and break out of the loop. If no value if found and the loop has reached the end, we print -1.

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

Time Complexity : O(n) as we loop through n characters of the string s
Space Complexity : O(n) as we create a hash map for n characters in the string.

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

Ans:-

In the brute force approach, we sort both arrays and then linearly compare elements. If we are using Arrays.sort() to sort the elements, the time complexity would be O(nLogn) and space complexity would be O(1).

Also, another equivalent approach to hashing will be sorting in linear time. We can use count sort to sort both the arrays in linear time and then compare elements linearly. This method too takes O(n) time complexity and O(n) space complexity.

A better approach would be to use hashing where we store all elements of arr1[] and their counts in a hash table. Then we traverse arr2[] and check if the count of every element in arr2[] matches with the count in arr1[]. This method takes O(n) time complexity for looping through n elements of the arrays and O(n) space complexity for creating hash table. Below is this implementation.

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

// 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);
}
}
}
Output :
1
0

Time Complexity : O(n). It takes O(n) time to go through array once and take count of all elements and store in hashmap and then we traverse the array again to check if the count of every element in arr2 matches arr1. So total time complexity will be O(n) + O(n) = O(2n) = O(n).

Space Complexity : O(n) as we utilise extra space of n elements to create the hashmap.

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

Ans:-

We can use hashing technique to solve this problem. We first sort the arr1 using Arrays.sort(). Next, we create a hashMap with keys as elements of the arr1 and values as their counts. We loop through arr1 and store count of every number in the hashMap. Next, we loop through arr2 and check if the element is present in hashmap, if it is then we put it in the output array that many number fo times and remove the element from the hashMap. Finally, we loop through the arr1 again and add the rest of the elements to the end of the output array in sorted order and we print the output array.

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

// first sort the array
Arrays.sort(arr1); //O(nLogn)

// create hashmap and put keys as elements of the array and values as their counts
HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>();
for(int i = 0; i<arr1.length; i++){ // O(n)
int counter = 0;
// we check if value already present, if it is we increment counter else we put the new value
if(hM.containsKey(arr1[i])){
counter = hM.get(arr1[i]);
}
hM.put(arr1[i], counter+1);
}

// create an output array
ArrayList output = new ArrayList();

// for each element in arr2, if it is present in arr1 add it to the output list, its value (count) number of times. Remove elements from the hashmap once added
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]);
}
}

// loop through elements in arr1 and check if present in hashmap, and similarly add them to the output array
for(int n = 0; n
Output :
2 2 1 1 8 8 3 5 6 7 9
2 2 6 6 4 5 7 8

Time Complexity : O(nLogn). The Arrays.sort() method takes O(nLogn) to sort the array. The rest of the for loops each take O(n) time individually so a total of all of them would still be O(n). So we have O(nLogn + n) time complexity, since the former is the larger term the overall time complexity would be O(nLogn)

Space Complexity : O(n) as we use extra space to create hash map and output array.

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

Ans:-

We can solve this problem using Lee's Algorithm. It follows the Bread First Search approach.
Steps :
a) Create an empty queue and enqueue the source cell having a distance 0 from the source (itself) and mark it as visited.
b) Loop till queue is empty and do the following :
i) Dequeue the front node
ii) If the popped node is the destination node, then return its distance
iii) Otherwise, for each of the four adjacent cells of the current cell, enqueue each valid cell with +1 diatance and mark them as visited
c) If all the queue nodes are processed and the destination is not reached, then return -1.

Note tht in BFS, all cells having the shortest path as 1 are visited first, followed by their adjacent cells having the shortest path as 1 + 1 = 2 and so on.. So if we reach any node in BFS, its shortest path is one more than the shortest path of the parent. So, the destination cell's first occurance gives us the result and we can stop our search there. It is impossible that the shortest path exists from some other cell for which we haven't reached the given node yet. If such path were possible, we would have already explored it.

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

class Node
{
// (x, y) represents matrix cell coordinates, and dist represents their minimum distance from the source
int x, y, dist;

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

public class ShortestSourceToDestinationPath {
// M × N matrix
private static final int M = 3;
private static final int N = 4;

// Below arrays detail all four possible movements from a cell(left, up, right, down)
private static final int[] row = { -1, 0, 0, 1 };
private static final int[] col = { 0, -1, 1, 0 };

// Function to check if it is possible to go to position (row, col) from the current position. The function returns false if (row, col) is not a valid position or has a value 0 or already visited.
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];
}

// Find the shortest possible route in a matrix mat from source cell (i, j) to destination cell (x, y)
private static void BFS(int mat[][], int i, int j, int x, int y)
{
// construct a matrix to keep track of visited cells
boolean[][] visited = new boolean[M][N];

// create an empty queue
Queue q = new ArrayDeque<>();

// mark the source cell as visited and enqueue the source node
visited[i][j] = true;
q.add(new Node(i, j, 0));

// stores length of the longest path from source to destination
int min_dist = Integer.MAX_VALUE;

// loop till queue is empty
while (!q.isEmpty())
{
// dequeue front node and process it
Node node = q.poll();

// (i, j) represents a current cell, and dist stores its minimum distance from the source
i = node.x;
j = node.y;
int dist = node.dist;

// if the destination is found, update min_dist and stop
if (i == x && j == y)
{
min_dist = dist;
break;
}

// check for all four possible movements from the current cell and enqueue each valid movement
for (int k = 0; k < 4; k++)
{
// check if it is possible to go to position (i + row[k], j + col[k]) from current position
if (isValid(mat, visited, i + row[k], j + col[k]))
{
// mark next cell as visited and enqueue it
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)
{
// input maze
int[][] mat =
{
{ 1, 0, 0, 0},
{ 1, 1, 0, 1},
{ 0, 1, 1, 1}
};

// Find the shortest path from source (0, 0) to destination (7, 5)
BFS(mat, 0, 0, 2, 3);
}
}
Output :
5

Time Complexity : O(M x N) where M and N are dimensions of the matrix
Space Complexity : O(M x N) used to create the visited array of size M x N

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

Ans:-

We solve this problem using dijkstra's algorithm. Each cell of grid represents a vertex and neighbor cells adjacent vertices. We do not make an explicit graph from these cells instead we will use matrix as it is in our dijkstra’s algorithm.

a) Create an empty priorityqueue with a distanceComparator and enqueue the source cell and put its distance in dist array. Initially dist array is initialised with all values as Integer.MAX_VALUE.
b) We Loop till queue is empty and do the following :
i) Dequeue the front node
ii) We check in all 4 directions of the popped node for the minimum cost and then if it is not already reached. If it is reached we remove it from the queue else we insert this cell in the priority queue and also update the distance.
c) We repeat the same process until we reach end of matrix.

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

public class MinimumCostPath {
// Below arrays detail all four possible movements from a cell (left, top, right, bottom)
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;
}
}

// Custom comparator for inserting cells into Priority Queue
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;
}
}
}

// Utility method to check whether current cell isValid or not
static boolean isValid(int i, int j, int M, int N)
{
return (i >= 0 && i < M && j >= 0 && j < N);
}

// Method to return shortest path from top-corner to bottom-corner in 2D grid
static int shortestPath(int[][] grid, int M, int N)
{
int[][] dist = new int[M][N];

// Initializing distance array by INT_MAX
for(int i = 0; i < M; i++)
{
for(int j = 0; j < N; j++)
{
dist[i][j] = Integer.MAX_VALUE;
}
}

// Initialized source distance as initial grid position value
dist[0][0] = grid[0][0];

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

// Insert source cell to priority queue
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 Node is already been reached once, remove it from priority queue
if (dist[R][C] != Integer.MAX_VALUE)
{
Node adj = new Node(R, C, dist[R][C]);
pq.remove(adj);
}

// Insert cell with updated distance
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

Time Complexity :
Space Complexity : O(M x N) used to create the dist array of size M x N

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

Ans:-

We solve this problem by treating this as a graph problem, where vertices will be the first and last character of strings, and we will draw an edge between two vertices if they are the first and last character of the same string, so a number of edges in the graph will be same as the number of strings in the array. If a loop among graph vertices is possible then, we can reorder the strings such that circle is possible otherwise we cannot. Now to check whether a graph can have a loop which goes through all the vertices, we’ll check two conditions :

1. Indegree and Outdegree of each vertex should be the same.
2. The graph should be strongly connected.
The first condition can be checked easily by keeping two arrays, in and out for each character. For checking whether a graph is having a loop which goes through all vertices is the same as checking complete directed graph is strongly connected or not because if it has a loop which goes through all vertices then we can reach to any vertex from any other vertex that is, the graph will be strongly connected and the same argument can be given for reverse statement also.

Now for checking the second condition we will just run a DFS from any character and visit all reachable vertices from this, now if the graph has a loop then after one DFS all vertices should be visited, if all vertices are visited then we will return true otherwise false so visiting all vertices in a single DFS flags a possible ordering among strings.

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

// Process all strings one by one
for(int i = 0; i < n; i++)
{

// Find first and last characters
int f = (int)(s[i].charAt(0) - 'a');
int l = (int)(s[i].charAt(s[i].length() - 1) - 'a');

// Mark the characters
mark[f] = mark[l] = true;

// Increase indegree and outdegree count
in[l]++;
out[f]++;

// Add an edge in graph
adj.get(f).add(l);
}

// If for any character indegree is not equal to outdegree then ordering is not possible
for(int i = 0; i < m; i++)
{
if (in[i] != out[i]){
return false;
}
}
return isConnected(adj, mark, s[0].charAt(0) - 'a');
}

// Returns true if all vertices are strongly connected i.e. can be made as loop
public static boolean isConnected(ArrayList adj, boolean mark[], int src)
{
boolean visited[] = new boolean[26];

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

/* ith character is marked (i.e. it was first or
last character of some string) then it should
be visited in last dfs (as for looping, graph
should be strongly connected) */
if (mark[i] && !visited[i]){
return false;
}
}

// If we reach that means graph is connected
return true;
}

// Utility method for a depth first
// search among vertices
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

Time Complexity :
Space Complexity : O(1) as we create the arrays mark, in, out and visited all containing constant space of 26 elements

CIRCLE OF STRINGS

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

Ans:-

Indegree and Outdegree of each vertex should be the same.
The graph should be strongly connected.
The first condition can be checked easily by keeping two arrays, in and out for each character. For checking whether a graph is having a loop which goes through all vertices is the same as checking complete directed graph is strongly connected or not because if it has a loop which goes through all vertices then we can reach to any vertex from any other vertex that is, the graph will be strongly connected and the same argument can be given for reverse statement also.

import java.util.ArrayList;

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

Time Complexity :
Space Complexity : O(1) as we create the arrays mark, in, out and visited all containing constant space of 26 elements.

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

Ans:-

Steps :

1. Create a count array of size 26(assuming only lower case characters are present) and initialize it with zero.
2. Create a queue of char datatype.
3. Store each character in queue and increase its frequency in the hash array.
4. For every character of stream, we check front of the queue.
5. If the frequency of character at the front of queue is one, then that will be the first non-repeating character.
Else if frequency is more than 1, then we pop that element.
6. If queue became empty that means there are no non-repeating characters so we will print -1.
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);
}
}
Output :
a -1 b b
a -1 c

Time Complexity : O(n) where n is the number of characters we need to go through of the given string
Space Complexity : O(n) as we are creating a queue and also a charCount array to store counts of elements.

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

Ans:-

The idea is to put the highest frequency character first (a greedy approach). We use a priority queue (Or Binary Max Heap) and put all characters and ordered by their frequencies (highest frequency character at root). We one by one take the highest frequency character from the heap and add it to result. After we add, we decrease the frequency of the character and we temporarily move this character out of priority queue so that it is not picked next time.

Steps :
1. Build a Priority_queue or max_heap, pq that stores characters and their frequencies.
2. Create a temporary Key that will be used as the previously visited element (the previous element in the resultant string. Initialize it { char = ‘#’ , freq = ‘-1’ }
3. While pq is not empty.
a) Pop an element and add it to the result.
b) Decrease frequency of the popped element by ‘1’
c) Push the previous element back into the priority_queue if it’s frequency > ‘0’
d) Make the current element as the previous element for the next iteration.
4. If the length of the resultant string and original string is not equal, print “not possible”. Else print result.Below is the code implementation of above approach.

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

class Key {
int freq; // store frequency of character
char ch;
Key(int val, char c)
{
freq = val;
ch = c;
}
}

class KeyComparator implements Comparator {

// Overriding compare()method of 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;

// Function to rearrange character of a string so that no char repeat twice
static void rearrangeString(String str)
{
int n = str.length();

// Store frequencies of all characters in string
int[] count = new int[MAX_CHAR];

for (int i = 0; i < n; i++)
count[str.charAt(i) - 'a']++;

// Insert all characters with their frequencies into a priority_queue
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' that will store resultant value
str = "";

// works as the previous visited element
// initial previous element be. ( '#' and
// it's frequency '-1' )
Key prev = new Key(-1, '#');

// traverse queue
while (pq.size() != 0) {

// pop top element from queue and add it to string.
Key k = pq.peek();
pq.poll();
str = str + k.ch;

// If frequency of previous character is less than zero that means it is useless, we need not to push it
if (prev.freq > 0)
pq.add(prev);

// make current character as the previous 'char' decrease frequency by 'one'
(k.freq)--;
prev = k;
}

// If length of the resultant string and original string is not same then string is not valid
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

Time Complexity : O(nlogn) as we loop through n elements in the given string and the min heap insertion and deletion occurs in logn time.
Space Complexity : O(n) as the priority queue created will have a maximum of n number of elements.

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

Ans:-

In the brute force approach, we can check if every subsequence of X[1..m] to see if it is also a subsequence of Y[1...n]. As there are 2^m subsequences possible of X, the time complexity for this approach would be O(n.2^m) where m is length of first string and n is length of second string. This is not a very efficient approach.

The LCS problem satisfies both optimal substructure property (problem can be broken down into smaller sub problems) and also overlapping subproblems property (recalculation of same result is done multiple times). Therefore, this problem can be solved using dynamic programming either in the top down (memoized) or bottom up (tabulation) approach. The base case is that if m (length of first string) is 0 or n (length of second string) is 0 then we return 0. Else, we check if the characters match, if they do we perform LCS by moving one character left for both the strings. Else if there is not match, we find the max of either moving a character to the left in string 1 and keeping string 2 as same or we move a character to the left in string 2 and keeping string 1 as same. We keep doing this over till m or n = 0 and store the results in a lookup table.

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)
{
// 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<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

Time Complexity : O(m x n) where m and n are the lengths of 2 strings
Space Complexity : O(m x n) where m and n are lengths of two strings. Extra space is taken as a result of creation of hashmap used to store previously calculated values

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

Ans:-

Let's say there are n stairs, and a frog is allowed to jump to the next position by skipping one or two or three positions. So there are n positions. The idea is that standing at the ith position the frog can move by i+1, i+2, i+3 position. So a recursive function can be formed where at current index i the function is recursively called for i+1, i+2 and i+3 positions. There is another way of forming the recursive function. To reach position i, the frog has to jump either from i-1, i-2 or i-3 position where i is the starting position. The time complexity of this approach would be O(3^n) as for each state a recursive function is called and there are 3 states as discussed above.

In order to improve this, we can use dynamic programming. As said above, there are n states but the recursive function gets called for 3^n times. This means that some states are called repeatedly. So we store the value of states in two ways :

The first way is to keep the recursive structure intact and just store the value in a HashMap and whenever the function is called, return the value store without computing (Top-Down Approach).
The second way is to take an extra space of size 3 and start computing values of states from 1, 2 .. to n, i.e. compute values of i, i+1, i+2 and then use them to calculate the value of i+3 (Bottom-Up Approach).
An even more efficient method would be, instead of using array of size n+1 we can use array of size 3 because for calculating no of ways for a particular step we need only last 3 steps no of ways.

Steps :

Create an array of size 3 and initialize the values for step 0,1,2 as 1,1,2 (Base cases).
Run a loop from 3 to n(dist).
For each index compute the value as ways[i%3] = ways[(i-1)%3] + ways[(i-2)%3] + ways[(i-3)%3] and store its value at i%3 index of array ways. If we are computing value for index 3 then the computed value will go at index 0 because for larger indices(4 ,5,6…..) we don’t need the value of index 0.
Return the value of ways[n%3].
Below is the code implementation.

public class CountNumberOfHops {

static int printCountDP(int steps){
// Create the array of size 3.
int [] ways = new int[3];
int n = steps;

// Initialize the bases cases
ways[0] = 1;
ways[1] = 1;
ways[2] = 2;

// Run a loop from 3 to n
// Bottom up approach to fill the array
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

Time Complexity : O(n) as there are n steps to traverse through
Space Complexity : O(1) as the space created for 3 ways is constant

Video Link : https://drive.google.com/file/d/1xxe2XURYYz6rhg-Pd1HEI99tAJHLqlAD/view?usp=sharing

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

In this problem, we need to get the maximum number of meetings that can occur in a single room. So it is a maximization problem and thereby an optimization problem. Such optimization problems can be solved using greedy approach. The greedy choice is to always pick the next meeting whose finish time is least among the remaining meetings and the start time is more than or equal to the finish time of the previously selected meeting. We can sort the meetings according to their finishing time so that we always consider the next meeting as minimum finishing time meeting.

Steps :
1) Sort the meetings according to their finishing time
2) Select the first meeting from the sorted array and print it.
3) Do the following for the remaining meetings in the sorted array.
a) If the start time of this meeting is greater than or equal to the finish time of the previously selected meeting, then select this meeting and print it.

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

Time Complexity : O(nlogn) if array is not sorted and O(n) if array comes sorted.
Space Complexity : O(1) as we do not utilise any extra space.

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

Ans:-

In this problem we need to find the minimum sum of product.So it is a minimization problem and thereby an optimization problem. Such optimization problems can be solved using greedy approach. The idea is to multiply minimum element of one array to maximum element of another array. So first we sort both the arrays and then multiply elements (first from arr1 and last from arr2, second from arr1 and second last from arr2 and so on) from each array and add them to get the minimum sum. Since multiplication of elements can lead to overflow conditions for large inputs, we store the result as long datatype.

To sort the arrays, we use a built in Arrays.sort() method which uses a dual pivot quicksort algorithm and takes O(nlogn) time complexity. We can get a better time complexity of O(n) by using a linear sorting algorithm like Count sort but that would require O(n) space to store the count and output arrays. But for large input sizes count sort becomes inefficient due to large amount of space it utilises.

Below we follow the Arrays.sort() implementation.

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

Time Complexity : O(nlogn) since we are using a dual pivot quicksort algorithm
Space Complexity : O(1) as we are not using any extra space.

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)

Ans:-

In this problem, we need to get the largest number possible given 2 numbers N and S. So it is a maximization problem and thereby an optimization problem. Such optimization problems can be solved using greedy approach. The idea is to fill one by one all digits from leftmost to rightmost (or from most significant digit to least significant).
We compare the remaining sum with 9 if the remaining sum is more than 9, we put 9 at the current position, else we put the remaining sum. Since we fill digits from left to right, we put the highest digits on the left side, hence get the largest number.

public class LargestNumberPossible {

static void largestNum(int N, int S){
// if sum is 0
if (S == 0)
{
System.out.print(N == 1 ? 0 : -1);
return ;
}

// Sum greater than the maximum possible sum
if (S > 9*N)
{
System.out.println(-1);
return ;
}

// create result array
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

Time Complexity : O(n) as we loop through N digits
Space Complexity : O(n) as we create a result array of N elements

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

Ans:-

We can solve this problem using two pointer approach. In order to store the last positions of the occurance of characters we need a hashmap to store it. Next, we loop through the array, and check if the character is present in the hashmap.

import java.util.HashMap;

public class LongestDistinctCharacters {

private static int findLongestDistinctCharacters(String s) {

// Creating a set to store the last positions of occurrence
HashMap<Character, Integer> seen = new HashMap<>();
int maximum_length = 0;

// starting the initial point of window to index 0
int start = 0;

for(int end = 0; end < s.length(); end++){
// Checking if we have already seen the element or not
if(seen.containsKey(s.charAt(end))){
// If we have seen the number, move the start pointer to position after the last occurrence
start = Math.max(start, seen.get(s.charAt(end)) + 1);
}

// Updating the last seen value of the character
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

Time Complexity : O(n) as we loop through n characters of the string
Space Complexity : O(n) as we create a hashmap to store the last indexes of already visited characters

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

Ans:-

In the brute force approach, we generate all the sub strings of the main string and for each sub string generated we check if it contains all characters of the pattern string. We print the smallest substring containing all characters of the pattern string. This is a highly inefficient solution.

A better approach would be to use two pointer technique along with hashing. Below are the steps :

1.First check if the length of the string is less than the length of the given pattern, if yes then “no such window 2.can exist “. (edge case)
3.Next, we store the occurrence of characters of the given pattern in a hash_pat[].
4.We start matching the characters of pattern with the characters of string i.e. increment count if a character matches.
5.We check if (count == length of pattern ) this means a window is found.
6.If such a window found, we try to minimize it by removing extra characters from the beginning of the current window.
We delete one character from first and again find this deleted key at right, once found apply step 5 .
7.We update min_length and finally Print the minimum length window.
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();

// Check if string's length is less than pattern's length. If yes then no such window can exist
if (len1 < len2) {
System.out.println(-1);
return "";
}

int hash_pat[] = new int[no_of_chars];
int hash_str[] = new int[no_of_chars];

// Store occurrence of characters of pattern
for (int i = 0; i < len2; i++){
hash_pat[pat.charAt(i)]++;
}

int start = 0, start_index = -1, min_len = Integer.MAX_VALUE;

// Start traversing the string. Count of characters
int count = 0;
for (int j = 0; j < len1; j++) {

// Count occurrence of characters of string
hash_str[str.charAt(j)]++;

// If string's char matches with pattern's char then increment count
if (hash_str[str.charAt(j)] <= hash_pat[str.charAt(j)]){
count++;
}

// If all the characters are matched
if (count == len2) {

// Try to minimize the window
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++;
}
}

// update window size
int len_window = j - start + 1;
if (min_len > len_window) {
min_len = len_window;
start_index = start;
}
}
}

// If no window found
if (start_index == -1) {
System.out.println(-1);
return "";
}

// Return substring starting from start_index and length min_len
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

Time Complexity : O(n) as we have 2 for loops, one for counting occurences of pattern string and other for looping through n characters of main string and detecting window and minimizing it. Both these loops takes O(n) time each so total time would be O(n) + O(n) = O(2n) = O(n)

Space Complexity : O(1) as we create hash maps of constant size of 256 elements

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

Ans:-

If we subtract a power of 2 number by 1 then all unset bits (zeros) after the only set bit (ones) become set; and the set bit becomes unset.
For example for 4 ( 100) and 16(10000), we get the following after subtracting 1
3 –> 011
15 –> 01111

So, if a number n is a power of 2 then bitwise & of n and n-1 will be zero. We can say n is a power of 2 or not based on the value of n&(n-1). The expression n&(n-1) will not work when n is 0. To handle this case also, our expression will become (n!=0 && ((n&(n-1)) == 0));

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

/* First x in the below expression is for the case when x is 0 */
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

Time Complexity : O(1)
Space Complexity : O(1)

Project 2

Ship work like this
in your own course.

Talk to a career counsellor

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.