HSBC Interview Question DSA

Q1. Longest Palindromic Substring

Intuition:

We create a 2-D array to fill the array with appropriate steps.
We fill the matrix using the gap method where we diagonally fill the matrix diagonal.
At every step, we check if the substring generated has met the condition of palindrome or not.
At every step, we keep a counter variable to store the max length of the palindrome string achieved so far.
At last, we return the answer.

Practice: Solve

Examples:

Input: Given string :"forgeeksskeegfor", 
Output: "geeksskeeg".

C++

// C++ program to find the longest palindromic substring in a given string. 
#include <iostream> 
using namespace std; 
  
string longestPalin(string s) { 
    // Initialize variables to keep track of the  
    // longest palindrome and its length. 
    int count = -1; 
    string ans = ""; 
  
    // Get the length of the input string. 
    int n = s.length(); 
  
    // Create a boolean 2D array to store palindrome information. 
    bool dp[n][n]; 
  
    // Iterate through different substring lengths. 
    for (int g = 0; g < n; g++) { 
        for (int i = 0, j = g; j < n; i++, j++) { 
            // Check if the substring is of length 1 (base case). 
            if (g == 0) { 
                dp[i][j] = true; 
            } else if (g == 1) { 
                // Check if the substring is of length 2 (base case). 
                dp[i][j] = (s[i] == s[j]); 
            } else { 
                // Check if the current substring is a  
                // palindrome based on its ends. 
                dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]); 
            } 
  
            // Update the longest palindrome and its length if found. 
            if (dp[i][j] && count < j - i + 1) { 
                ans = s.substr(i, j - i + 1); 
                count = ans.length(); 
            } 
        } 
    } 
    return ans; 
} 
  
int main() { 
    // Input string 
    string str = "forgeeksskeegfor"; 
      
    // Print the longest palindromic substring. 
    cout << longestPalin(str) << endl; 
    return 0; 
} 

Java

// Java program to find the longest palindromic substring in a given string. 
  
class LongestPalindrome { 
    static String longestPalin(String s) { 
        // Initialize variables to keep track of the  
        // longest palindrome and its length. 
        int count = -1; 
        String ans = ""; 
  
        // Get the length of the input string. 
        int n = s.length(); 
  
        // Create a boolean 2D array to store palindrome information. 
        boolean[][] dp = new boolean[n][n]; 
  
        // Iterate through different substring lengths. 
        for (int g = 0; g < n; g++) { 
            for (int i = 0, j = g; j < n; i++, j++) { 
                // Check if the substring is of length 1 (base case). 
                if (g == 0) { 
                    dp[i][j] = true; 
                } else if (g == 1) { 
                    // Check if the substring is of length 2 (base case). 
                    dp[i][j] = (s.charAt(i) == s.charAt(j)); 
                } else { 
                    // Check if the current substring is a  
                    // palindrome based on its ends. 
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]); 
                } 
  
                // Update the longest palindrome and its length if found. 
                if (dp[i][j] && count < s.substring(i, j + 1).length()) { 
                    ans = s.substring(i, j + 1); 
                    count = ans.length(); 
                } 
            } 
        } 
        return ans; 
    } 
  
    public static void main(String[] args) { 
        // Input string 
        String str = "forgeeksskeegfor"; 
          
        // Print the longest palindromic substring. 
        System.out.println(longestPalin(str)); 
    } 
} 

Output

geeksskeeg

Q2. Quick Sort

QuickSort is a sorting algorithm based on the Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array. The key process in quickSort is a partition(). The target of partitions is to place the pivot (any element can be chosen to be a pivot) at its correct position in the sorted array and put all smaller elements to the left of the pivot, and all greater elements to the right of the pivot.

Partition is done recursively on each side of the pivot after the pivot is placed in its correct position and this finally sorts the array.

Practise: Solve

Example:

Input= arr[10,7,8,9,1,5]
Output= 1 5 7 8 9 10

C++

#include <bits/stdc++.h> 
using namespace std; 
  
int partition(int arr[],int low,int high) 
{ 
//choose the pivot 
  
int pivot=arr[high]; 
//Index of smaller element and Indicate 
//the right position of pivot found so far 
int i=(low-1); 
  
for(int j=low;j<=high;j++) 
{ 
    //If current element is smaller than the pivot 
    if(arr[j]<pivot) 
    { 
    //Increment index of smaller element 
    i++; 
    swap(arr[i],arr[j]); 
    } 
} 
swap(arr[i+1],arr[high]); 
return (i+1); 
} 
  
// The Quicksort function Implement 
              
void quickSort(int arr[],int low,int high) 
{ 
// when low is less than high 
if(low<high) 
{ 
    // pi is the partition return index of pivot 
      
    int pi=partition(arr,low,high); 
      
    //Recursion Call 
    //smaller element than pivot goes left and 
    //higher element goes right 
    quickSort(arr,low,pi-1); 
    quickSort(arr,pi+1,high); 
} 
} 
              
  
int main() { 
int arr[]={10,7,8,9,1,5}; 
int n=sizeof(arr)/sizeof(arr[0]); 
// Function call 
quickSort(arr,0,n-1); 
//Print the sorted array 
cout<<"Sorted Array\n"; 
for(int i=0;i<n;i++) 
{ 
    cout<<arr[i]<<" "; 
} 
return 0; 
} 

Java

// Java implementation of QuickSort 
import java.io.*; 
  
class GFG { 
  
    // A utility function to swap two elements 
    static void swap(int[] arr, int i, int j) 
    { 
        int temp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = temp; 
    } 
  
    // This function takes last element as pivot, 
    // places the pivot element at its correct position 
    // in sorted array, and places all smaller to left 
    // of pivot and all greater elements to right of pivot 
    static int partition(int[] arr, int low, int high) 
    { 
        // Choosing the pivot 
        int pivot = arr[high]; 
  
        // Index of smaller element and indicates 
        // the right position of pivot found so far 
        int i = (low - 1); 
  
        for (int j = low; j <= high - 1; j++) { 
  
            // If current element is smaller than the pivot 
            if (arr[j] < pivot) { 
  
                // Increment index of smaller element 
                i++; 
                swap(arr, i, j); 
            } 
        } 
        swap(arr, i + 1, high); 
        return (i + 1); 
    } 
  
    // The main function that implements QuickSort 
    // arr[] --> Array to be sorted, 
    // low --> Starting index, 
    // high --> Ending index 
    static void quickSort(int[] arr, int low, int high) 
    { 
        if (low < high) { 
  
            // pi is partitioning index, arr[p] 
            // is now at right place 
            int pi = partition(arr, low, high); 
  
            // Separately sort elements before 
            // partition and after partition 
            quickSort(arr, low, pi - 1); 
            quickSort(arr, pi + 1, high); 
        } 
    } 
    // To print sorted array 
    public static void printArr(int[] arr) 
    { 
        for (int i = 0; i < arr.length; i++) { 
            System.out.print(arr[i] + " "); 
        } 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        int[] arr = { 10, 7, 8, 9, 1, 5 }; 
        int N = arr.length; 
  
        // Function call 
        quickSort(arr, 0, N - 1); 
        System.out.println("Sorted array:"); 
        printArr(arr); 
    } 
} 

Output

Sorted Array
1 5 7 8 9 10

Q3. Detect loop or cycle in a linked list

The idea is to insert the nodes in the hashmap and whenever a node is encountered that is already present in the hashmap then return true.

Follow the steps below to solve the problem:

Traverse the list individually and keep putting the node addresses in a Hash Table.
At any point, if NULL is reached then return false
If the next of the current nodes points to any of the previously stored nodes in Hash then return true.

Practise: Solve

Example:

C++

// C++ program to detect loop in a linked list 
#include <bits/stdc++.h> 
using namespace std; 
  
/* Link list node */
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
void push(struct Node** head_ref, int new_data) 
{ 
    /* allocate node */
    struct Node* new_node = new Node; 
  
    /* put in the data */
    new_node->data = new_data; 
  
    /* link the old list of the new node */
    new_node->next = (*head_ref); 
  
    /* move the head to point to the new node */
    (*head_ref) = new_node; 
} 
  
// Returns true if there is a loop in linked list 
// else returns false. 
bool detectLoop(struct Node* h) 
{ 
    unordered_set<Node*> s; 
    while (h != NULL) { 
        // If this node is already present 
        // in hashmap it means there is a cycle 
        // (Because you will be encountering the 
        // node for the second time). 
        if (s.find(h) != s.end()) 
            return true; 
  
        // If we are seeing the node for 
        // the first time, insert it in hash 
        s.insert(h); 
  
        h = h->next; 
    } 
  
    return false; 
} 
  
/* Driver program to test above function*/
int main() 
{ 
    /* Start with the empty list */
    struct Node* head = NULL; 
  
    push(&head, 20); 
    push(&head, 4); 
    push(&head, 15); 
    push(&head, 10); 
  
    /* Create a loop for testing */
    head->next->next->next->next = head; 
  
    if (detectLoop(head)) 
        cout << "Loop Found"; 
    else
        cout << "No Loop"; 
  
    return 0; 
}

Java

// Java program to detect loop in a linked list 
import java.util.*; 
  
public class LinkedList { 
  
    static Node head; // head of list 
  
    /* Linked list Node*/
    static class Node { 
        int data; 
        Node next; 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
  
    /* Inserts a new Node at front of the list. */
    static public void push(int new_data) 
    { 
        /* 1 & 2: Allocate the Node & 
                Put in the data*/
        Node new_node = new Node(new_data); 
  
        /* 3. Make next of new Node as head */
        new_node.next = head; 
  
        /* 4. Move the head to point to new Node */
        head = new_node; 
    } 
  
    // Returns true if there is a loop in linked 
    // list else returns false. 
    static boolean detectLoop(Node h) 
    { 
        HashSet<Node> s = new HashSet<Node>(); 
        while (h != null) { 
            // If we have already has this node 
            // in hashmap it means there is a cycle 
            // (Because you we encountering the 
            // node second time). 
            if (s.contains(h)) 
                return true; 
  
            // If we are seeing the node for 
            // the first time, insert it in hash 
            s.add(h); 
  
            h = h.next; 
        } 
  
        return false; 
    } 
  
