HSBC Interview Question
Explore these carefully selected HSBC interview questions to prepare for a successful career move with this renowned global bank. Understand the kinds of questions they might ask in technical assessments and when solving problems. Elevate your readiness for interviews by delving into these questions. HSBC, which stands for the Hong Kong and Shanghai Banking Corporation, is a major global bank with a rich history dating back to 1865. Renowned for its international presence, HSBC provides a wide range of financial services, serving millions of customers worldwide. The bank is recognized for its commitment to innovation, diversity, and fostering a dynamic work culture. Discover the exciting career prospects and fantastic work culture at HSBC, and gear up for a fulfilling journey with this leading international financial institution.
Landing your desired position at HSBC isn’t just about technical skills – it also involves understanding how they conduct interviews. This article takes a close look at what to expect in HSBC’s interviews, providing insights into the types of questions you might come across.
Table of Content
- HSBC Interview Question DSA
- HSBC Interview Question on OOPS
- HSBC Interview Question on OS
- HSBC Interview Question Computer Networks
HSBC Interview Question DSA
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 :"forBeginnerskeegfor",
Output: "Beginnerskeeg".
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 = "forBeginnerskeegfor" ; // 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 = "forBeginnerskeegfor" ; // Print the longest palindromic substring. System.out.println(longestPalin(str)); } } |
Beginnerskeeg
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); } } |
Sorted Array 1 5 7 8 9 10
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" ); } } |
Loop Found
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" ); } } |
Yes
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)); } } |
213739916
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: Beginnerforgeeg
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[] = "Beginnerforgeeg" ; 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 = "Beginnerforgeeg" ; System.out.println(remove(str1)); } } |
gksfor
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 )); } } |
Total palindromic subsequence are: 6
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)); } } |
Count is 3
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); } } |
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[] = {"Beginner", "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
Beginner
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[] = { "Beginner" , "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[] = { "Beginner" , "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); } } |
Following words of dictionary are present Beginner QUIZ
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",
"BeginnerQUIZGEEK",
"IDEQAPRACTICE"};
word = "Beginner"
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" , "BeginnerQUIZGEEK" , "IDEQAPRACTICE" }; patternSearch(( char *)grid, "Beginner" , 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, "Beginner" ); System.out.println(); patternSearch(grid, "EEE" ); } } |
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
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 ); } } |
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); } } |
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)); } } |
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); } } |
111
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()); } } |
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 )); } } |
8
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); } } |
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)); } } |
Length of shortest chain is: 7
HSBC Interview Question on OOPS
Object-oriented programming – As the name suggests uses objects in programming. Object-oriented programming aims to implement real-world entities like inheritance, hiding, polymorphism, etc. in programming. The main aim of OOP is to bind together the data and the functions that operate on them so that no other part of the code can access this data except that function.
Q1. What are the 4 pillars of OOPS?
The four pillars of OOPS are:
- Abstraction
- Encapsulation
- Inheritance
- Polymorphism
Abstraction: is a process of hiding implementation details and exposing only the functionality to the user.
Encapsulation: is the process of wrapping code and data together into a single unit.
Inheritance: is the process of one class inheriting properties and methods from another class in Java.
Polymorphism: is the ability to perform many things in many ways.
Q2. Define virtual functions.
A virtual function (also known as virtual methods) is a member function that is declared within a base class and is re-defined (overridden) by a derived class. When you refer to a derived class object using a pointer or a reference to the base class, you can call a virtual function for that object and execute the derived class’s version of the method.
Abstraction |
Encapsulation |
---|---|
Abstraction is the process or method of gaining the information. | While encapsulation is the process or method to contain the information. |
In abstraction, problems are solved at the design or interface level. | While in encapsulation, problems are solved at the implementation level. |
Abstraction is the method of hiding the unwanted information. | Whereas encapsulation is a method to hide the data in a single entity or unit along with a method to protect information from outside. |
We can implement abstraction using abstract classes and interfaces. | Whereas encapsulation can be implemented using by access modifier i.e. private, protected and public. |
Q4. What is Polymorphism?
Polymorphism is considered one of the important features of Object-Oriented Programming. Polymorphism allows us to perform a single action in different ways. In other words, polymorphism allows you to define one interface and have multiple implementations.
Q5. What are Manipulators?
Manipulators are helping functions that can modify the input/output stream. It does not mean that we change the value of a variable, it only modifies the I/O stream using insertion (<<) and extraction (>>) operators.
Method Overloading |
Method Overriding |
---|---|
Method overloading is a compile-time polymorphism. | Method overriding is a run-time polymorphism. |
Method overloading helps to increase the readability of the program. | Method overriding is used to grant the specific implementation of the method which is already provided by its parent class or superclass. |
It occurs within the class. | It is performed in two classes with inheritance relationships. |
Method overloading may or may not require inheritance. | Method overriding always needs inheritance. |
Q7. What is Inheritance?
Inheritance is an important pillar of OOP(Object-Oriented Programming). It is the mechanism in Java by which one class is allowed to inherit the features(fields and methods) of another class. In Java, Inheritance means creating new classes based on existing ones. A class that inherits from another class can reuse the methods and fields of that class. In addition, you can add new fields and methods to your current class as well.
Compile Time Polymorphism | Run time Polymorphism |
---|---|
In compile-time Polymorphism, the call is resolved by the compiler. | In run-time Polymorphism, the call is not resolved by the compiler. |
It is also known as Static binding, Early binding and overloading as well. | It is also known as Dynamic binding, Late binding and overriding as well. |
Method overloading is the compile-time polymorphism where more than one methods share the same name with different parameters or signatures and different return types with compared. | Method overriding is the runtime polymorphism having the same method with the same parameters or signature but associated with compared, different classes. |
It is achieved by function overloading and operator overloading. | It is achieved by virtual functions and pointers. |
Q9. What is encapsulation?
Encapsulation in Java is a fundamental concept in object-oriented programming (OOP) that refers to the bundling of data and methods that operate on that data within a single unit, which is called a class in Java. Java Encapsulation is a way of hiding the implementation details of a class from outside access and only exposing a public interface that can be used to interact with the class.
Q10. What are Constructors in Java?
Constructor is a block of codes similar to the method. It is called when an instance of the class is created. At the time of calling the constructor, memory for the object is allocated in the memory. It is a special type of method that is used to initialize the object. Every time an object is created using the new() keyword, at least one constructor is called.
HSBC Interview Question on OS
An Operating System(OS) is software that manages and handles the hardware and software resources of a computer system. It provides interaction between users of computers and computer hardware. An operating system is responsible for managing and controlling all the activities and sharing of computer resources.
Q1. What is Resource Allocation Graph (RAG) in Operating System?
A resource allocation graph shows which resource is held by which process and which process is waiting for a resource of a specific kind. It is an amazing and straight – forward tool to outline how interacting processes can deadlock. Therefore, the resource allocation graph describes the condition of the system as far as processes and resources are concerned like what number of resources are allocated and what is the request of each process.
Q2. What is Process Control Block in OS ?
A Process Control Block (PCB) is a data structure that is used by an Operating System to manage and regulate how processes are carried out. In operating systems, managing the process and scheduling them properly play the most significant role in the efficient usage of memory and other system resources.
Q3. What is Demand Paging in Operating System?
Demand paging can be described as a memory management technique that is used in operating systems to improve memory usage and system performance. Demand paging is a technique used in virtual memory systems where pages enter main memory only when requested or needed by the CPU.
Q4. What is IPC?
IPC stands for Interprocess Communication. It is a medium for the communication of processes. It is a technique where an operating system allows all the independent processes to interact or communicate with each other within a single or multiple systems connected via a network. At the same time, it can handle many requests. We can also say that it is used for sharing data between multiple threads in one or more processes.
Q5. What is Fragmentation in Operating System?
The process of dividing a computer file, such as a data file or an executable program file, into fragments that are stored in different parts of a computer’s storage medium, such as its hard disc or RAM, is known as fragmentation in computing. When a file is fragmented, it is stored on the storage medium in non-contiguous blocks, which means that the blocks are not stored next to each other.
User-level thread |
Kernel-level thread |
---|---|
The operating system doesn’t recognize user-level threads. | Kernel threads are recognized by the Operating System. |
If one user-level thread performs a blocking operation then the entire process will be blocked. | If one kernel thread performs a blocking operation then another thread can continue execution. |
Multithread applications cannot take advantage of multiprocessing. | Kernels can be multithreaded. |
The thread library contains the code for thread creation, message passing, thread scheduling, data transfer, and thread destroying | The application code does not contain thread management code. It is merely an API to the kernel mode. The Windows operating system makes use of this feature. |
Q7. What is Process Synchronization?
Process Synchronization is the coordination of execution of multiple processes in a multi-process system to ensure that they access shared resources in a controlled and predictable manner. It aims to resolve the problem of race conditions and other synchronization issues in a concurrent system
Q8. What is a semaphore explain?
Semaphores are just normal variables used to coordinate the activities of multiple processes in a computer system. They are used to enforce mutual exclusion, avoid race conditions, and implement synchronization between processes.
Q9. What is a Banker’s algorithm?
The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for the predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.
Q10. What is Belady’s Anomaly?
Bélády’s anomaly is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.
HSBC Interview Question Computer Networks
A computer network is a collection of computers or devices connected to share resources. Any device which can share or receive the data is called a Node. Through which the information or data propagate is known as channels, It can be guided or unguided.
Q1. What is an IPv4 address?
IP stands for Internet Protocol and v4 stands for Version Four (IPv4). IPv4 was the primary version brought into action for production within the ARPANET in 1983. IP version four addresses are 32-bit integers which will be expressed in decimal notation.
SMTP is a push protocol and is used to send the mail whereas POP (post office protocol) or IMAP (internet message access protocol) is used to retrieve those emails at the receiver’s side. SMTP is an application layer protocol. The client who wants to send the mail opens a TCP connection to the SMTP server and then sends the mail across the connection. The SMTP server is an always-on listening mode. As soon as it listens for a TCP connection from any client, the SMTP process initiates a connection through port 25.
Q3. What is a subnet?
The working of subnets starts in such a way that firstly it divides the subnets into smaller subnets. For communicating between subnets, routers are used. Each subnet allows its linked devices to communicate with each other. Subnetting for a network should be done in such a way that it does not affect the network bits.
Q4. What is the ARP protocol?
It broadcasts a packet to all the devices of the source network. The devices of the network peel the header of the data link layer from the Protocol Data Unit (PDU) called frame and transfer the packet to the network layer (layer 3 of OSI) where the network ID of the packet is validated with the destination IP’s network ID of the packet and if it’s equal then it responds to the source with the MAC address of the destination, else the packet reaches the gateway of the network and broadcasts packet to the devices it is connected with and validates their network ID.
Q5. What is IPCONFIG?
IPCONFIG stands for Internet Protocol Configuration. This is a command-line application which displays all the current TCP/IP (Transmission Control Protocol/Internet Protocol) network configuration and refreshes the DHCP (Dynamic Host Configuration Protocol) and DNS (Domain Name Server). It also displays the IP address, subnet mask, and default gateway for all adapters. It is available for Microsoft Windows, ReactOS, and Apple macOS.
Q6. What is the firewall?
A firewall is a network security device, either hardware or software-based, which monitors all incoming and outgoing traffic and based on a defined set of security rules accepts, rejects or drops that specific traffic. Accept: allow the traffic Reject: block the traffic but reply with an “unreachable error” Drop: block the traffic with no reply A firewall establishes a barrier between secured internal networks and outside untrusted networks, such as the Internet.
Q7. What is the ICMP protocol?
Internet Control Message Protocol (ICMP) is a network layer protocol used to diagnose communication errors by performing an error control mechanism. Since IP does not have an inbuilt mechanism for sending error and control messages. It depends on Internet Control Message Protocol(ICMP) to provide error control.
Q8. What is bandwidth?
Bandwidth, or precisely network bandwidth, is the maximum rate at which data transfer occurs across any particular path of the network. Bandwidth is a measure of the amount of data that can be sent and received at any instance of time. That simply means that the higher the bandwidth of a network, the larger the amount of data the network can send to and from across its path.
Q9. What are Gateways in Computer Network?
Gateways play a very important role in connecting two different networks. It works according to its name, which means it acts like a gate, i.e. entry point for a network. If anyone wants to enter a network then if that network has any implemented gateway, they have to cross that gateway to enter any network. Gateways are also known as protocol converters because they help to convert protocol supported by traffic of the different networks into that are supported by this network. Because of that, it makes smooth communication between two different networks.
Q10. What is Domain Name System(DNS)?
A Domain Name System (DNS) is a critical component of the Internet infrastructure that plays a fundamental role in connecting users to websites, services, and resources across the World Wide Web. It is essentially the “phone book” of the internet, translating user-friendly domain names (like www.example.com) into numerical IP addresses (such as 192.0.2.1) that computers and network devices use to locate one another on the internet.