    /* Driver program to test above function */
    public static void main(String[] args) 
    { 
        LinkedList llist = new LinkedList(); 
  
        llist.push(20); 
        llist.push(4); 
        llist.push(15); 
        llist.push(10); 
  
        /*Create loop for testing */
        llist.head.next.next.next.next = llist.head; 
  
        if (detectLoop(head)) 
            System.out.println("Loop Found"); 
        else
            System.out.println("No Loop"); 
    } 
}

Output

Loop Found

Q4. Pythagorean Triplet

A simple solution is to run three loops, three loops pick three array elements, and check if the current three elements form a Pythagorean Triplet.

Practise: Solve

Example:

Input: arr[3, 1, 4, 6, 5] 
Output: True 
There is a Pythagorean triplet (3, 4, 5).

C++

// A C++ program that returns true if there is a Pythagorean 
// Triplet in a given array. 
#include <iostream> 
  
using namespace std; 
  
// Returns true if there is Pythagorean triplet in ar[0..n-1] 
bool isTriplet(int ar[], int n) 
{ 
    for (int i = 0; i < n; i++) { 
        for (int j = i + 1; j < n; j++) { 
            for (int k = j + 1; k < n; k++) { 
                // Calculate square of array elements 
                int x = ar[i] * ar[i], y = ar[j] * ar[j], z = ar[k] * ar[k]; 
  
                if (x == y + z || y == x + z || z == x + y) 
                    return true; 
            } 
        } 
    } 
  
    // If we reach here, no triplet found 
    return false; 
} 
  
/* Driver program to test above function */
int main() 
{ 
    int ar[] = { 3, 1, 4, 6, 5 }; 
    int ar_size = sizeof(ar) / sizeof(ar[0]); 
    isTriplet(ar, ar_size) ? cout << "Yes" : cout << "No"; 
    return 0; 
} 

Java

// A Java program that returns true if there is a Pythagorean 
// Triplet in a given array. 
import java.io.*; 
  
class PythagoreanTriplet { 
  
    // Returns true if there is Pythagorean triplet in ar[0..n-1] 
    static boolean isTriplet(int ar[], int n) 
    { 
        for (int i = 0; i < n; i++) { 
            for (int j = i + 1; j < n; j++) { 
                for (int k = j + 1; k < n; k++) { 
                    // Calculate square of array elements 
                    int x = ar[i] * ar[i], y = ar[j] * ar[j], z = ar[k] * ar[k]; 
  
                    if (x == y + z || y == x + z || z == x + y) 
                        return true; 
                } 
            } 
        } 
  
        // If we reach here, no triplet found 
        return false; 
    } 
  
    // Driver program to test above function 
    public static void main(String[] args) 
    { 
        int ar[] = { 3, 1, 4, 6, 5 }; 
        int ar_size = ar.length; 
        if (isTriplet(ar, ar_size) == true) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
}

Output

Yes

Q5. Multiply two strings

We start with the last digit of the second number and multiply it by the first number. Then we multiply the second digit of the second number with the first number, and so on. We add all these multiplications. While adding, we put i-th multiplication shifted. We traverse all digits of the first and second numbers in a loop and add the result at the appropriate position.

Practise: Solve

Example:

Input : num1 = 4154  
             num2 = 51454
Output : 213739916

C++

// C++ program to multiply two numbers represented 
// as strings. 
#include<bits/stdc++.h> 
using namespace std; 
  
// Multiplies str1 and str2, and prints result. 
string multiply(string num1, string num2) 
{ 
    int len1 = num1.size(); 
    int len2 = num2.size(); 
    if (len1 == 0 || len2 == 0) 
    return "0"; 
  
    // will keep the result number in vector 
    // in reverse order 
    vector<int> result(len1 + len2, 0); 
  
    // Below two indexes are used to find positions 
    // in result.  
    int i_n1 = 0;  
    int i_n2 = 0;  
      
    // Go from right to left in num1 
    for (int i=len1-1; i>=0; i--) 
    { 
        int carry = 0; 
        int n1 = num1[i] - '0'; 
  
        // To shift position to left after every 
        // multiplication of a digit in num2 
        i_n2 = 0;  
          
        // Go from right to left in num2              
        for (int j=len2-1; j>=0; j--) 
        { 
            // Take current digit of second number 
            int n2 = num2[j] - '0'; 
  
            // Multiply with current digit of first number 
            // and add result to previously stored result 
            // at current position.  
            int sum = n1*n2 + result[i_n1 + i_n2] + carry; 
  
            // Carry for next iteration 
            carry = sum/10; 
  
            // Store result 
            result[i_n1 + i_n2] = sum % 10; 
  
            i_n2++; 
        } 
  
        // store carry in next cell 
        if (carry > 0) 
            result[i_n1 + i_n2] += carry; 
  
        // To shift position to left after every 
        // multiplication of a digit in num1. 
        i_n1++; 
    } 
  
    // ignore '0's from the right 
    int i = result.size() - 1; 
    while (i>=0 && result[i] == 0) 
    i--; 
  
    // If all were '0's - means either both or 
    // one of num1 or num2 were '0' 
    if (i == -1) 
    return "0"; 
  
    // generate the result string 
    string s = ""; 
      
    while (i >= 0) 
        s += std::to_string(result[i--]); 
  
    return s; 
} 
  
// Driver code 
int main() 
{ 
    string str1 = "4154"; 
    string str2 = "51454"; 
      
    if((str1.at(0) == '-' || str2.at(0) == '-') &&  
        (str1.at(0) != '-' || str2.at(0) != '-' )) 
        cout<<"-"; 
  
  
    if(str1.at(0) == '-') 
        str1 = str1.substr(1); 
  
    if(str2.at(0) == '-') 
        str2 = str2.substr(1); 
  
    cout << multiply(str1, str2); 
    return 0; 
} 

Java

// Java program to multiply two numbers  
// represented as Strings. 
import java.util.*; 
import java.io.*; 
class GFG 
{ 
      
// Multiplies str1 and str2, and prints result. 
static String multiply(String num1, String num2) 
{ 
    int len1 = num1.length(); 
    int len2 = num2.length(); 
    if (len1 == 0 || len2 == 0) 
        return "0"; 
  
    // will keep the result number in vector 
    // in reverse order 
    int result[] = new int[len1 + len2]; 
  
    // Below two indexes are used to  
    // find positions in result.  
    int i_n1 = 0;  
    int i_n2 = 0;  
      
    // Go from right to left in num1 
    for (int i = len1 - 1; i >= 0; i--) 
    { 
        int carry = 0; 
        int n1 = num1.charAt(i) - '0'; 
  
        // To shift position to left after every 
        // multipliccharAtion of a digit in num2 
        i_n2 = 0;  
          
        // Go from right to left in num2              
        for (int j = len2 - 1; j >= 0; j--) 
        { 
            // Take current digit of second number 
            int n2 = num2.charAt(j) - '0'; 
  
            // Multiply with current digit of first number 
            // and add result to previously stored result 
            // charAt current position.  
            int sum = n1 * n2 + result[i_n1 + i_n2] + carry; 
  
            // Carry for next itercharAtion 
            carry = sum / 10; 
  
            // Store result 
            result[i_n1 + i_n2] = sum % 10; 
  
            i_n2++; 
        } 
  
        // store carry in next cell 
        if (carry > 0) 
            result[i_n1 + i_n2] += carry; 
  
        // To shift position to left after every 
        // multipliccharAtion of a digit in num1. 
        i_n1++; 
    } 
  
    // ignore '0's from the right 
    int i = result.length - 1; 
    while (i >= 0 && result[i] == 0) 
    i--; 
  
    // If all were '0's - means either both  
    // or one of num1 or num2 were '0' 
    if (i == -1) 
    return "0"; 
  
    // genercharAte the result String 
    String s = ""; 
      
    while (i >= 0) 
        s += (result[i--]); 
  
    return s; 
} 
  
// Driver code 
public static void main(String[] args)  
{ 
    String str1 = "4154"; 
    String str2 = "51454"; 
  
    if ((str1.charAt(0) == '-' || str2.charAt(0) == '-') &&  
        (str1.charAt(0) != '-' || str2.charAt(0) != '-')) 
        System.out.print("-"); 
  
    if (str1.charAt(0) == '-') 
        str1 = str1.substring(1); 
  
    if (str2.charAt(0) == '-') 
        str2 = str2.substring(1); 
  
    System.out.println(multiply(str1, str2)); 
} 
} 

Output

213739916

Q6. Recursively remove all adjacent duplicates

Intuition:

Start from the leftmost character and remove duplicates at the left corner if there are any.
The first character must be different from its adjacent now. Recur for a string of length n-1 (string without first character).
Let the string obtained after reducing the right substring of length n-1 be rem_str. There are three possible cases
- If the first character of rem_str matches with the first character of the original string, remove the first character from rem_str.
- If the remaining string becomes empty and the last removed character is the same as the first character of the original string. Return an empty string.
- Otherwise, append the first character of the original string at the beginning of rem_str.
Return rem_str.

Practise: Solve

Examples:

Input: geeksforgeeg 
Output: gksfor

C++

// C++ program to remove all adjacent duplicates from a 
// string 
#include <bits/stdc++.h> 
using namespace std; 
  
// Recursively removes adjacent duplicates from str and 
// returns new string. last_removed is a pointer to 
// last_removed character 
char* removeUtil(char* str, char* last_removed) 
{ 
  
    // If length of string is 1 or 0 
    if (str[0] == '\0' || str[1] == '\0') 
        return str; 
  
    // Remove leftmost same characters and recur for 
    // remaining string 
    if (str[0] == str[1]) { 
        *last_removed = str[0]; 
        while (str[1] && str[0] == str[1]) 
            str++; 
        str++; 
        return removeUtil(str, last_removed); 
    } 
  
    // At this point, the first character is definitely 
    // different from its adjacent. Ignore first character 
    // and recursively remove characters from remaining 
    // string 
    char* rem_str = removeUtil(str + 1, last_removed); 
  
    // Check if the first character of the rem_string 
    // matches with the first character of the original 
    // string 
    if (rem_str[0] && rem_str[0] == str[0]) { 
        *last_removed = str[0]; 
  
        // Remove first character 
        return (rem_str + 1); 
    } 
  
    // If remaining string becomes empty and last removed 
    // character is same as first character of original 
    // string. This is needed for a string like "acbbcddc" 
    if (rem_str[0] == '\0' && *last_removed == str[0]) 
        return rem_str; 
  
    // If the two first characters of str and rem_str don't 
    // match, append first character of str before the first 
    // character of rem_str. 
    rem_str--; 
    rem_str[0] = str[0]; 
    return rem_str; 
} 
  
// Function to remove 
char* remove(char* str) 
{ 
    char last_removed = '\0'; 
    return removeUtil(str, &last_removed); 
} 
  
// Driver program to test above functions 
int main() 
{ 
    char str1[] = "geeksforgeeg"; 
    cout << remove(str1) << endl; 
  
  
    return 0; 
} 

Java

// Java program to remove all adjacent duplicates from a 
// string 
import java.io.*; 
import java.util.*; 
  
class GFG { 
  
    static char last_removed; // will store the last char 
                            // removed during recursion 
  
    // Recursively removes adjacent duplicates from str and 
    // returns new string. last_removed is a pointer to 
    // last_removed character 
    static String removeUtil(String str) 
    { 
  
        // If length of string is 1 or 0 
        if (str.length() == 0 || str.length() == 1) 
            return str; 
  
        // Remove leftmost same characters and recur for 
        // remaining string 
        if (str.charAt(0) == str.charAt(1)) { 
            last_removed = str.charAt(0); 
            while (str.length() > 1
                && str.charAt(0) == str.charAt(1)) 
                str = str.substring(1, str.length()); 
            str = str.substring(1, str.length()); 
            return removeUtil(str); 
        } 
  
        // At this point, the first character is definitely 
        // different from its adjacent. Ignore first 
        // character and recursively remove characters from 
        // remaining string 
        String rem_str 
            = removeUtil(str.substring(1, str.length())); 
  
        // Check if the first character of the rem_string 
        // matches with the first character of the original 
        // string 
        if (rem_str.length() != 0
            && rem_str.charAt(0) == str.charAt(0)) { 
            last_removed = str.charAt(0); 
  
            // Remove first character 
            return rem_str.substring(1, rem_str.length()); 
        } 
  
        // If remaining string becomes empty and last 
        // removed character is same as first character of 
        // original string. This is needed for a string like 
        // "acbbcddc" 
        if (rem_str.length() == 0
            && last_removed == str.charAt(0)) 
            return rem_str; 
  
        // If the two first characters of str and rem_str 
        // don't match, append first character of str before 
        // the first character of rem_str 
        return (str.charAt(0) + rem_str); 
    } 
  
    static String remove(String str) 
    { 
        last_removed = '\0'; 
        return removeUtil(str); 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
        String str1 = "geeksforgeeg"; 
        System.out.println(remove(str1)); 
  
    } 
} 

Output

gksfor

Q7. Count Palindromic Subsequences

The above problem can be recursively defined.

Initial Values : i= 0, j= n-1;
CountPS(i,j)
// Every single character of a string is a palindrome 
// subsequence 
if i == j
   return 1 // palindrome of length 1
// If first and last characters are same, then we 
// consider it as palindrome subsequence and check
// for the rest subsequence (i+1, j), (i, j-1)
Else if (str[i] == str[j])
   return   countPS(i+1, j) + countPS(i, j-1) + 1;
else
   // check for rest sub-sequence and  remove common
   // palindromic subsequences as they are counted
   // twice when we do countPS(i+1, j) + countPS(i,j-1)
   return countPS(i+1, j) + countPS(i, j-1) - countPS(i+1, j-1)

Practise: Solve

Examples:

Input : str = "abcd"
Output : 6

C++

#include <iostream> 
#include <string> 
  
using namespace std; 
  
// Function to return the total palindromic subsequence 
int Solve(string str, int i, int j) { 
    if (i == j) // Base case: when the indices are the same, there is one palindrome 
        return 1; 
  
    if (i > j) // Base case: when the first index is greater than the second, there are no palindromes 
        return 0; 
  
    if (str[i] == str[j]) { 
        // If the characters at indices i and j are the same, we can form palindromic subsequences 
        // by including or excluding both characters, so we add 1 and make recursive calls. 
        return 1 + Solve(str, i + 1, j) + Solve(str, i, j - 1); 
    } else { 
        // If the characters at indices i and j are different, we exclude one of them and make recursive calls. 
        return Solve(str, i + 1, j) + Solve(str, i, j - 1) - Solve(str, i + 1, j - 1); 
    } 
} 
  
// Driver program 
int main() { 
    string str = "abcb"; 
    cout << "Total palindromic subsequence are: " << Solve(str, 0, str.length() - 1) << endl; 
    return 0; 
} 

Java

// Java code to Count Palindromic Subsequence 
// in a given String 
public class GFG { 
    // Function return the total palindromic 
    // subsequence 
    static int solve(String str, int i, int j) 
    { 
        if (i == j) // base case when index is same 
            return 1; 
  
        if (i > j) 
            return 0; 
  
        if (str.charAt(i) == str.charAt(j)) { 
  
            return 1 + solve(str, i + 1, j) 
                + solve(str, i, j - 1); 
        } 
  
        else
            return solve(str, i + 1, j) 
                + solve(str, i, j - 1) 
                - solve(str, i + 1, j - 1); 
    } 
  
    // Driver program 
    public static void main(String args[]) 
    { 
        String str = "abcb"; 
        System.out.println( 
            "Total palindromic "
            + "subsequence are : "
            + solve(str, 0, str.length() - 1)); 
    } 
}

Output

Total palindromic subsequence are: 6

Q8. Total Decoding Messages

This problem is recursive and can be broken into sub-problems. We start from the end of the given digit sequence. We initialize the total count of decodings as 0. We recur for two subproblems.

If the last digit is non-zero, recur for the remaining (n-1) digits and add the result to the total count.
If the last two digits form a valid character (or smaller than 27), recur for the remaining (n-2) digits and add the result to the total count.

Practise: Solve

Examples:

Input:  digits[] = "121"
Output: 3
// The possible decodings are "ABA", "AU", "LA"

C++

// C++ implementation to count number of 
// decodings that can be formed from a  
// given digit sequence 
#include <cstring> 
#include <iostream> 
using namespace std; 
  
// recurring function to find 
// ways in how many ways a 
// string can be decoded of length 
// greater than 0 and starting with 
// digit 1 and greater. 
int countDecoding(char* digits, int n) 
{ 
    // base cases 
    if (n == 0 || n == 1) 
        return 1; 
    if (digits[0] == '0') 
        return 0; 
  
    // for base condition "01123" should return 0 
    // Initialize count 
    int count = 0;  
  
    // If the last digit is not 0, 
    // then last digit must add  
    // to the number of words 
    if (digits[n - 1] > '0') 
        count = countDecoding(digits, n - 1); 
  
    // If the last two digits form a number smaller 
    // than or equal to 26, then consider 
    // last two digits and recur 
    if (digits[n - 2] == '1'
        || (digits[n - 2] == '2'
        && digits[n - 1] < '7')) 
        count += countDecoding(digits, n - 2); 
  
    return count; 
} 
  
// Given a digit sequence of length n, 
// returns count of possible decodings by 
// replacing 1 with A, 2 with B, ... 26 with Z 
int countWays(char* digits, int n) 
{ 
    if (n == 0 || (n == 1 && digits[0] == '0')) 
        return 0; 
    return countDecoding(digits, n); 
} 
  
// Driver code 
int main() 
{ 
    char digits[] = "121"; 
    int n = strlen(digits); 
    cout << "Count is " << countWays(digits, n); 
    return 0; 
} 

Java

// A naive recursive Java implementation 
// to count number of decodings that 
// can be formed from a given digit sequence 
  
class GFG { 
  
    // recurring function to find 
    // ways in how many ways a 
    // string can be decoded of length 
    // greater than 0 and starting with 
    // digit 1 and greater. 
    static int countDecoding(char[] digits, int n) 
    { 
        // base cases 
        if (n == 0 || n == 1) 
            return 1; 
  
        // for base condition "01123" should return 0 
        if (digits[0] == '0') 
            return 0; 
  
        // Initialize count 
        int count = 0; 
  
        // If the last digit is not 0, then 
        // last digit must add to 
        // the number of words 
        if (digits[n - 1] > '0') 
            count = countDecoding(digits, n - 1); 
  
        // If the last two digits form a number 
        // smaller than or equal to 26, 
        // then consider last two digits and recur 
        if (digits[n - 2] == '1'
            || (digits[n - 2] == '2'
                && digits[n - 1] < '7')) 
            count += countDecoding(digits, n - 2); 
  
        return count; 
    } 
  
    // Given a digit sequence of length n, 
    // returns count of possible decodings by 
    // replacing 1 with A, 2 with B, ... 26 with Z 
    static int countWays(char[] digits, int n) 
    { 
        if (n == 0 || (n == 1 && digits[0] == '0')) 
            return 0; 
        return countDecoding(digits, n); 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        char digits[] = { '1', '2', '1'}; 
        int n = digits.length; 
        System.out.printf("Count is %d", 
                        countWays(digits, n)); 
    } 
} 

Output

Count is 3

Q9. Maximum Sub Array

The idea is to use Kadane’s Algorithm to find the maximum subarray sum and store the starting and ending index of the subarray having maximum sum and print the subarray from the starting index to the ending index. Below are the steps:

Initialize 3 variables endIndex to 0, currMax, and globalMax to the first value of the input array.
For each element in the array starting from index(say i) 1, update currMax to max(nums[i], nums[i] + currMax) and globalMax and endIndex to i only if currMax > globalMax.
To find the start index, iterate from endIndex in the left direction and keep decrementing the value of globalMax until it becomes 0. The point at which it becomes 0 is the start index.
Now print the subarray between [start, end].

Practise: Solve

Examples:

Input: arr = [-2, -5, 6, -2, -3, 1, 5, -6] 
Output: [6, -2, -3, 1, 5]

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to print the elements 
// of Subarray with maximum sum 
void SubarrayWithMaxSum(vector<int>& nums) 
{ 
    // Initialize currMax and globalMax 
    // with first value of nums 
    int endIndex, currMax = nums[0]; 
    int globalMax = nums[0]; 
  
    // Iterate for all the elements 
    // of the array 
    for (int i = 1; i < nums.size(); ++i) { 
  
        // Update currMax 
        currMax = max(nums[i], 
                    nums[i] + currMax); 
  
        // Check if currMax is greater 
        // than globalMax 
        if (currMax > globalMax) { 
            globalMax = currMax; 
            endIndex = i; 
        } 
    } 
  
    int startIndex = endIndex; 
  
    // Traverse in left direction to 
    // find start Index of subarray 
    while (startIndex >= 0) { 
  
        globalMax -= nums[startIndex]; 
  
        if (globalMax == 0) 
            break; 
  
        // Decrement the start index 
        startIndex--; 
    } 
  
    // Printing the elements of 
    // subarray with max sum 
    for (int i = startIndex; 
        i <= endIndex; ++i) { 
  
        cout << nums[i] << " "; 
    } 
} 
  
// Driver Code 
int main() 
{ 
    // Given array arr[] 
    vector<int> arr 
        = { -2, -5, 6, -2, 
            -3, 1, 5, -6 }; 
  
    // Function call 
    SubarrayWithMaxSum(arr); 
    return 0; 
} 

Java

// Java program for the above approach 
import java.util.*; 
class GFG{ 
  
// Function to print the elements 
// of Subarray with maximum sum 
static void SubarrayWithMaxSum(Vector<Integer> nums) 
{ 
    // Initialize currMax and globalMax 
    // with first value of nums 
    int endIndex = 0, currMax = nums.get(0); 
    int globalMax = nums.get(0); 
  
    // Iterate for all the elements 
    // of the array 
    for (int i = 1; i < nums.size(); ++i) 
    { 
  
    // Update currMax 
    currMax = Math.max(nums.get(i), 
                        nums.get(i) + currMax); 
  
    // Check if currMax is greater 
    // than globalMax 
    if (currMax > globalMax)  
    { 
        globalMax = currMax; 
        endIndex = i; 
    } 
    } 
  
    int startIndex = endIndex; 
  
    // Traverse in left direction to 
    // find start Index of subarray 
    while (startIndex >= 0)  
    { 
    globalMax -= nums.get(startIndex); 
  
    if (globalMax == 0) 
        break; 
  
    // Decrement the start index 
    startIndex--; 
    } 
  
    // Printing the elements of 
    // subarray with max sum 
    for(int i = startIndex; i <= endIndex; ++i) 
    { 
    System.out.print(nums.get(i) + " "); 
    } 
} 
  
// Driver Code 
public static void main(String[] args) 
{ 
    // Given array arr[] 
    Vector<Integer> arr = new Vector<Integer>(); 
    arr.add(-2); 
    arr.add(-5); 
    arr.add(6); 
    arr.add(-2); 
    arr.add(-3); 
    arr.add(1); 
    arr.add(5); 
    arr.add(-6); 
  
    // Function call 
    SubarrayWithMaxSum(arr); 
} 
}

Output

6 -2 -3 1 5

Q10. Word boggle

The idea is to consider every character as a starting character and find all words starting with it. All words starting from a character can be found using Depth First Traversal. We do depth-first traversal starting from every cell. We keep track of visited cells to make sure that a cell is considered only once in a word.

Practise: Solve

Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
       boggle[][]   = {{'G', 'I', 'Z'},
                       {'U', 'E', 'K'},
                       {'Q', 'S', 'E'}};
      isWord(str): returns true if str is present in dictionary
                   else false.
Output:  Following words of dictionary are present
         GEEKS
         QUIZ

C++

// C++ program for Boggle game 
#include <cstring> 
#include <iostream> 
using namespace std; 
  
#define M 3 
#define N 3 
  
// Let the given dictionary be following 
string dictionary[] = { "GEEKS", "FOR", "QUIZ", "GO" }; 
int n = sizeof(dictionary) / sizeof(dictionary[0]); 
  
// A given function to check if a given string is present in 
// dictionary. The implementation is naive for simplicity. As 
// per the question dictionary is given to us. 
bool isWord(string& str) 
{ 
    // Linearly search all words 
    for (int i = 0; i < n; i++) 
        if (str.compare(dictionary[i]) == 0) 
            return true; 
    return false; 
} 
  
// A recursive function to print all words present on boggle 
void findWordsUtil(char boggle[M][N], bool visited[M][N], int i, 
                int j, string& str) 
{ 
    // Mark current cell as visited and append current character 
    // to str 
    visited[i][j] = true; 
    str = str + boggle[i][j]; 
  
    // If str is present in dictionary, then print it 
    if (isWord(str)) 
        cout << str << endl; 
  
    // Traverse 8 adjacent cells of boggle[i][j] 
    for (int row = i - 1; row <= i + 1 && row < M; row++) 
        for (int col = j - 1; col <= j + 1 && col < N; col++) 
            if (row >= 0 && col >= 0 && !visited[row][col]) 
                findWordsUtil(boggle, visited, row, col, str); 
  
    // Erase current character from string and mark visited 
    // of current cell as false 
    str.erase(str.length() - 1); 
    visited[i][j] = false; 
} 
  
// Prints all words present in dictionary. 
void findWords(char boggle[M][N]) 
{ 
    // Mark all characters as not visited 
    bool visited[M][N] = { { false } }; 
  
    // Initialize current string 
    string str = ""; 
  
    // Consider every character and look for all words 
    // starting with this character 
    for (int i = 0; i < M; i++) 
        for (int j = 0; j < N; j++) 
            findWordsUtil(boggle, visited, i, j, str); 
} 
  
// Driver program to test above function 
int main() 
{ 
    char boggle[M][N] = { { 'G', 'I', 'Z' }, 
                        { 'U', 'E', 'K' }, 
                        { 'Q', 'S', 'E' } }; 
  
    cout << "Following words of dictionary are present\n"; 
    findWords(boggle); 
    return 0; 
} 

Java

// Java program for Boggle game 
class GFG { 
    // Let the given dictionary be following 
    static final String dictionary[] = { "GEEKS", "FOR", "QUIZ", "GUQ", "EE" }; 
    static final int n = dictionary.length; 
    static final int M = 3, N = 3; 
   
    // A given function to check if a given string is present in 
    // dictionary. The implementation is naive for simplicity. As 
    // per the question dictionary is given to us. 
    static boolean isWord(String str) 
    { 
        // Linearly search all words 
        for (int i = 0; i < n; i++) 
            if (str.equals(dictionary[i])) 
                return true; 
        return false; 
    } 
   
    // A recursive function to print all words present on boggle 
    static void findWordsUtil(char boggle[][], boolean visited[][], int i, 
                              int j, String str) 
    { 
        // Mark current cell as visited and append current character 
        // to str 
        visited[i][j] = true; 
        str = str + boggle[i][j]; 
   
        // If str is present in dictionary, then print it 
        if (isWord(str)) 
            System.out.println(str); 
   
        // Traverse 8 adjacent cells of boggle[i][j] 
        for (int row = i - 1; row <= i + 1 && row < M; row++) 
            for (int col = j - 1; col <= j + 1 && col < N; col++) 
                if (row >= 0 && col >= 0 && !visited[row][col]) 
                    findWordsUtil(boggle, visited, row, col, str); 
   
        // Erase current character from string and mark visited 
        // of current cell as false 
        str = "" + str.charAt(str.length() - 1); 
        visited[i][j] = false; 
    } 
   
    // Prints all words present in dictionary. 
    static void findWords(char boggle[][]) 
    { 
        // Mark all characters as not visited 
        boolean visited[][] = new boolean[M][N]; 
   
        // Initialize current string 
        String str = ""; 
   
        // Consider every character and look for all words 
        // starting with this character 
        for (int i = 0; i < M; i++) 
            for (int j = 0; j < N; j++) 
                findWordsUtil(boggle, visited, i, j, str); 
    } 
   
    // Driver program to test above function 
    public static void main(String args[]) 
    { 
        char boggle[][] = { { 'G', 'I', 'Z' }, 
                            { 'U', 'E', 'K' }, 
                            { 'Q', 'S', 'E' } }; 
   
        System.out.println("Following words of dictionary are present"); 
        findWords(boggle); 
    } 
}

Output

Following words of dictionary are present
GEEKS
QUIZ

Q11. Find the string in grid

The idea used here is simple, we check every cell. If a cell has the first character, then we one by one try all 8 directions from that cell for a match. Implementation is interesting though. We use two arrays x[] and y[] to find the next move in all 8 directions.

Practise: Solve

Example:

Input:  grid[][] = {"w3wiki",
                    "GEEKSQUIZGEEK",
                    "IDEQAPRACTICE"};
        word = "GEEKS"
Output: pattern found at 0, 0
        pattern found at 0, 8
        pattern found at 1, 0

C++

// C++ programs to search a word in a 2D grid 
#include <bits/stdc++.h> 
using namespace std; 
  
// For searching in all 8 direction 
int x[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; 
int y[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; 
  
// This function searches in 
// all 8-direction from point 
// (row, col) in grid[][] 
bool search2D(char *grid, int row, int col, 
            string word, int R, int C) 
{ 
    // If first character of word doesn't 
    // match with given starting point in grid. 
    if (*(grid+row*C+col) != word[0]) 
        return false; 
  
    int len = word.length(); 
  
    // Search word in all 8 directions 
    // starting from (row, col) 
    for (int dir = 0; dir < 8; dir++) { 
        // Initialize starting point 
        // for current direction 
        int k, rd = row + x[dir], cd = col + y[dir]; 
  
        // First character is already checked, 
        // match remaining characters 
        for (k = 1; k < len; k++) { 
            // If out of bound break 
            if (rd >= R || rd < 0 || cd >= C || cd < 0) 
                break; 
  
            // If not matched, break 
            if (*(grid+rd*C+cd) != word[k]) 
                break; 
  
            // Moving in particular direction 
            rd += x[dir], cd += y[dir]; 
        } 
  
        // If all character matched, then value of k must 
        // be equal to length of word 
        if (k == len) 
            return true; 
    } 
    return false; 
} 
  
// Searches given word in a given 
// matrix in all 8 directions 
void patternSearch(char *grid, string word, 
                int R, int C) 
{ 
    // Consider every point as starting 
    // point and search given word 
    for (int row = 0; row < R; row++) 
        for (int col = 0; col < C; col++) 
            if (search2D(grid, row, col, word, R, C)) 
                cout << "pattern found at "
                    << row << ", "
                    << col << endl; 
} 
  
// Driver program 
int main() 
{ 
    int R = 3, C = 13; 
    char grid[R][C] = { "w3wiki", 
                        "GEEKSQUIZGEEK", 
                        "IDEQAPRACTICE" }; 
  
    patternSearch((char *)grid, "GEEKS", R, C); 
    cout << endl; 
    patternSearch((char *)grid, "EEE", R, C); 
    return 0; 
} 

Java

// Java program to search 
// a word in a 2D grid 
import java.io.*; 
import java.util.*; 
  
class GFG { 
  
    // Rows and columns in the given grid 
    static int R, C; 
  
    // For searching in all 8 direction 
    static int[] x = { -1, -1, -1, 0, 0, 1, 1, 1 }; 
    static int[] y = { -1, 0, 1, -1, 1, -1, 0, 1 }; 
  
    // This function searches in all 
    // 8-direction from point 
    // (row, col) in grid[][] 
    static boolean search2D(char[][] grid, int row, 
                            int col, String word) 
    { 
        // If first character of word 
        // doesn't match with 
        // given starting point in grid. 
        if (grid[row][col] != word.charAt(0)) 
            return false; 
  
        int len = word.length(); 
  
        // Search word in all 8 directions 
        // starting from (row, col) 
        for (int dir = 0; dir < 8; dir++) { 
            // Initialize starting point 
            // for current direction 
            int k, rd = row + x[dir], cd = col + y[dir]; 
  
            // First character is already checked, 
            // match remaining characters 
            for (k = 1; k < len; k++) { 
                // If out of bound break 
                if (rd >= R || rd < 0 || cd >= C || cd < 0) 
                    break; 
  
                // If not matched, break 
                if (grid[rd][cd] != word.charAt(k)) 
                    break; 
  
                // Moving in particular direction 
                rd += x[dir]; 
                cd += y[dir]; 
            } 
  
            // If all character matched, 
            // then value of must 
            // be equal to length of word 
            if (k == len) 
                return true; 
        } 
        return false; 
    } 
  
    // Searches given word in a given 
    // matrix in all 8 directions 
    static void patternSearch( 
        char[][] grid, 
        String word) 
    { 
        // Consider every point as starting 
        // point and search given word 
        for (int row = 0; row < R; row++) { 
            for (int col = 0; col < C; col++) { 
                if (grid[row][col]==word.charAt(0) &&  
                    search2D(grid, row, col, word)) 
                        System.out.println( 
                            "pattern found at " + row + ", " + col); 
            } 
        } 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
        R = 3; 
        C = 13; 
        char[][] grid = { { 'G', 'E', 'E', 'K', 'S', 'F', 'O', 'R', 'G', 'E', 'E', 'K', 'S' }, 
                        { 'G', 'E', 'E', 'K', 'S', 'Q', 'U', 'I', 'Z', 'G', 'E', 'E', 'K' }, 
                        { 'I', 'D', 'E', 'Q', 'A', 'P', 'R', 'A', 'C', 'T', 'I', 'C', 'E' } }; 
        patternSearch(grid, "GEEKS"); 
        System.out.println(); 
        patternSearch(grid, "EEE"); 
    } 
} 

Output

pattern found at 0, 0
pattern found at 0, 8
pattern found at 1, 0

pattern found at 0, 2
pattern found at 0, 10
pattern found at 2, 2
pattern found at 2, 12

Q12. Sum of two elements with sum nearest to zero

For each element, find the sum of it with every other element in the array and compare sums. Finally, return the minimum sum.

Practise: Solve

Example:

Input:  arr[1, 60, -10, 70, -80, 85]
Output: The two elements whose sum is minimum are -80 and 85

C++

// C++ code to find Two elements 
// whose sum is closest to zero 
# include <bits/stdc++.h> 
# include <stdlib.h> /* for abs() */ 
# include <math.h> 
  
using namespace std; 
void minAbsSumPair(int arr[], int arr_size) 
{ 
    int inv_count = 0; 
    int l, r, min_sum, sum, min_l, min_r; 
      
    /* Array should have at least 
    two elements*/
    if(arr_size < 2) 
    { 
        cout << "Invalid Input"; 
        return; 
    } 
      
    /* Initialization of values */
    min_l = 0; 
    min_r = 1; 
    min_sum = arr[0] + arr[1]; 
      
    for(l = 0; l < arr_size - 1; l++) 
    { 
        for(r = l + 1; r < arr_size; r++) 
        { 
        sum = arr[l] + arr[r]; 
        if(abs(min_sum) > abs(sum)) 
        { 
            min_sum = sum; 
            min_l = l; 
            min_r = r; 
        } 
        } 
    } 
    cout << "The two elements whose sum is minimum are "
        << arr[min_l] << " and " << arr[min_r]; 
} 
  
// Driver Code 
int main() 
{ 
    int arr[] = {1, 60, -10, 70, -80, 85}; 
    minAbsSumPair(arr, 6); 
    return 0; 
} 

Java

// Java code to find Two elements 
// whose sum is closest to zero 
import java.util.*; 
import java.lang.*; 
class Main 
{ 
    static void minAbsSumPair(int arr[], int arr_size) 
    { 
    int inv_count = 0; 
    int l, r, min_sum, sum, min_l, min_r; 
      
    /* Array should have at least two elements*/
    if(arr_size < 2) 
    { 
        System.out.println("Invalid Input"); 
        return; 
    } 
      
    /* Initialization of values */
    min_l = 0; 
    min_r = 1; 
    min_sum = arr[0] + arr[1]; 
      
    for(l = 0; l < arr_size - 1; l++) 
    { 
        for(r = l+1; r < arr_size; r++) 
        { 
        sum = arr[l] + arr[r]; 
        if(Math.abs(min_sum) > Math.abs(sum)) 
        { 
            min_sum = sum; 
            min_l = l; 
            min_r = r; 
        } 
        } 
    } 
      
    System.out.println(" The two elements whose "+ 
                            "sum is minimum are "+ 
                        arr[min_l]+ " and "+arr[min_r]); 
    } 
      
    // main function 
    public static void main (String[] args)  
    { 
        int arr[] = {1, 60, -10, 70, -80, 85}; 
        minAbsSumPair(arr, 6); 
    } 
      
} 

Output

The two elements whose sum is minimum are -80 and 85

Q13. Jumping Numbers

A number is called a Jumping Number if all adjacent digits in it differ by 1. The difference between ‘9’ and ‘0’ is not considered as 1. All single-digit numbers are considered Jumping Numbers. One Simple Solution is to traverse all numbers from 0 to x. For every traversed number, check if it is a Jumping number. If yes, then print it. Otherwise, ignore it.

Practise: Solve

Example:

Input: x = 20
Output:  0 1 2 3 4 5 6 7 8 9 10 12

C++14

#include <bits/stdc++.h> 
  
using namespace std; 
  
void print_sieve(int& x) 
{ 
    int i,temp,digit; 
    bool check; 
      
    for(i=0;i<=x;i++) 
    { 
        if(i<10) 
        { 
            cout<<i<<" "; 
            continue; 
        } 
        check=1; 
        temp=i; 
        digit=temp%10; 
        temp/=10; 
        while(temp) 
        { 
            if(abs(digit-temp%10)!=1) 
            { 
                check=0; 
                break; 
            } 
            digit=temp%10; 
            temp/=10; 
        } 
        if(check) 
        cout<<i<<" "; 
    } 
} 
  
int main() 
{ 
    int x=20; 
    print_sieve(x); 
  
    return 0; 
} 

Java

// Java program to implement 
// the above approach 
import java.util.*; 
import java.lang.*; 
import java.io.*; 
  
class GFG 
{ 
public static void print_sieve(int x) 
{ 
    int i, temp, digit; 
    int check; 
  
    for(i = 0; i <= x; i++) 
    { 
    if(i < 10) 
    { 
        System.out.print(i + " "); 
        continue; 
    } 
    check = 1; 
    temp = i; 
    digit = temp % 10; 
    temp /= 10; 
    while(temp != 0) 
    { 
        if(Math.abs(digit - temp % 10) != 1) 
        { 
        check = 0; 
        break; 
        } 
        digit = temp % 10; 
        temp /= 10; 
    } 
    if(check != 0) 
        System.out.print(i + " "); 
    } 
} 
  
// Driver Code 
public static void main(String[] args) 
{ 
    int x = 20; 
    print_sieve(x); 
} 
}

Output

0 1 2 3 4 5 6 7 8 9 10 12

Q14. Median of BST

Given a Binary Search Tree, find the median of it.

If number of nodes are even: then median = ((n/2th node + ((n)/2th+1) node) /2
If the number of nodes is odd: then median = (n+1)/2th node.

Practise: Solve

Follow the steps to implement the idea:

Count the number of nodes in the given BST using Morris Inorder Traversal.
Then perform Morris Inorder traversal one more time by counting nodes and by checking if the count is equal to the median point.
To consider even no. of nodes, an extra pointer pointing to the previous node is used.

Example:

Input: 40,20,30,60,80,70,50
Output: Median of BST is 50

C++

/* C++ program to find the median of BST in O(n) 
time and O(1) space*/
#include<bits/stdc++.h> 
using namespace std; 
  
/* A binary search tree Node has data, pointer 
to left child and a pointer to right child */
struct Node 
{ 
    int data; 
    struct Node* left, *right; 
}; 
  
// A utility function to create a new BST node 
struct Node *newNode(int item) 
{ 
    struct Node *temp = new Node; 
    temp->data = item; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
  
/* A utility function to insert a new node with 
given key in BST */
struct Node* insert(struct Node* node, int key) 
{ 
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key); 
  
    /* Otherwise, recur down the tree */
    if (key < node->data) 
        node->left = insert(node->left, key); 
    else if (key > node->data) 
        node->right = insert(node->right, key); 
  
    /* return the (unchanged) node pointer */
    return node; 
} 
  
/* Function to count nodes in a binary search tree 
using Morris Inorder traversal*/
int counNodes(struct Node *root) 
{ 
    struct Node *current, *pre; 
  
    // Initialise count of nodes as 0 
    int count = 0; 
  
    if (root == NULL) 
        return count; 
  
    current = root; 
    while (current != NULL) 
    { 
        if (current->left == NULL) 
        { 
            // Count node if its left is NULL 
            count++; 
  
            // Move to its right 
            current = current->right; 
        } 
        else
        { 
            /* Find the inorder predecessor of current */
            pre = current->left; 
  
            while (pre->right != NULL && 
                pre->right != current) 
                pre = pre->right; 
  
            /* Make current as right child of its 
            inorder predecessor */
            if(pre->right == NULL) 
            { 
                pre->right = current; 
                current = current->left; 
            } 
  
            /* Revert the changes made in if part to 
            restore the original tree i.e., fix 
            the right child of predecessor */
            else
            { 
                pre->right = NULL; 
  
                // Increment count if the current 
                // node is to be visited 
                count++; 
                current = current->right; 
            } /* End of if condition pre->right == NULL */
        } /* End of if condition current->left == NULL*/
    } /* End of while */
  
    return count; 
} 
  
  
/* Function to find median in O(n) time and O(1) space 
using Morris Inorder traversal*/
int findMedian(struct Node *root) 
{ 
if (root == NULL) 
        return 0; 
  
    int count = counNodes(root); 
    int currCount = 0; 
    struct Node *current = root, *pre, *prev; 
  
    while (current != NULL) 
    { 
        if (current->left == NULL) 
        { 
            // count current node 
            currCount++; 
  
            // check if current node is the median 
            // Odd case 
            if (count % 2 != 0 && currCount == (count+1)/2) 
                return current->data; 
  
            // Even case 
            else if (count % 2 == 0 && currCount == (count/2)+1) 
                return (prev->data + current->data)/2; 
  
            // Update prev for even no. of nodes 
            prev = current; 
  
            //Move to the right 
            current = current->right; 
        } 
        else
        { 
            /* Find the inorder predecessor of current */
            pre = current->left; 
            while (pre->right != NULL && pre->right != current) 
                pre = pre->right; 
  
            /* Make current as right child of its inorder predecessor */
            if (pre->right == NULL) 
            { 
                pre->right = current; 
                current = current->left; 
            } 
  
            /* Revert the changes made in if part to restore the original 
            tree i.e., fix the right child of predecessor */
            else
            { 
                pre->right = NULL; 
  
                prev = pre; 
  
                // Count current node 
                currCount++; 
  
                // Check if the current node is the median 
                if (count % 2 != 0 && currCount == (count+1)/2 ) 
                    return current->data; 
  
                else if (count%2==0 && currCount == (count/2)+1) 
                    return (prev->data+current->data)/2; 
  
                // update prev node for the case of even 
                // no. of nodes 
                prev = current; 
                current = current->right; 
  
            } /* End of if condition pre->right == NULL */
        } /* End of if condition current->left == NULL*/
    } /* End of while */
} 
  
/* Driver program to test above functions*/
int main() 
{ 
  
    /* Let us create following BST 
                50 
            /     \ 
            30     70 
            / \ / \ 
        20 40 60 80 */
    struct Node *root = NULL; 
    root = insert(root, 50); 
    insert(root, 30); 
    insert(root, 20); 
    insert(root, 40); 
    insert(root, 70); 
    insert(root, 60); 
    insert(root, 80); 
  
    cout << "\nMedian of BST is "
        << findMedian(root); 
    return 0; 
} 

Java

/* Java program to find the median of BST in O(n)  
time and O(1) space*/
class GfG {  
  
/* A binary search tree Node has data, pointer  
to left child and a pointer to right child */
static class Node  
{  
    int data;  
    Node left, right;  
} 
  
// A utility function to create a new BST node  
static Node newNode(int item)  
{  
    Node temp = new Node();  
    temp.data = item;  
    temp.left = null; 
    temp.right = null;  
    return temp;  
}  
  
/* A utility function to insert a new node with  
given key in BST */
static Node insert(Node node, int key)  
{  
    /* If the tree is empty, return a new node */
    if (node == null) return newNode(key);  
  
    /* Otherwise, recur down the tree */
    if (key < node.data)  
        node.left = insert(node.left, key);  
    else if (key > node.data)  
        node.right = insert(node.right, key);  
  
    /* return the (unchanged) node pointer */
    return node;  
}  
  
/* Function to count nodes in a binary search tree  
using Morris Inorder traversal*/
static int counNodes(Node root)  
{  
    Node current, pre;  
  
    // Initialise count of nodes as 0  
    int count = 0;  
  
    if (root == null)  
        return count;  
  
    current = root;  
    while (current != null)  
    {  
        if (current.left == null)  
        {  
            // Count node if its left is NULL  
            count++;  
  
            // Move to its right  
            current = current.right;  
        }  
        else
        {  
            /* Find the inorder predecessor of current */
            pre = current.left;  
  
            while (pre.right != null &&  
                pre.right != current)  
                pre = pre.right;  
  
            /* Make current as right child of its  
            inorder predecessor */
            if(pre.right == null)  
            {  
                pre.right = current;  
                current = current.left;  
            }  
  
            /* Revert the changes made in if part to  
            restore the original tree i.e., fix  
            the right child of predecessor */
            else
            {  
                pre.right = null;  
  
                // Increment count if the current  
                // node is to be visited  
                count++;  
                current = current.right;  
            } /* End of if condition pre->right == NULL */
        } /* End of if condition current->left == NULL*/
    } /* End of while */
  
    return count;  
}  
  
  
/* Function to find median in O(n) time and O(1) space  
using Morris Inorder traversal*/
static int findMedian(Node root)  
{  
if (root == null)  
        return 0;  
  
    int count = counNodes(root);  
    int currCount = 0;  
    Node current = root, pre = null, prev = null;  
  
    while (current != null)  
    {  
        if (current.left == null)  
        {  
            // count current node  
            currCount++;  
  
            // check if current node is the median  
            // Odd case  
            if (count % 2 != 0 && currCount == (count+1)/2)  
                return current.data;  
  
            // Even case  
            else if (count % 2 == 0 && currCount == (count/2)+1)  
                return (prev.data + current.data)/2;  
  
            // Update prev for even no. of nodes  
            prev = current;  
  
            //Move to the right  
            current = current.right;  
        }  
        else
        {  
            /* Find the inorder predecessor of current */
            pre = current.left;  
            while (pre.right != null && pre.right != current)  
                pre = pre.right;  
  
            /* Make current as right child of its inorder predecessor */
            if (pre.right == null)  
            {  
                pre.right = current;  
                current = current.left;  
            }  
  
            /* Revert the changes made in if part to restore the original  
            tree i.e., fix the right child of predecessor */
            else
            {  
                pre.right = null;  
  
                prev = pre;  
  
                // Count current node  
                currCount++;  
  
                // Check if the current node is the median  
                if (count % 2 != 0 && currCount == (count+1)/2 )  
                    return current.data;  
  
                else if (count%2==0 && currCount == (count/2)+1)  
                    return (prev.data+current.data)/2;  
  
                // update prev node for the case of even  
                // no. of nodes  
                prev = current;  
                current = current.right;  
  
            } /* End of if condition pre->right == NULL */
        } /* End of if condition current->left == NULL*/
    } /* End of while */
    return -1; 
}  
  
/* Driver code*/
public static void main(String[] args)  
{  
  
    /* Let us create following BST  
                50  
            / \  
            30 70  
            / \ / \  
        20 40 60 80 */
    Node root = null;  
    root = insert(root, 50);  
    insert(root, 30);  
    insert(root, 20);  
    insert(root, 40);  
    insert(root, 70);  
    insert(root, 60);  
    insert(root, 80);  
  
    System.out.println("Median of BST is " + findMedian(root));  
} 
}

Output

Median of BST is 50

Q15. Closest Palindrome

The simple solution is to find the largest palindrome number which is smaller than the given number and also find the first palindrome number which is greater than the Given number. we can find the Palindromic numbers by simply decreasing and increasing by one in a given number until we find these palindromic numbers.

Practise: Solve

Examples:

Input :  N = 121 
Output : 131 or 111

C++

// C++ Program to find the closest Palindrome 
// number 
#include <bits/stdc++.h> 
using namespace std; 
  
// function check Palindrome 
bool isPalindrome(string n) 
{ 
    for (int i = 0; i < n.size() / 2; i++) 
        if (n[i] != n[n.size() - 1 - i]) 
            return false; 
    return true; 
} 
  
// convert number into String 
string convertNumIntoString(int num) 
{ 
  
    // base case: 
    if (num == 0) 
        return "0"; 
  
    string Snum = ""; 
    while (num > 0) { 
        Snum += (num % 10 - '0'); 
        num /= 10; 
    } 
    return Snum; 
} 
  
// function return closest Palindrome number 
int closestPalindrome(int num) 
{ 
  
    // case1 : largest palindrome number 
    // which is smaller to given number 
    int RPNum = num - 1; 
  
    while (!isPalindrome(convertNumIntoString(abs(RPNum)))) 
        RPNum--; 
  
    // Case 2 : smallest palindrome number 
    // which is greater than given number 
    int SPNum = num + 1; 
  
    while (!isPalindrome(convertNumIntoString(SPNum))) 
        SPNum++; 
  
    // check absolute difference 
    if (abs(num - RPNum) > abs(num - SPNum)) 
        return SPNum; 
    else
        return RPNum; 
} 
  
// Driver program to test above function 
int main() 
{ 
    int num = 121; 
    cout << closestPalindrome(num) << endl; 
    return 0; 
} 

Java

// Java program to find the closest 
// Palindrome number 
import java.io.*; 
  
class GFG { 
  
    // Function to check Palindrome 
    public static boolean isPalindrome(String s) 
    { 
        int left = 0; 
        int right = s.length() - 1; 
  
        while (left < right) { 
            if (s.charAt(left) != s.charAt(right)) { 
                return false; 
            } 
            left++; 
            right--; 
        } 
        return true; 
    } 
  
    // Function return closest Palindrome number 
    public static void closestPalindrome(int num) 
    { 
  
        // Case1 : largest palindrome number 
        // which is smaller to given number 
        int RPNum = num - 1; 
  
        while (isPalindrome(Integer.toString(RPNum)) 
            == false) { 
            RPNum--; 
        } 
  
        // Case 2 : smallest palindrome number 
        // which is greater than given number 
        int SPNum = num + 1; 
  
        while (isPalindrome(Integer.toString(SPNum)) 
            == false) { 
            SPNum++; 
        } 
  
        // Check absolute difference 
        if (Math.abs(num - SPNum) < Math.abs(num - RPNum)) { 
            System.out.println(SPNum); 
        } 
        else
            System.out.println(RPNum); 
    } 
  
    // Driver code 
    public static void main(String[] args) 
    { 
        int n = 121; 
  
        closestPalindrome(n); 
    } 
} 

Output

Q16. Maximum Path Sum between 2 Special Nodes

Intuition:

Find the maximum sum from leaf to root in the left subtree of X.
Find the maximum sum from leaf to root in the right subtree of X.
Add the above two calculated values and X->data compare the sum with the maximum value obtained so far and update the maximum value.
Return the maximum value.

Practise: Solve

C++

// C++ program to find maximum path  
//sum between two leaves of a binary tree 
#include <bits/stdc++.h> 
using namespace std; 
  
// A binary tree node 
struct Node 
{ 
    int data; 
    struct Node* left, *right; 
}; 
  
// Utility function to allocate memory for a new node 
struct Node* newNode(int data) 
{ 
    struct Node* node = new(struct Node); 
    node->data = data; 
    node->left = node->right = NULL; 
    return (node); 
} 
  
// Utility function to find maximum of two integers 
int max(int a, int b) 
{ return (a >= b)? a: b; } 
  
// A utility function to find the maximum sum between any 
// two leaves.This function calculates two values: 
// 1) Maximum path sum between two leaves which is stored 
// in res. 
// 2) The maximum root to leaf path sum which is returned. 
// If one side of root is empty, then it returns INT_MIN 
int maxPathSumUtil(struct Node *root, int &res) 
{ 
    // Base cases 
    if (root==NULL) return 0; 
    if (!root->left && !root->right) return root->data; 
  
    // Find maximum sum in left and right subtree. Also 
    // find maximum root to leaf sums in left and right 
    // subtrees and store them in ls and rs 
    int ls = maxPathSumUtil(root->left, res); 
    int rs = maxPathSumUtil(root->right, res); 
  
  
    // If both left and right children exist 
    if (root->left && root->right) 
    { 
        // Update result if needed 
        res = max(res, ls + rs + root->data); 
  
        // Return maximum possible value for root being 
        // on one side 
        return max(ls, rs) + root->data; 
    } 
  
    // If any of the two children is empty, return 
    // root sum for root being on one side 
    return (!root->left)? rs + root->data: 
                        ls + root->data; 
} 
  
// The main function which returns sum of the maximum 
// sum path between two leaves. This function mainly 
// uses maxPathSumUtil() 
int maxPathSum(struct Node *root) 
{ 
    int res = INT_MIN; 
  
    int val = maxPathSumUtil(root, res); 
          
    //--- for test case --- 
    //         7                  
    //     / \              
        // Null -3          
    //     (case - 1)          
    // value of res will be INT_MIN but the answer is 4 , which is returned by the  
    // function maxPathSumUtil(). 
  
    if(root->left && root->right) 
            return res; 
        return max(res, val); 
} 
  
// Driver Code 
int main() 
{ 
    struct Node *root = newNode(-15); 
    root->left = newNode(5); 
    root->right = newNode(6); 
    root->left->left = newNode(-8); 
    root->left->right = newNode(1); 
    root->left->left->left = newNode(2); 
    root->left->left->right = newNode(6); 
    root->right->left = newNode(3); 
    root->right->right = newNode(9); 
    root->right->right->right= newNode(0); 
    root->right->right->right->left= newNode(4); 
    root->right->right->right->right= newNode(-1); 
    root->right->right->right->right->left= newNode(10); 
    cout << "Max pathSum of the given binary tree is "
        << maxPathSum(root); 
    return 0; 
} 

Java

// Java program to find maximum path sum between two leaves 
// of a binary tree 
class Node { 
    int data; 
    Node left, right; 
  
    Node(int item) { 
        data = item; 
        left = right = null; 
    } 
} 
  
// An object of Res is passed around so that the 
// same value can be used by multiple recursive calls. 
class Res { 
    int val; 
} 
  
class BinaryTree { 
    static Node root; 
  
    // A utility function to find the maximum sum between any 
    // two leaves.This function calculates two values: 
    // 1) Maximum path sum between two leaves which is stored 
    // in res. 
    // 2) The maximum root to leaf path sum which is returned. 
    int maxPathSumUtil(Node node, Res res) { 
  
        // Base cases 
        if (node == null) 
            return 0; 
        if (node.left == null && node.right == null) 
            return node.data; 
  
        // Find maximum sum in left and right subtree. Also 
        // find maximum root to leaf sums in left and right 
        // subtrees and store them in ls and rs 
        int ls = maxPathSumUtil(node.left, res); 
        int rs = maxPathSumUtil(node.right, res); 
  
        // If both left and right children exist 
        if (node.left != null && node.right != null) { 
  
            // Update result if needed 
            res.val = Math.max(res.val, ls + rs + node.data); 
  
            // Return maximum possible value for root being 
            // on one side 
            return Math.max(ls, rs) + node.data; 
        } 
  
        // If any of the two children is empty, return 
        // root sum for root being on one side 
        return (node.left == null) ? rs + node.data : ls + node.data; 
    } 
  
    // The main function which returns sum of the maximum 
    // sum path between two leaves. This function mainly 
    // uses maxPathSumUtil() 
    int maxPathSum() { 
        Res res = new Res(); 
        res.val = Integer.MIN_VALUE; 
  
        int val = maxPathSumUtil(root, res); 
      
        if (root.left != null && root.right != null) 
            return res.val; 
        else { 
            //--- for test case --- 
            //         7                  
            //     / \              
                // Null -3                  
            // value of res will be INT_MIN but the answer is 4,  
            // which is returned by the function maxPathSumUtil() 
            return Math.max(res.val,val); 
        } 
    } 
  
    //Driver program to test above functions 
    public static void main(String args[]) { 
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(-15); 
        tree.root.left = new Node(5); 
        tree.root.right = new Node(6); 
        tree.root.left.left = new Node(-8); 
        tree.root.left.right = new Node(1); 
        tree.root.left.left.left = new Node(2); 
        tree.root.left.left.right = new Node(6); 
        tree.root.right.left = new Node(3); 
        tree.root.right.right = new Node(9); 
        tree.root.right.right.right = new Node(0); 
        tree.root.right.right.right.left = new Node(4); 
        tree.root.right.right.right.right = new Node(-1); 
        tree.root.right.right.right.right.left = new Node(10); 
      
        System.out.println("Max pathSum of the given binary tree is "
                + tree.maxPathSum()); 
    } 
}

Output

Max pathSum of the given binary tree is 27

Q18. Minimum Cost Path

This problem has the optimal substructure property. The path to reach (m, n) must be through one of the 3 cells: (m-1, n-1) (m-1, n) or (m, n-1). So minimum cost to reach (m, n) can be written as “minimum of the 3 cells plus cost[m][n]”.

minCost(m, n) = min (minCost(m-1, n-1), minCost(m-1, n), minCost(m, n-1)) + cost[m][n]

Practise: Solve

Follow the steps to solve the problem:

If N is less than zero or M is less than zero then return Integer Maximum(Base Case)
If M is equal to zero and N is equal to zero then return cost[M][N](Base Case)
Return cost[M][N] + minimum of (minCost(M-1, N-1), minCost(M-1, N), minCost(M, N-1))

C++

// A Naive recursive implementation 
// of MCP(Minimum Cost Path) problem 
#include <bits/stdc++.h> 
using namespace std; 
  
#define R 3 
#define C 3 
  
int min(int x, int y, int z); 
  
// Returns cost of minimum cost path 
// from (0,0) to (m, n) in mat[R][C] 
int minCost(int cost[R][C], int m, int n) 
{ 
    if (n < 0 || m < 0) 
        return INT_MAX; 
    else if (m == 0 && n == 0) 
        return cost[m][n]; 
    else
        return cost[m][n] 
            + min(minCost(cost, m - 1, n - 1), 
                    minCost(cost, m - 1, n), 
                    minCost(cost, m, n - 1)); 
} 
  
// A utility function that returns 
// minimum of 3 integers 
int min(int x, int y, int z) 
{ 
    if (x < y) 
        return (x < z) ? x : z; 
    else
        return (y < z) ? y : z; 
} 
  
// Driver code 
int main() 
{ 
    int cost[R][C] 
        = { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } }; 
  
    cout << minCost(cost, 2, 2) << endl; 
  
    return 0; 
}

Java

/* A Naive recursive implementation of 
MCP(Minimum Cost Path) problem */
public class GFG { 
  
    /* A utility function that returns 
    minimum of 3 integers */
    static int min(int x, int y, int z) 
    { 
        if (x < y) 
            return (x < z) ? x : z; 
        else
            return (y < z) ? y : z; 
    } 
  
    /* Returns cost of minimum cost path 
    from (0,0) to (m, n) in mat[R][C]*/
    static int minCost(int cost[][], int m, int n) 
    { 
        if (n < 0 || m < 0) 
            return Integer.MAX_VALUE; 
        else if (m == 0 && n == 0) 
            return cost[m][n]; 
        else
            return cost[m][n] 
                + min(minCost(cost, m - 1, n - 1), 
                    minCost(cost, m - 1, n), 
                    minCost(cost, m, n - 1)); 
    } 
  
    // Driver code 
    public static void main(String args[]) 
    { 
  
        int cost[][] 
            = { { 1, 2, 3 }, { 4, 8, 2 }, { 1, 5, 3 } }; 
  
        System.out.print(minCost(cost, 2, 2)); 
    } 
}

Output

Q19. Fixing Two nodes of a BST

The in-order traversal of a BST produces a sorted array. So a simple method is to store in order the traversal of the input tree in an auxiliary array. Sort the auxiliary array. Finally, insert the auxiliary array elements back into the BST, keeping the structure of the BST same.

Practise: Solve

Example:

Input: x = 20, y = 8 
         6
        / \
       10  2
      / \ / \
     1  3 7 12
Output:
      6         
     / \        
   2  10      
  / \ / \      
 1  3 7 12

C++

// C++ Program for the above approach 
#include<bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    Node* left; 
    Node* right; 
    Node(int data){ 
        this->data = data; 
        this->left = this->right = NULL; 
    } 
}; 
  
Node* newNode(int data){ 
    return new Node(data); 
} 
  
void storeInVector(Node* root, vector<int>&vec){ 
    if(root == NULL) return; 
    storeInVector(root->left, vec); 
    vec.push_back(root->data); 
    storeInVector(root->right, vec); 
} 
  
void correctBSTUtil(Node* root, vector<int> &vec, int &index){ 
    if(root == NULL) return; 
    correctBSTUtil(root->left, vec, index); 
    root->data = vec[index]; 
    index++; 
    correctBSTUtil(root->right, vec, index); 
} 
  
void correctBST(Node* root){ 
    // vector to store the inorder traversal of 
    // given tree 
    vector<int> vec; 
    storeInVector(root, vec); 
    sort(vec.begin(), vec.end()); 
    int index = 0; 
    correctBSTUtil(root, vec, index); 
} 
  
void printInorder(Node* root){ 
    if(root == NULL) return; 
    printInorder(root->left); 
    cout<<root->data<<" "; 
    printInorder(root->right); 
} 
  
int main(){ 
    /* 6 
        / \ 
    10 2 
    / \ / \ 
    1 3 7 12 
      
    10 and 2 are swapped */
    struct Node *root = newNode(6); 
    root->left = newNode(10); 
    root->right = newNode(2); 
    root->left->left = newNode(1); 
    root->left->right = newNode(3); 
    root->right->right = newNode(12); 
    root->right->left = newNode(7); 
      
    // Inorder traversal of the Original Tree 
    cout <<"Inorder Traversal of the original tree \n"; 
    printInorder(root); 
  
    correctBST(root); 
      
    // inorder traversal of the fixed tree 
    cout <<"\nInorder Traversal of the fixed tree \n"; 
    printInorder(root); 
  
    return 0; 
} 

Java

import java.io.*; 
import java.util.ArrayList; 
import java.util.Collections; 
  
class Node { 
    int data; 
    Node left; 
    Node right; 
    Node(int data) 
    { 
        this.data = data; 
        this.left = this.right = null; 
    } 
} 
  
class GFG { 
    public static void storeInVector(Node root, 
                                    ArrayList<Integer> vec) 
    { 
        if (root == null) 
            return; 
        storeInVector(root.left, vec); 
        vec.add(root.data); 
        storeInVector(root.right, vec); 
    } 
    public static void
    correctBSTUtil(Node root, ArrayList<Integer> vec, 
                int[] index) 
    { 
        if (root == null) 
            return; 
        correctBSTUtil(root.left, vec, index); 
        root.data = vec.get(index[0]); 
        index[0]++; 
        correctBSTUtil(root.right, vec, index); 
    } 
  
    public static void correctBST(Node root) 
    { 
        // ArrayList to store the inorder traversal of 
        // given tree 
        ArrayList<Integer> vec = new ArrayList<Integer>(); 
        storeInVector(root, vec); 
        Collections.sort(vec); 
        int[] index = { 0 }; 
        correctBSTUtil(root, vec, index); 
    } 
  
    public static void printInorder(Node root) 
    { 
        if (root == null) 
            return; 
        printInorder(root.left); 
        System.out.print(root.data + " "); 
        printInorder(root.right); 
    } 
  
    public static void main(String[] args) 
    { 
        /* 6 
            / \ 
        10 2 
        / \ / \ 
        1 3 7 12 
  
        10 and 2 are swapped */
        Node root = new Node(6); 
        root.left = new Node(10); 
        root.right = new Node(2); 
        root.left.left = new Node(1); 
        root.left.right = new Node(3); 
        root.right.right = new Node(12); 
        root.right.left = new Node(7); 
  
        // Inorder traversal of the Original Tree 
        System.out.println( 
            "Inorder Traversal of the original tree"); 
        printInorder(root); 
  
        correctBST(root); 
  
        // inorder traversal of the fixed tree 
        System.out.println( 
            "\nInorder Traversal of the fixed tree"); 
        printInorder(root); 
    } 
} 

Output

Inorder Traversal of the original tree 
1 10 3 6 7 2 12 
Inorder Traversal of the fixed tree 
1 2 3 6 7 10 12

Q20. Word Ladder

The idea to solve the problem is to use BFS. To find the shortest path through BFS, start from the start word and push it in a queue. And once the target is found for the first time, then return that level of BFS traversal. In each step of BFS, one can get all the words that can be formed using that many steps. So whenever the target word is found for the first time that will be the length of the shortest chain of words.

Start from the given start word.
Push the word in the queue
Run a loop until the queue is empty
Traverse all adjacent words (differ by one character) to it and push the word in a queue (for BFS)
Keep doing so until we find the target word or we have traversed all words.

Practise: Solve

Example:

Input: Dictionary = {POON, PLEE, SAME, POIE, PLEA, PLIE, POIN}, start = TOON, target = PLEA
Output: 7
Explanation: TOON – POON – POIN – POIE – PLIE – PLEE – PLEA

C++

// C++ program to find length  
// of the shortest chain 
// transformation from source 
// to target 
#include <bits/stdc++.h> 
using namespace std; 
  
// Returns length of shortest chain  
// to reach 'target' from 'start' 
// using minimum number of adjacent  
// moves. D is dictionary 
int shortestChainLen( 
string start, string target,  
set<string>& D) 
{ 
  
    if(start == target) 
    return 0; 
  
    // If the target string is not 
    // present in the dictionary 
    if (D.find(target) == D.end()) 
        return 0; 
  
    // To store the current chain length 
    // and the length of the words 
    int level = 0, wordlength = start.size(); 
  
    // Push the starting word into the queue 
    queue<string> Q; 
    Q.push(start); 
  
    // While the queue is non-empty 
    while (!Q.empty()) { 
  
        // Increment the chain length 
        ++level; 
  
        // Current size of the queue 
        int sizeofQ = Q.size(); 
  
        // Since the queue is being updated while 
        // it is being traversed so only the 
        // elements which were already present 
        // in the queue before the start of this 
        // loop will be traversed for now 
        for (int i = 0; i < sizeofQ; ++i) { 
  
            // Remove the first word from the queue 
            string word = Q.front(); 
            Q.pop(); 
  
            // For every character of the word 
            for (int pos = 0; pos < wordlength; ++pos) { 
  
                // Retain the original character 
                // at the current position 
                char orig_char = word[pos]; 
  
                // Replace the current character with 
                // every possible lowercase alphabet 
                for (char c = 'a'; c <= 'z'; ++c) { 
                    word[pos] = c; 
  
                    // If the new word is equal 
                    // to the target word 
                    if (word == target) 
                        return level + 1; 
  
                    // Remove the word from the set 
                    // if it is found in it 
                    if (D.find(word) == D.end()) 
                        continue; 
                    D.erase(word); 
  
                    // And push the newly generated word 
                    // which will be a part of the chain 
                    Q.push(word); 
                } 
  
                // Restore the original character 
                // at the current position 
                word[pos] = orig_char; 
            } 
        } 
    } 
  
    return 0; 
} 
  
// Driver program 
int main() 
{ 
    // make dictionary 
    set<string> D; 
    D.insert("poon"); 
    D.insert("plee"); 
    D.insert("same"); 
    D.insert("poie"); 
    D.insert("plie"); 
    D.insert("poin"); 
    D.insert("plea"); 
    string start = "toon"; 
    string target = "plea"; 
    cout << "Length of shortest chain is: "
        << shortestChainLen(start, target, D); 
    return 0; 
} 

Java

// Java program to find length 
// of the shortest chain 
// transformation from source 
// to target 
import java.util.*; 
  
class GFG 
{ 
  
// Returns length of shortest chain  
// to reach 'target' from 'start' 
// using minimum number of adjacent moves. 
// D is dictionary 
static int shortestChainLen(String start,  
                            String target,  
                            Set<String> D) 
{ 
  
    if(start == target) 
    return 0; 
    // If the target String is not 
    // present in the dictionary 
    if (!D.contains(target)) 
        return 0; 
  
    // To store the current chain length 
    // and the length of the words 
    int level = 0, wordlength = start.length(); 
  
    // Push the starting word into the queue 
    Queue<String> Q = new LinkedList<>(); 
    Q.add(start); 
  
    // While the queue is non-empty 
    while (!Q.isEmpty()) 
    { 
  
        // Increment the chain length 
        ++level; 
  
        // Current size of the queue 
        int sizeofQ = Q.size(); 
  
        // Since the queue is being updated while 
        // it is being traversed so only the 
        // elements which were already present 
        // in the queue before the start of this 
        // loop will be traversed for now 
        for (int i = 0; i < sizeofQ; ++i)  
        { 
  
            // Remove the first word from the queue 
            char []word = Q.peek().toCharArray(); 
            Q.remove(); 
  
            // For every character of the word 
            for (int pos = 0; pos < wordlength; ++pos) 
            { 
  
                // Retain the original character 
                // at the current position 
                char orig_char = word[pos]; 
  
                // Replace the current character with 
                // every possible lowercase alphabet 
                for (char c = 'a'; c <= 'z'; ++c) 
                { 
                    word[pos] = c; 
  
                    // If the new word is equal 
                    // to the target word 
                    if (String.valueOf(word).equals(target)) 
                        return level + 1; 
  
                    // Remove the word from the set 
                    // if it is found in it 
                    if (!D.contains(String.valueOf(word))) 
                        continue; 
                    D.remove(String.valueOf(word)); 
  
                    // And push the newly generated word 
                    // which will be a part of the chain 
                    Q.add(String.valueOf(word)); 
                } 
  
                // Restore the original character 
                // at the current position 
                word[pos] = orig_char; 
            } 
        } 
    } 
  
    return 0; 
} 
  
// Driver code 
public static void main(String[] args) 
{ 
    // make dictionary 
    Set<String> D = new HashSet<String>(); 
    D.add("poon"); 
    D.add("plee"); 
    D.add("same"); 
    D.add("poie"); 
    D.add("plie"); 
    D.add("poin"); 
    D.add("plea"); 
    String start = "toon"; 
    String target = "plea"; 
    System.out.print("Length of shortest chain is: "
        + shortestChainLen(start, target, D)); 
} 
}

Output

Length of shortest chain is: 7

Practice: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++14

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

Practise: Solve

C++

Java

HSBC Interview Question

Similar Reads