 # Java Programming Question

#### 1. Wap to print Fibonnaci series eg 1 1 2 3 5 8 …. up to a given number

``````class Fibonacci{
public static void main(String args[])
{
int n1=0,n2=1,n3,i,count=10;
System.out.print(n1+" "+n2);//printing 0 and 1
for(i=2;i<count;++i)//loop starts from 2 because 0 and 1 are already printed
{
n3=n1+n2;
System.out.print(" "+n3);
n1=n2;
n2=n3;
}
}
}
Output: 0 1 1 2 3 5 8 13 21 34``````

#### 2. Wap to check if given number is prime number or not.

``````public class Prime{
public static void main(String args[]){
int i,m=0,flag=0;
int n=3;//it is the number to be checked
m=n/2;
if(n==0||n==1){
System.out.println(n+" is not prime number");
}else{
for(i=2;i<=m;i++){
if(n%i==0){
System.out.println(n+" is not prime number");
flag=1;
break;
}
}
if(flag==0)  { System.out.println(n+" is prime number"); }
}//end of else
}
}
Output:
3 is prime number``````

#### 3. Wap to check if given string is palindrome or not.

``````public class Palindrome
{
public static void main(String args[])
{
String a, b = "";
Scanner s = new Scanner(System.in);
System.out.print("Enter the string you want to check:");
a = s.nextLine();
int n = a.length();
for(int i = n - 1; i >= 0; i--)
{
b = b + a.charAt(i);
}
if(a.equalsIgnoreCase(b))
{
System.out.println("The string is palindrome.");
}
else
{
System.out.println("The string is not palindrome.");
}
}
}
Output:
Enter the string you want to check: abba
The string is palindrome.
``````

#### 4. Wap to check if given integer is palindrome or not.

``````class Palindrome{
public static void main(String args[]){
int r,sum=0,temp;
int n=313;//It is the number variable to be checked for palindrome
temp=n;
while(n>0){
r=n%10;  //getting remainder
sum=(sum*10)+r;
n=n/10;
}
if(temp==sum)
System.out.println("Palindrome Number ");
else
System.out.println("not palindrome");
}
}
Output:
Palindrome Number``````

#### 5. Wap to check if given number is armstrong or not.

``````class Armstrong{
public static void main(String[] args)  {
int c=0,a,temp;
int n=371;//It is the number to check armstrong
temp=n;
while(n>0)
{
a=n%10;
n=n/10;
c=c+(a*a*a);
}
if(temp==c)
System.out.println("Armstrong Number");
else
System.out.println("Not Armstrong Number");
}
}
Output:
Armstrong Number``````

#### 6. Wap for Factorial.

``````class Factorial{
public static void main(String args[]){
int i,fact=1;
int number=6;//It is the number to calculate factorial
for(i=1;i<=number;i++){
fact=fact*i;
}
System.out.println("Factorial of "+number+" is: "+fact);
}
}
Output:
Factorial of 6 is: 720``````

#### 7. WAP to Reverse the String.

``````1) By StringBuilder / StringBuffer
public class StringFormatter {
public static String reverseString(String str){
StringBuilder sb=new StringBuilder(str);
sb.reverse();
return sb.toString();
}
}
public class TestStringFormatter {
public static void main(String[] args) {
System.out.println(StringFormatter.reverseString("India"));
System.out.println(StringFormatter.reverseString("Hindustan"));
}
}
Output:
aidnI
natsudniH
2) By Reverse Iteration
public class StringFormatter {
public static String reverseString(String str){
char ch[]=str.toCharArray();
String rev="";
for(int i=ch.length-1;i>=0;i--){
rev+=ch[i];
}
return rev;
}
}
public class TestStringFormatter {
public static void main(String[] args) {
System.out.println(StringFormatter.reverseString("India"));
System.out.println(StringFormatter.reverseString("Hindustan"));
}
}
Output:
aidnI
natsudniH``````

#### 8. Wap to remove duplicates from array.

``````public class RemoveDuplicate{
public static int removeDuplicate(int arr[], int n){
if (n==0 || n==1){
return n;
}
int[] temp = new int[n];
int j = 0;
for (int i=0; i<n-1; i++){
if (arr[i] != arr[i+1]){
temp[j++] = arr[i];
}
}
temp[j++] = arr[n-1];
// Changing original array
for (int i=0; i<j; i++){
arr[i] = temp[i];
}
return j;
}
public static void main (String[] args) {
int arr[] = {5,10,20,20,30,5,30,40,50,50};
int length = arr.length;
length = removeDuplicate(arr, length);
//printing array elements
for (int i=0; i<length; i++)
System.out.print(arr[i]+" ");
}
}
Output:
5 10 20 30 40 50 ``````

#### 9. Wap to calculate square root of number.

``````public class Squareroot {
private static Scanner c;
public static void main(String[] args)
{
double number, squareRoot;
c = new Scanner(System.in);
System.out.print(" Please Enter any Number : ");
number = c.nextDouble();
squareRoot = Math.sqrt(number);
System.out.println("\n The Square of a Given Number  " + number + "  =  " + squareRoot);
}
}
Output:
Please enter any number : 144
The Square of a Given Number 144 is 12.0``````

#### 10. Wap to reverse the word in a string.

``````import java.io.*;
import java.util.*;
class Reverse {
// reverses individual words of a string
static void reverseWords(String str)
{
Stack<Character> st=new Stack<Character>();
// Traverse given string
for (int i = 0; i < str.length(); ++i) {
if (str.charAt(i) != ' ')
st.push(str.charAt(i));
else {
while (st.empty() == false) {
System.out.print(st.pop());
}
System.out.print(" ");
}
}
while (st.empty() == false) {
System.out.print(st.pop());
}
}
public static void main(String[] args)
{
String str = "Hello World";
reverseWords(str);
}
}
Output:
dlroW olleH``````

#### 11. Wap to check if given two string is Anagram or not.

``````public class Anagram {
static void isAnagram(String str1, String str2) {
String s1 = str1.replaceAll("\\s", "");
String s2 = str2.replaceAll("\\s", "");
boolean status = true;
if (s1.length() != s2.length()) {
status = false;
} else {
char[] ArrayS1 = s1.toLowerCase().toCharArray();
char[] ArrayS2 = s2.toLowerCase().toCharArray();
Arrays.sort(ArrayS1);
Arrays.sort(ArrayS2);
status = Arrays.equals(ArrayS1, ArrayS2);
}
if (status) {
System.out.println(s1 + " and " + s2 + " are anagrams");
} else {
System.out.println(s1 + " and " + s2 + " are not anagrams");
}
}
public static void main(String[] args) {
isAnagram("Website", "Android");
}
}
Output:
Website and Android are anagrams``````

#### 12. Wap to determine if given year is leap year or not.

``````public class LeapYear {
public static void main(String[] args) {
//year we want to check int year = 2004;
//if year is divisible by 4, it is a leap year
if(year % 400 == 0) || ((year % 4 == 0) && (year % 100 != 0)) System.out.println("Year " + year + " is a leap year");
else
System.out.println("Year " + year + " is not a leap year");
}
}
Output :
Year 2004 is a leap year
``````

#### 13. Wap to print number 1 to 1000.

``````public class PrintNumbers
{
public static void main(String[] args)
{
for(int i=1; i<=1000; i++)
{
System.out.println(i);
}
}
}``````

#### 14. Wap to calculate sum of first 20 natural number.

``````public class SumNumbers
{
public static void main(String[] args)
{
int sum = 0;
for(int i=1; i<=20; i++)
{
sum += i;
}
System.out.println("Sum: " + sum);
}
}``````

#### 15. Wap to Decimal to Binary.

``````import java.util.Scanner;
public class DecimalToBinary
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
System.out.println("Enter Decimal Number : ");
int inputNumber = scanner.nextInt();
int copyOfInputNumber = inputNumber;
String binary = "";
int rem = 0;
while (inputNumber > 0)
{
rem = inputNumber % 2;
binary =  rem + binary;
inputNumber = inputNumber/2;
}
System.out.println("Binary of "+copyOfInputNumber+" is "+binary);
}
}
Output :
Enter Decimal Number :
30
Binary of 30 is 11110``````

#### 16. Wap to convert Decimal to Octal.

``````import java.util.Scanner;
public class DecimalToOctal
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
System.out.println("Enter Decimal Number : ");
int inputNumber = scanner.nextInt();
int copyOfInputNumber = inputNumber;
String octal = "";
int rem = 0;
while (inputNumber > 0)
{
rem = inputNumber%8;
octal =  rem + octal;
inputNumber = inputNumber/8;
}
System.out.println("Octal of "+copyOfInputNumber+" is "+octal);
}
}
Output :
Enter Decimal Number :
250
Octal of 250 is 372``````

#### 17. Wap to convert Decimal to HexaDecimal.

``````import java.util.Scanner;
{
public static void main(String[] args)
{
Scanner scanner= new Scanner(System.in);
System.out.println("Enter Decimal Number : ");
int inputNumber = scanner.nextInt();
int copyOfInputNumber = inputNumber;
String hexa = "";
int rem = 0;
while (inputNumber > 0)
{
rem = inputNumber%16;
inputNumber = inputNumber/16;
}
}
}
Output :
Enter Decimal Number :
1500

#### 18. Wap that reads a set of integers, then print the sum of even and odd integers.

``````import java.util.Scanner;
{
public static void main(String[] args)
{
Scanner console = new Scanner(System.in);
int number;
char choice;
int evenSum = 0;
int oddSum = 0;
do
{
System.out.print("Enter the number ");
number = console.nextInt();
if( number % 2 == 0)
{
evenSum += number;
}
else
{
oddSum += number;
}
System.out.print("Do you want to continue y/n? ");
choice = console.next().charAt(0);
}while(choice=='y' || choice == 'Y');
System.out.println("Sum of even numbers: " + evenSum);
System.out.println("Sum of odd numbers: " + oddSum);
}
}``````

#### 19. Wap to convert Arraylist to array.

``````public class MainClass
{
public static void main(String[] args)
{
ArrayList<String> list = new ArrayList<String>();
System.out.println(list);
Object[] array = list.toArray();
for (Object object : array)
{
System.out.println(object);
}
}
}
Output:
PHP
Python
C
Servlet
J2EE
``````

#### 20. Wap to insert an element at particular position in an arraylist.

``````public class MainClass
{
public static void main(String[] args)
{
ArrayList<String> al = new ArrayList<String>();
System.out.println(list);
//Inserting "A" at index 1
//Inserting "B" at index 3
System.out.println(al);
}
}
Output:
[First, A, Second, B, Third, Fourth]``````

#### 21. Wap to remove an element at the particular positon of an arraylist.

``````public class MainClass
{
public static void main(String[] args)
{
ArrayList<String> al = new ArrayList<String>();
System.out.println(al);
//Removing an element from position 2
al.remove(2);
System.out.println(al);
//Removing an element from position 3
al.remove(3);
System.out.println(al);
}
}
Output:
[A,B,C,D]
[A,B,D]
[A,B]``````

#### 22. Wap to retrieve a portion of an arraylist.

``````public class MainClass
{
public static void main(String[] args)
{
ArrayList<Integer> al = new ArrayList<Integer>();
System.out.println(al);
//Retrieving a SubList
List<Integer> subList = al.subList(1, 4);
System.out.println(subList);    //Output : [2, 3, 4]
//Modifying the list
al.set(2, 0);
//Changes will be reflected in subList
System.out.println(subList);    //Output : [2, 0, 4]
//Modifying the subList
subList.set(2, 0);
//Changes will be reflected in list
System.out.println(al);    //Output : [1, 2, 0, 0, 5, 6]
}
}
Output:
[1 2 3 4 5 6]
[2 3 4]
[2 0 4]
[1 2 0 0 5 6]``````

#### 23. Wap to insert more than one element at a particular position in arraylist.

``````public class MainClass
{
public static void main(String[] args)
{
ArrayList<Integer> al = new ArrayList<Integer>();
System.out.println(al);     //Output : [1, 2, 3, 4]
ArrayList<Integer> list = new ArrayList<Integer>();
System.out.println(list);    //Output : [5, 6, 7, 8]
//Inserting all elements of list at index 2 of al
System.out.println(al);    //Output : [1, 2, 5, 6, 7, 8, 3, 4]
}
}``````

#### 24. Wap to sort an array and search an element inside it.

``````import java.util.Arrays;
public class MainClass {
public static void main(String args[]) throws Exception {
int array[] = { 4, 2, -7 , 9, -25, 19, 14, -35 };
Arrays.sort(array);
printArray("Sorted array", array);
int index = Arrays.binarySearch(array, 4);
System.out.println("Found 4 @ " + index);
}
private static void printArray(String message, int array[]) {
System.out.println(message + ": [length: " + array.length + "]");
for (int i = 0; i < array.length; i++) {
if(i != 0) {
System.out.print(", ");
}
System.out.print(array[i]);
}
System.out.println();
}
}
Output :-
Sorted array: [length: 8]
-35 -25 -7 2 4 9 14 19
Found 4 @ 4``````

#### 25. Wap to sort an array and insert an element inside it.

``````import java.util.Arrays;
public class MainClass {
public static void main(String args[]) throws Exception {
int array[] = { 4, 2, -7 , 9, -25, 19, 14, -35 };
Arrays.sort(array);
printArray("Sorted array", array);
int index = Arrays.binarySearch(array, 1);
System.out.println("Didn't find 1 @ " + index);
int newIndex = -index - 1;
array = insertElement(array, 1, newIndex);
}
private static void printArray(String message, int array[]) {
System.out.println(message + ": [length: " + array.length + "]");
for (int i = 0; i < array.length; i++) {
if (i != 0){
System.out.print(", ");
}
System.out.print(array[i]);
}
System.out.println();
}
private static int[] insertElement(int original[], int element, int index) {
int length = original.length;
int destination[] = new int[length + 1];
System.arraycopy(original, 0, destination, 0, index);
destination[index] = element;
System.arraycopy(original, index, destination, index + 1, length - index);
return destination;
}
}
Output:
Sorted array: [length: 8]
-35 -25 -7 2 4 9 14 19
Didn't find 1 @ 5
-35 -25 -7 2 4 1 9 14 19
``````

#### 26. Wap to merge two array.

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String args[]) {
String a[] = { "K", "O", "D" };
String b[] = { "N", "E", "S", "T" };
List list = new ArrayList(Arrays.asList(a));
Object[] c = list.toArray();
System.out.println(Arrays.toString(c));
}
}
Output:
[K, O, D, N, E, S, T]``````

#### 27. Wap to sort an array and search an element inside it.

``````import java.util.Arrays;
public class MainClass {
public static void main(String args[]) throws Exception {
int array[] = { 4, 2, -7 , 9, -25, 19, 14, -35 };
Arrays.sort(array);
printArray("Sorted array", array);
int index = Arrays.binarySearch(array, 4);
System.out.println("Found 4 @ " + index);
}
private static void printArray(String message, int array[]) {
System.out.println(message + ": [length: " + array.length + "]");
for (int i = 0; i < array.length; i++) {
if(i != 0){
System.out.print(", ");
}
System.out.print(array[i]);
}
System.out.println();
}
}
Output:
Sorted array: [length: 10]
-35 -25 -7 2 4 9 14 19
Found 4 @ 4``````

#### 28. Wap to check if two arrays are equal or not.

``````import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
int[] arry = {2,3,5,7,9,10};
int[] arry1 = {2,3,5,7,9,10};
int[] arry2 = {1,2,3,4};
System.out.println("Is array 1 equal to array 2? " +Arrays.equals(arry, arry1));
System.out.println("Is array 1 equal to array 3? " +Arrays.equals(arry, arry2));
}
}
Output:
Is array 1 equal to array 2? true
Is array 1 equal to array 3? false``````

#### 29. Wap to iterate array-list using for-loop, while loop and advance for loop.

``````import java.util.*;
public class arrayList {
public static void main(String[] args) {
ArrayList al = new ArrayList();
System.out.println(al.size());
System.out.println("While Loop:");
Iterator itr = al.iterator();
while(itr.hasNext()) {
System.out.println(itr.next());
}
for(Object obj : al) {
System.out.println(obj);
}
System.out.println("For Loop:");
for(int i=0; i<list.size(); i++) {
System.out.println(al.get(i));
}
}
}
Output:
3
While Loop:
5
10
15
5
10
15
For Loop:
5
10
15``````

#### 30. Wap to find second largest number in an integer in array.

``````public class MainClass
{
static int secondLargest(int[] input)
{
int firstLargest, secondLargest;
//Checking elements of input array
if(input > input)
{
//If first element is greater than second element
firstLargest = input;
secondLargest = input;
}
else
{
//If second element is greater than first element
firstLargest = input;
secondLargest = input;
}
//Checking remaining elements of input array
for (int i = 2; i < input.length; i++)
{
if(input[i] > firstLargest)
{
secondLargest = firstLargest;
firstLargest = input[i];
}
else if (input[i] < firstLargest && input[i] > secondLargest)
{
secondLargest = input[i];
}
}
return secondLargest;
}
public static void main(String[] args)
{
System.out.println(secondLargest(new int[] {25, 12, 10, 33, 4, 90}));
System.out.println(secondLargest(new int[] {122, 150, 108, 298, 399}));
System.out.println(secondLargest(new int[] {1202, 1543, 1011, 2584, 5894}));
}
}
Output :
10
122
1202
``````

#### 31. Wap to find missing number in an array.

``````public class MissingNumber
{
static int sumOfNnumbers(int n)
{
int sum = (n * (n+1))/ 2;
return sum;
}
static int sumOfElements(int[] array)
{
int sum = 0;
for (int i = 0; i < array.length; i++)
{
sum = sum + array[i];
}
return sum;
}
public static void main(String[] args)
{
int n = 8;
int[] a = {1, 5, 2, 3, 7, 6, 8};
int sumOfNnumbers = sumOfNnumbers(n);
int sumOfElements = sumOfElements(a);
int missingNumber = sumOfNnumbers - sumOfElements;
System.out.println("Missing Number is = "+missingNumber);
}
}
``````

#### 32. Wap to get roman value of a decimal number.

``````import java.util.Scanner;
public class MainClass
{
public static void main(String[] args)
{
String[] romanSymbols = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "X", "CD", "D", "CM", "M"};
int[] decimals = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
Scanner scanner = new Scanner(System.in);
System.out.println("Enter The Decimal Number Between 1 and 2999");
int inputNumber = scanner.nextInt();
int copyOfInputNumber = inputNumber;
String roman = "";
if (inputNumber >= 1 && inputNumber <= 2999)
{
for (int i = 0; i < 13; i++)
{
while(inputNumber >= decimals[i])
{
inputNumber = inputNumber - decimals[i];
roman = roman + romanSymbols[i];
}
}
System.out.println("Roman Value Of "+copyOfInputNumber+" is : "+roman);
}
else
{
System.out.println("Not a valid number");
}
}
}
Output :
Enter The Decimal Number Between 1 and 2999
1269
Roman Value Of 1269 is : MCCLXIX``````

#### 33. Wap to move zero to an end of an array.

``````public class SeparateZeros
{
static void moveZerosToEnd(int inputArray[])
{
int counter = 0;
for (int i = 0; i < inputArray.length; i++)
{
if(inputArray[i] != 0)
{
inputArray[counter] = inputArray[i];
//Incrementing the counter by 1
counter++;
}
}
//Assigning zero to remaining elements
while (counter < inputArray.length)
{
inputArray[counter] = 0;
counter++;
}
System.out.println(Arrays.toString(inputArray));
}
public static void main(String[] args)
{
moveZerosToEnd(new int[] {4, 10, 20, 0, 30, 0, 8});
moveZerosToEnd(new int[] {-9, 0, 12, 24, 0, 15, 0, 22});
}
}
Output :
[4, 10, 20, 30, 8, 0, 0]
[-9, 12, 24, 15, 22, 0, 0]
``````

#### 34. Wap to bring zero to front of an array.

``````public class SeparateZeros
{
static void moveZerosToFront(int inputArray[])
{
int counter = inputArray.length-1;
for (int i = inputArray.length-1; i >= 0; i--)
{
if(inputArray[i] != 0)
{
inputArray[counter] = inputArray[i];
counter--;
}
}
while (counter >= 0)
{
inputArray[counter] = 0;
counter--;
}
System.out.println(Arrays.toString(inputArray));
}
public static void main(String[] args)
{
moveZerosToFront(new int[] {4, 10, 20, 0, 30, 0, 8});
moveZerosToFront(new int[] {-9, 0, 12, 24, 0, 15, 0, 22});
}
}
Output:
[0, 0, 4, 10, 20, 30, 8]
[0, 0, -9, 12, 24, 15, 22]``````

#### 35. Wap to count occurances of character in string.

``````class CharCountInString
{
static void characterCount(String inputString)
{
HashMap<Character, Integer> charCountMap = new HashMap<Character, Integer>();
//Converting given string to char array
char[] strArray = inputString.toCharArray();
for (char c : strArray)
{
if(charCountMap.containsKey(c))
{
charCountMap.put(c, charCountMap.get(c)+1);
}
else
{
charCountMap.put(c, 1);
}
}
System.out.println(charCountMap);
}
public static void main(String[] args)
{
characterCount("Internationalization");
}
}
Output :
{I=1, n=4, t=2, e=1, r=1, a=3, i=3, z=1, o=2}``````

#### 36. How to find all permutation of a given string

``````public class StringPermutations {
public static void main(String args[]) {
permutation("123");
}
public static void permutation(String input){
permutation("", input);
}
private static void permutation(String perm, String word) {
if (word.isEmpty()) {
System.err.println(perm + word);
} else {
for (int i = 0; i < word.length(); i++) {
permutation(perm + word.charAt(i), word.substring(0, i)
+ word.substring(i + 1, word.length()));
}
}
}
}
Output:
123
132
213
231
312
321
``````

#### 37. Wap to remove all white space from a string.

1) Using replaceAll() Method.

In the first method, we use replaceAll() method of String class to remove all white spaces (including tab also) from a string. This is the one of the easiest method to remove all white spaces from a string. This method takes two parameters. One is the string to be replaced and another one is the string to be replaced with. We pass the string “\s” to be replaced with an empty string “”.

2) Without Using replaceAll() Method.

In the second method, we remove all white spaces (including tab also) from a string without using replaceAll() method. First we convert the given string to char array and then we traverse this array to find white spaces. We append the characters which are not the white spaces to StringBuffer object.

``````class RemoveWhiteSpaces
{
public static void main(String[] args)
{
String str = " Core Java jsp servlet  jdbc struts hibernate spring ";
//1. Using replaceAll() Method
String strWithoutSpace = str.replaceAll("\\s", "");
System.out.println(strWithoutSpace);
Output : CoreJavajspservletsjdbcstrutshibernatespring
//2. Without Using replaceAll() Method
char[] strArray = str.toCharArray();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < strArray.length; i++)
{
if( (strArray[i] != ' ') && (strArray[i] != '\t') )
{
sb.append(strArray[i]);
}
}
System.out.println(sb);
}
}
//Output : CoreJavajspservletsjdbcstrutshibernatespring
``````

#### 38. Wap to convert String To Integer in Java.

There are two methods available in java to convert string to integer. One is Integer.parseInt() method and another one is Integer.valueOf() method. Both these methods are static methods of java.lang.Integer class. Both these methods throw NumberFormatException if input string is not a valid integer. The main difference between Integer.parseInt() and Integer.valueOf() method is that parseInt() method returns primitive int where as valueOf() method returns java.lang.Integer object.

``````public class Demo1
{
public static void main(String[] args)
{
String s = "2015";
int i = Integer.parseInt(s);
System.out.println(i);
}
}
//Output : 2015
Example2:
public class Demo2
{
public static void main(String[] args)
{
String s = "2015";
int i = Integer.valueOf(s);
System.out.println(i);
}
}
//Output : 2015
``````

#### 39. Wap to convert Integer to String in Java.

You are also often need to do the reverse conversion i.e converting from integer to string. Java provides couple of methods to do that also. one is Integer.toString() method and another one is String.valueOf() method. Both these methods return string representation of the given integer.

``````public class Demo1
{
public static void main(String[] args)
{
int i = 2015;
String s = Integer.toString(i);
System.out.println(s);
}
}
//Output : 2015
Example2:
public class Demo2
{
public static void main(String[] args)
{
int i = 2015;
String s = String.valueOf(i);
System.out.println(s);
}
}
//Output : 2015``````

#### 40. Wap to reverse a given string with preserving the position of spaces

``````public class MainClass1
{
static void reverseString(String inputString)
{
//Converting inputString to char array 'inputStringArray'
char[] inputStringArray = inputString.toCharArray();
//Defining a new char array 'resultArray' with same size as inputStringArray
char[] resultArray = new char[inputStringArray.length];
//First for loop :
//For every space in the 'inputStringArray',
//we insert spaces in the 'resultArray' at the corresponding positions
for (int i = 0; i < inputStringArray.length; i++)
{
if (inputStringArray[i] == ' ')
{
resultArray[i] = ' ';
}
}
//Initializing 'j' with length of resultArray
int j = resultArray.length-1;
//Second for loop :
//we copy every non-space character of inputStringArray
//from first to last at 'j' position of resultArray
for (int i = 0; i < inputStringArray.length; i++)
{
if (inputStringArray[i] != ' ')
{
//If resultArray already has space at index j then decrementing 'j'
if(resultArray[j] == ' ')
{
j--;
}
resultArray[j] = inputStringArray[i];
j--;
}
}
System.out.println(inputString+" ---> "+String.valueOf(resultArray));
}
public static void main(String[] args)
{
reverseString("I Am Not String");
reverseString("JAVA JSP ANDROID");
}
}
Output:
I Am Not String —> g ni rtS toNmAI
JAVA JSP ANDROID —> DIOR DNA PSJAVAJ
``````

#### 41. Wap to swap first and last character of words in a sentence.

Input : kodnest for freshers

Output :todnesk  rof sresherf

Approach:As mentioned in the example we have to replace first and last character of word and keep rest of the alphabets as it is.

First we will create an Char array of given String by using toCharArray() method.

Now we iterate the char array by using for loop.

In for loop, we declare a variable whose value is dependent on i.

Whenever we found an alphabet we increase the value of i and whenever we reach at space, we are going to perform swapping between first and last character of the word which is previous of space.

``````class Demo
{
static String count(String str)
{
// Create an equivalent char array
// of given string
char[] ch = str.toCharArray();
for (int i = 0; i < ch.length; i++) {
// k stores index of first character
// and i is going to store index of last
// character.
int k = i;
while (i < ch.length && ch[i] != ' ')
i++;
// Swapping
char temp = ch[k];
ch[k] = ch[i - 1];
ch[i - 1] = temp;
// We assume that there is only one space
// between two words.
}
return new String(ch);
}
public static void main(String[] args)
{
String str = "kodnest for freshers";
System.out.println(count(str));
}
}
``````

#### 42. Wap to replace character in string.

``````public class StringReplace {
public static void main(String args[]) {
String word = "World";
//replacing character in this String
String replaced = word.replace("W", "K");
System.out.println("Replacing character in String");
System.out.println("Original String before replace : " + word);
System.out.println("Replaced String : " + replaced);
//replacing substring on String in Java
String str = "PHP is good programming language";
replaced = str.replaceAll("PHP", "Java");
System.out.println("String before replace : " + str);
System.out.println("String after replace : " + replaced);
//replacing all space in String with # using regular expression
replaced = str.replaceFirst("\\s", "#");
System.out.println("Replacing first match of regex using replaceFirst()");
System.out.println("Original String before replacement : " + str);
System.out.println("Final String : " + replaced);
System.out.println("Replacing all occurrence of substring which match regex");
replaced = str.replaceAll("\\s", "#");
System.out.println("ReplaceAll Example : " + replaced);
}
}
Output:
Replacing character in String
Original String before replace : World
Replaced String : Korld
String before replace : PHP is good programming language
String after replace : Java is good programming language
Replacing first match of regex using replaceFirst()
Original String before replacement : PHP is good programming language
Final String : PHP#is good programming language
Replacing all occurrence of substring which match regex
ReplaceAll Example : PHP#is#good#programming#language
``````

#### 43. Wap to count number of words in string.

``````public class WordCount {
static int wordcount(String string)
{
int count=0;
char ch[]= new char[string.length()];
for(int i=0;i<string.length();i++)
{
ch[i]= string.charAt(i);
if( ((i>0)&&(ch[i]!=' ')&&(ch[i-1]==' ')) || ((ch!=' ')&&(i==0)) )
count++;
}
return count;
}
public static void main(String[] args) {
String string ="Java is a best programming language";
System.out.println(wordcount(string) + " words.");
}
}
Output:
6 words.``````

#### 44. Wap to swap two number without using third variable.

``````import java.util.Scanner;
class SwapTwoNumberWithoutThirdVariable
{
public static void main(String args[])
{
int x, y;
System.out.println("Enter the number for x and y ");
Scanner in = new Scanner(System.in);
x = in.nextInt();
y = in.nextInt();
System.out.println("Before Swapping\nx = "+x+"\ny = "+y);
x = x + y
y = x - y;
x = x - y;
System.out.println("After Swapping without third variable\nx = "+x+"\ny = "+y);
}
}
Output:
Enter the number for x and y
25
49
Before Swapping
x = 25
y = 49
After Swapping without a third variable
x = 49
y = 25``````

#### 45. Wap to implement Encapsulation in Java.

``````class Loan
{
private int duration; //private variables examples of encapsulation
private String loan;
private String borrower;
private String salary;
//public constructor can break encapsulation instead use factory method
private Loan(int duration, String loan, String borrower, String salary)
{
this.duration = duration;
this.loan = loan;
this.borrower = borrower;
this.salary = salary;
}
// create loan can encapsulate loan creation logic
public Loan createLoan(String loanType)
{
return loan;
}
}
``````

#### 46. Wap to achieve encapsulation.

To achieve encapsulation in Java:

• Declare the variables of a class as ‘private’.

• Provide public setter and getter methods to modify and view the variable’s values

``````public class EncapTest
{
private String name;
private String idNum;
private int age;
public int getAge()
{
return age;
}
public String getName()
{
return name;
}
public String getIdNum()
{
return idNum;
}
public void setAge( int newAge)
{
age = newAge;
}
public void setName(String newName)
{
name = newName;
}
public void setIdNum( String newId)
{
idNum = newId;
}
}
``````

#### 47. Wap to reverse a linked list.

``````class LinkList {
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
/* Function to reverse the linked list */
Node reverse(Node node) {
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
// prints content of double linked list
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args) {
System.out.println("");
}
}
Output:
65 25 14 10
10 14 25 65``````

#### 48. Wap to insert a new node at the middle of the singly linked list.

``````public class InsertNodeMiddle {
class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public int size;
public Node tail = null;
Node newNode = new Node(data);
//Checking if the list is empty
tail = newNode;
}
else {
tail.next = newNode;
//newNode this will become new end of the list
tail = newNode;
}
//This will count the number of nodes present in the list
size++;
}
//This function will add the new node at the middle of the list.
Node newNode = new Node(data);
//Checks if the list is empty
//If list is empty, both start and end would point to new node
tail = newNode;
}
else {
Node temp, current;
//Store the mid position of the list
int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);
//Node temp will point to head
current = null;
//Traverse through the list till the middle of the list is reached
for(int i = 0; i < count; i++) {
//Node current will point to temp
current = temp;
//Node temp will point to node next to it.
temp = temp.next;
}
//current will point to new node
current.next = newNode;
//new node will point to temp
newNode.next = temp;
}
size++;
}
//display() will display all the nodes present in the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
InsertNodeMiddle inm = new InsertNodeMiddle();
System.out.println("Initial list: ");
inm.display();
//Inserting node '30' in the middle
System.out.println( "Updated List: ");
inm.display();
//Inserting node '4' in the middle
System.out.println("Updated List: ");
inm.display();
}
}
Output:
Initial list:
10 20
Updated List:
10 30 20
Updated List:
10 30 40 20 ``````

#### 49. Wap to insert new node at the start of the singly linked list.

``````public class InsertNodeStart {
class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
//Represent the origin and destination of the singly linked list
public Node tail = null;
//addAtStart() will add a new node to the beginning of the list
//Create a new node
Node newNode = new Node(data);
//Checks if the list is empty
//If list is empty, both origin and destination will point to new node
tail = newNode;
}
else {
//Node temp will point to origin
//newNode will become new origin of the list
//Node temp(previous origin) will be added after new origin
}
}
//display() will display all the nodes present in the list
public void display() {
//Node current will point to origin
System.out.println("List is empty");
return;
}
System.out.println("Adding nodes at the beginning of the list: ");
while(current != null) {
//Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
InsertNodeStart ins = new InsertNodeStart();
ins.display();
ins.display();
ins.display();
ins.display();
}
}
Output:
Adding nodes at the beginning of the list:
10
Adding nodes at the beginning of the list:
20 10
Adding nodes at the beginning of the list:
30 20 10
Adding nodes at the beginning of the list:
40 30 20 10 ``````

#### 50. Wap to insert new node at the end of the singly linked list.

``````public class InsertNodeEnd {
class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
//Represent the origin and destination of the singly linked list
public Node tail = null;
//addAtEnd() will add a new node to the destination of the list
//Create a new node
Node newNode = new Node(data);
//Checks if the list is empty
//If list is empty, both origin and destionation will point to new node
tail = newNode;
}
else {
//newNode will be added after end such that end's next will point to newNode
tail.next = newNode;
//newNode will become new destination of the list
tail = newNode;
}
}
//display() will display all the nodes present in the list
public void display() {
//Node current will point to origin
System.out.println("List is empty");
return;
}
System.out.println("Adding new node at the end of the list: ");
while(current != null) {
//Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
InsertNodeEnd ine = new InsertNodeEnd();
ine.display();
ine.display();
ine.display();
ine.display();
}
}
Output:
Adding new node at the end of the list:
10
Adding new node at the end of the list:
10 20
Adding new node at the end of the list:
10 20 30
Adding new node at the end of the list:
10 20 30 40 ``````

#### 51. Wap to delete a node in the middle of the singly linked list.

``````public class deleteNodeMiddle{
class Node{
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
//Represent the origin and destination of the singly linked list
public Node tail = null;
public int size;
// New node will be added
//Create a new node
Node newNode = new Node(data);
//Checking if the list is empty
//If list is empty, both start and end will point to new node
tail = newNode;
}
else {
//newNode will be added after end such that end's next will point to newNode
tail.next = newNode;
//newNode will become new end of the list
tail = newNode;
}
size++;
}
//deleteFromMid()  this will delete a node from the middle of the list
void deleteFromMid() {
Node temp, current;
//Checking if the list is empty
System.out.println("List is empty");
return;
}
else {
//Store the mid position of the list
int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);
//Checks whether the start is equal to the end or not, if yes then the list has only one node.
if( head != tail ) {
//Initially, temp will point to start
current = null;
//Current will point to node previous to temp
//If temp is pointing to node 2 then current will point to node 1.
for(int i = 0; i < count-1; i++){
current = temp;
temp = temp.next;
}
if(current != null) {
//temp is the middle that needs to be removed.
//So, current node will point to node next to temp by skipping temp.
current.next = temp.next;
//Delete temp
temp = null;
}
//If current points to NULL then, origin and destination will point to node next to temp.
else {
//Delete temp
temp = null;
}
}
//If the list contains only one element
//then it will remove it and both start and end will point to NULL
else {
}
}
size--;
}
//display() will display all the nodes present in the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
deleteNodeMiddle dnm = new deleteNodeMiddle();
//Printing original list
System.out.println("Initial List: ");
dnm.display();
dnm.deleteFromMid();
//Printing updated list
System.out.println("Updated List: ");
dnm.display();
}
}
}
Output:
Initial List:
10 20 30 40
Updated List:
10 30 40
Updated List:
10 40
Updated List:
40
Updated List:
List is empty``````

#### 52. Wap to delete a node at the start of the singly linked list.

``````public class DeleteNodeStart {
class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
//Represent the start and end of the singly linked list
public Node tail = null;
//Create a new node
Node newNode = new Node(data);
//Checking if the list is empty
//If list is empty, both start and end will point to new node
tail = newNode;
}
else {
//newNode will be added after end such that end's next will point to newNode
tail.next = newNode;
//newNode will become new end of the list
tail = newNode;
}
}
//deleteFromStart() this will delete a node from the start of the list
public void deleteFromStart() {
//Checking if the list is empty
System.out.println("List is empty");
return;
}
else {
//Checking whether the list contains only one node
//If not, the start will point to next node in the list and end will point to the new head.
}
//If the list contains only one node
//then, it will remove it and both start and end will point to null
else {
}
}
}
//display() this will display all the nodes present in the list
public void display() {
//Node current will point to start
System.out.println("List is empty");
return;
}
while(current != null) {
//Printing each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
DeleteNodeStart dns = new DeleteNodeStart();
//Printing initial list
System.out.println("Initial List: ");
dns.display();
dns.deleteFromStart();
//Printing updated list
System.out.println("Updated List: ");
dns.display();
}
}
}
Output:
Initial List:
10 20 30 40
Updated List:
20 30 40
Updated List:
30 40
Updated List:
40
Updated List:
List is empty``````

#### 53. Wap to remove a node from the end of the singly linked list.

``````public class DeleteNodeEnd {
class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
//Represent the start and end of the singly linked list
public Node tail = null;
//Create a new node
Node newNode = new Node(data);
//Checking if the list is empty
//If list is empty, both start and end will point to new node
tail = newNode;
}
else {
//newNode will be added after end such that end's next will point to newNode
tail.next = newNode;
//newNode will become new end of the list
tail = newNode;
}
}
//deleteFromEnd() thos will delete a node from end of the list
public void deleteFromEnd() {
//Checking if the list is empty
System.out.println("List is empty");
return;
}
else {
//Checking whether the list contains only one element
//Looping through the list till the second last element such that current.next is pointing to end
while(current.next != tail) {
current = current.next;
}
//Second last element will become new end of the list
tail = current;
tail.next = null;
}
//If the list contains only one element
//Then it will remove it and both start and end will point to null
else {
}
}
}
//display() this will display all the nodes present in the list
public void display() {
//Node current will point to start
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing pointer
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
DeleteNodeEnd dne = new DeleteNodeEnd();
//Printing initial list
System.out.println("Initial List: ");
dne.display();
dne.deleteFromEnd();
//Printing updated list
System.out.println("Updated List: ");
dne.display();
}
}
}
Output:
Initial List:
10 20 30 40
Updated List:
10 20 30
Updated List:
10 20
Updated List:
10
Updated List:
List is empty``````

#### 54. Wap to create and display circular Linked List.

``````public class CreateCircularLinkedList {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public Node tail = null;
//This function will add the new node at the end of the list.
//Create new node
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
}
else {
//tail will point to new node.
tail.next = newNode;
//New node will become new tail.
tail = newNode;
}
}
//Displays all the nodes in the list
public void display() {
System.out.println("List is empty");
}
else {
do{
//Prints each node by incrementing pointer.
System.out.print(" "+ current.data);
current = current.next;
System.out.println();
}
}
public static void main(String[] args) {
//Displays all the nodes present in the list
ccll.display();
}
}
Output:
10 20 30 40
``````

#### 55. Wap to generate Circular Linked List of N node and count nodes.

``````public class CountCircularNodes {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public int count;
//Declaring head and tail pointer as null.
public Node tail = null;
//This function will add the new node at the end of the list.
//Create new node
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
}
else {
//tail will point to new node.
tail.next = newNode;
//New node will become new tail.
tail = newNode;
}
}
//This function will count the nodes of circular linked list
public void countNodes() {
do{
//Increment the count variable by 1 for each node
count++;
current = current.next;
System.out.println("Count of nodes present in circular linked list: "+count);
}
public static void main(String[] args) {
CountCircularNodes ccn = new CountCircularNodes();
//Counts the number of nodes present in the list
ccn.countNodes();
}
}
Output:
Count of nodes present in circular linked list: 6``````

#### 56. Wap to find minimum and maximum node value in Circular Linked list.

``````public class MinMaxNode {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public Node tail = null;
//This function will add the new node at the end of the list.
//Create new node
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
}
else {
//tail will point to new node.
tail.next = newNode;
//New node will become new tail.
tail = newNode;
}
}
//Finds out the minimum value node in the list
public void minNode() {
//Initializing min to initial node data
System.out.println("List is empty");
}
else {
do{
//If current node's data is smaller than min
//Then replace value of min with current node's data
if(min > current.data) {
min = current.data;
}
current= current.next;
System.out.println("Minimum value node in the list: "+ min);
}
}
//Finds out the maximum value node in the list
public void maxNode() {
//Initializing max to initial node data
System.out.println("List is empty");
}
else {
do{
//If current node's data is greater than max
//Then replace value of max with current node's data
if(max < current.data) {
max = current.data;
}
current= current.next;
System.out.println("Maximum value node in the list: "+ max);
}
}
public static void main(String[] args) {
MinMaxNode mmn = new MinMaxNode();
//Prints the minimum value node in the list
mmn.minNode();
//Prints the maximum value node in the list
mmn.maxNode();
}
}
Output:
Minimum value node in the list: 8
Maximum value node in the list: 24``````

#### 57. Wap to insert node at the beginning of the Circular Linked list.

``````public class InsertNodeStart {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
//Declaring start and end pointer as null.
public Node tail = null;
//This function will add the new node at the end of the list.
//Create new node
Node newNode = new Node(data);
//Checking if the list is empty.
//If list is empty, both start and end would point to new node.
tail = newNode;
}
else {
//Store data into temporary node
//New node will point to temp as next node
newNode.next = temp;
//New node will be the start node
}
}
//Displays all the nodes in the list
public void display() {
System.out.println("List is empty");
}
else {
System.out.println("Adding nodes at the beginning of the list: ");
do{
//Printing each node by incrementing pointer.
System.out.print(" "+ current.data);
current = current.next;
System.out.println();
}
}
public static void main(String[] args) {
InsertNodeStart ins = new InsertNodeStart();
ins.display();
ins.display();
ins.display();
ins.display();
}
}
Output:
Adding nodes at the beginning of the list:
10
Adding nodes at the beginning of the list:
20 10
Adding nodes at the beginning of the list:
30 20 10
Adding nodes at the beginning of the list:
40 30 20 10``````

#### 58. Wap to insert a node at the end of the Circular linked list.

``````public class InsertNodeEnd {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
//Declaring start and end pointer as null.
public Node tail = null;
//This function will add the new node at the end of the list.
//Create new node
Node newNode = new Node(data);
//Checking if the list is empty.
//If list is empty, both start and end would point to new node.
tail = newNode;
}
else {
//end will point to new node.
tail.next = newNode;
//New node will become new end.
tail = newNode;
//Since, it is circular linked list end will points to start.
}
}
//Displays all the nodes in the list
public void display() {
System.out.println("List is empty");
}
else {
System.out.println("Adding nodes at the end of the list: ");
do{
//Prints each node by incrementing pointer.
System.out.print(" "+ current.data);
current = current.next;
System.out.println();
}
}
public static void main(String[] args) {
InsertNodeEnd ine = new InsertNodeEnd();
ine.display();
ine.display();
ine.display();
ine.display();
}
}
Output:
Adding nodes at the end of the list:
10
Adding nodes at the end of the list:
10 20
Adding nodes at the end of the list:
10 20 30
Adding nodes at the end of the list:
10 20 30 40``````

#### 59. Wap to insert a node at middle in Circular linked list.

``````public class InsertNodeMiddle {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public int size;
//Declaring start and end pointer as null.
public Node tail = null;
//This function will add the new node to the list.
//Create new node
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both start and end would point to new node.
tail = newNode;
}
else {
//tail will point to new node.
tail.next = newNode;
//New node will become new tail.
tail = newNode;
}
//Size will count the number of element in the list
size++;
}
//This function will add the new node at the middle of the list.
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
}
else{
Node temp,current;
//Store the mid-point of the list
int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);
current= null;
for(int i = 0; i < count; i++){
//Current will point to node previous to temp.
current = temp;
//Traverse through the list till the middle of the list is reached
temp = temp.next;
}
//current will point to new node
current.next = newNode;
//new node will point to temp
newNode.next = temp;
}
size++;
}
//Displays all the nodes in the list
public void display() {
System.out.println("List is empty");
}
else {
do{
//Prints each node by incrementing pointer.
System.out.print(" "+ current.data);
current = current.next;
System.out.println();
}
}
public static void main(String[] args) {
InsertNodeMiddle inm = new InsertNodeMiddle();
System.out.println("Initial  list: ");
inm.display();
//Inserting node '50' in the middle
System.out.println( "Updated List: ");
inm.display();
//Inserting node '6' in the middle
System.out.println("Updated List: ");
inm.display();
}
}
Output:
Initial list:
10 20 30 40
Updated List:
10 20 50 30 40
Updated List:
10 20 50 60 30 40``````

#### 60. Wap to remove node at the beginning of the Circular Linked list.

``````public class DeleteNodeStart {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
//Declaring start and end pointer as null.
public Node tail = null;
Node newNode = new Node(data);
tail = newNode;
}
else {
tail.next = newNode;
tail = newNode;
}
}
//Deletes node from the start of the list
public void deleteStart() {
//Checks whether list is empty
return;
}
else {
}
else {
}
}
}
//Displays all the nodes in the list
public void display() {
System.out.println("List is empty");
}
else {
do{
//Prints each node by incrementing pointer.
System.out.print(" "+ current.data);
current = current.next;
System.out.println();
}
}
public static void main(String[] args) {
DeleteNodeStart dns = new DeleteStart();
//Printing initial  list
System.out.println("Initial List: ");
dns.display();
dns.deleteStart();
//Printing updated list
System.out.println("Updated List: ");
dns.display();
}
}
}
Output:
Initial List:
10 20 30 40
Updated List:
20 30 40
Updated List:
30 40
Updated List:
40
Updated List:
List is empty``````

#### 61. Wap to remove node at the end of the Circular Linked list.

``````public class DeleteNodeEnd {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
//Declaring start and end pointer as null.
public Node tail = null;
//This function will add the new node at the end of the list.
//Create new node
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
}
else {
//tail will point to new node.
tail.next = newNode;
//New node will become new tail.
tail = newNode;
}
}
//Deletes node from end of the list
public void deleteEnd() {
//Checks whether list is empty
return;
}
else {
//Checks whether contain only one element
//Loop will iterate till the second last element as current.next is pointing to tail
while(current.next != tail) {
current = current.next;
}
//Second last element will be new tail
tail = current;
//Tail will point to head as it is a circular linked list
}
//If the list contains only one element
//Then it will remove it and both head and tail will point to null
else {
}
}
}
//Displays all the nodes in the list
public void display() {
System.out.println("List is empty");
}
else {
do{
//Prints each node by incrementing pointer.
System.out.print(" "+ current.data);
current = current.next;
System.out.println();
}
}
public static void main(String[] args) {
DeleteNodeEnd dne = new DeleteNodeEnd();
//Printing Initial list
System.out.println("Initial List: ");
dne.display();
dne.deleteEnd();
//Printing updated list
System.out.println("Updated List: ");
dne.display();
}
}
}
Output:
Initial List:
10 20 30 40
Updated List:
10 20 30
Updated List:
10 20
Updated List:
10
Updated List:
List is empty``````

#### 62. Wap to remove a node from middle of Circular Linked List.

``````public class DeleteNodeMiddle {
public class Node{
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public int size;
//Declaring start and end pointer as null.
public Node tail = null;
//This function will add the new node at the end of the list.
//Create new node
Node newNode = new Node(data);
//Checks if the list is empty.
//If list is empty, both head and tail would point to new node.
tail = newNode;
}
else {
//tail will point to new node.
tail.next = newNode;
//New node will become new tail.
tail = newNode;
}
//Counts the number of nodes in list
size++;
}
//Deletes node from the middle of the list
public void deleteMid() {
Node current, temp;
//Checks whether list is empty
return;
}
else {
//Store the mid position of the list
int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);
//Checks whether head is equal to tail or not, if yes then list has only one node.
if( head != tail ) {
//Initially temp will point to head;
current = null;
//Current will point to node previous to temp
//If temp is pointing to node 2 then current will points to node 1.
for(int i = 0; i < count-1; i++){
current = temp;
temp = temp.next;
}
if(current != null) {
//temp is the middle that needs to be removed.
//So, current node will point to node next to temp by skipping temp.
current.next = temp.next;
//Delete temp;
temp = null;
}
//Current points to null then head and tail will point to node next to temp.
else {
//Delete temp;
temp = null;
}
}
//If the list contains only one element
//then it will remove it and both head and tail will point to null
else {
}
}
size--;
}
//Displays all the nodes in the list
public void display() {
System.out.println("List is empty");
}
else {
do{
//Prints each node by incrementing pointer.
System.out.print(" "+ current.data);
current = current.next;
System.out.println();
}
}
public static void main(String[] args) {
DeleteNodeMiddle dnm = new DeleteNodeMiddle();
//Printing Initial list
System.out.println("Initial List: ");
dnm.display();
dnm.deleteMid();
//Printing updated list
System.out.println("Updated List: ");
dnm.display();
}
}
}
Output:
Initial List:
10 20 30 40
Updated List:
10 30 40
Updated List:
10 40
Updated List:
40
Updated List:
List is empty``````

#### 63. Wap to implement Linked list as a queue (FIFO).

``````public class LinkedListExamples
{
public static void main(String[] args)
{
//adding the elements into the queue
que.offer(100);
que.offer(200);
que.offer(300);
que.offer(400);
//Printing the elements of queue
System.out.println(que);      //Output : [100, 200, 300, 400]
//Removing the elements from the queue
System.out.println(que.poll());    //Output : 100
System.out.println(que.poll());    //Output : 200
}
}``````

#### 64. Wap to replace an element at a specific position in linked list.

``````public class LinkedListReplace
{
public static void main(String[] args)
{
//Adding elements at the end of the list
//Printing the elements of list
System.out.println(list);      //Output : [First, Second, Third, Fourth]
//Replacing an element at index 2 with "ZERO"
list.set(2, "ABC");
System.out.println(list);     //Output : [First, Second, ABC, Fourth]
}
}``````

#### 65. Wap to create clone of LinkedList.

``````public class LinkedListClone
{
public static void main(String[] args)
{
System.out.println(linkedList1);       //Output : [100, 200, 300, 400, 500]
System.out.println(linkedList2);     //Output : [100, 200, 300, 400, 500]
}
}``````

#### 66. Wap to find the middle Node of a Linked List in single pass.

``````public class LinkedListMiddleNode {
public static void main(String args[]) {
//finding middle element of LinkedList in single pass
int length = 0;
while(current.next() != null){
length++;
if(length%2 ==0){
middle = middle.next();
}
current = current.next();
}
if(length%2 == 1){
middle = middle.next();
}
System.out.println("length of LinkedList: " + length);
System.out.println("middle element of LinkedList : "                                  + middle);
}
}
private Node tail;
}
}
tail.next = node;
tail = node;
}
public static class Node{
private Node next;
private String data;
public Node(String data){
this.data = data;
}
public String data() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node next() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public String toString(){
return this.data;
}
}
}
Output:
``````

#### 67. Wap to convert binary tree to Doubly linked list.

``````public class BinaryTreeDoubly {
public static class Node{
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
//Represent the root of the binary tree
public Node root;
//convertbtToDLL() will convert the given binary tree to corresponding doubly linked list
public void convertbtToDLL(Node node) {
//Checks whether node is null
if(node == null)
return;
//Convert left subtree to doubly linked list
convertbtToDLL(node.left);
//Both head and tail will point to node
}
//Otherwise, add node to the end of the list
else {
//node will be added after tail such that tail's right will point to node
tail.right = node;
//node's left will point to tail
node.left = tail;
//node will become new tail
tail = node;
}
//Convert right subtree to doubly linked list
convertbtToDLL(node.right);
}
//display() will print out the nodes of the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
System.out.println("Nodes of generated doubly linked list: ");
while(current != null) {
//Prints each node by incrementing the pointer.
System.out.print(current.data + " ");
current = current.right;
}
System.out.println();
}
public static void main(String[] args) {
BinaryTreeDoubly btd = new BinaryTreeToDLL();
//Add nodes to the binary tree
btd.root = new Node(10);
btd.root.left = new Node(20);
btd.root.right = new Node(30);
btd.root.left.left = new Node(40);
btd.root.left.right = new Node(50);
btd.root.right.left = new Node(60);
btd.root.right.right = new Node(70);
//Converts the given binary tree to doubly linked list
btd.convertbtToDLL(btd.root);
//Displays the nodes present in the list
btd.display();
}
}
Output:
Nodes of generated doubly linked list:
40 20 50 10 60 30 70``````

#### 68. Wap to generate a Doubly linked list of n nodes and count numbers of node.

``````public class CountNodes {
class Node{
int data;
Node previous;
Node next;
public Node(int data) {
this.data = data;
}
}
//Create a new node
Node newNode = new Node(data);
//If list is empty
tail.next = null;
}
else {
//newNode this will be added after tail such that tail's next will point to newNode
tail.next = newNode;
newNode.previous = tail;
tail = newNode;
tail.next = null;
}
}
//countNodes() this will count the nodes present in the list
public int countNodes() {
int counter = 0;
//Node current will point to start
while(current != null) {
//Increment the counter by 1 for each node
counter++;
current = current.next;
}
return counter;
}
//display() this will print out the elements of the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
System.out.println("Elements of doubly linked list: ");
while(current != null) {
//Prints each node by incrementing the pointer.
System.out.print(current.data + " ");
current = current.next;
}
}
public static void main(String[] args) {
CountNodes cn = new CountList();
//Displays the nodes present in the list
cn.display();
//Counts the nodes present in the given list
System.out.println("\nCount of nodes present in the list: " + cn.countNodes());
}
}
Output:
10 20 30 40 50
Count of nodes present in the list: 5``````

#### 70. Wap to get value of maximum and minimum node in Double Linked List.

``````public class MinMaxNode {
class Node{
int data;
Node previous;
Node next;
public Node(int data) {
this.data = data;
}
}
Node newNode = new Node(data);
//If list is empty
tail.next = null;
}
else {
tail.next = newNode;
//newNode's previous will point to end
newNode.previous = tail;
//newNode will become new end
tail = newNode;
tail.next = null;
}
}
//MinimumNode() will find out minimum value node in the list
public int minimumNode() {
//Node current will point to head
int min;
//Checks if list is empty
System.out.println("List is empty");
return 0;
}
else {
//Initially, min will store the value of head's data
while(current != null) {
//If the value of min is greater than the current's data
//Then, replace the value of min with current node's data
if(min > current.data)
min = current.data;
current = current.next;
}
}
return min;
}
//MaximumNode() will find out maximum value node in the list
public int maximumNode() {
//Node current will point to head
int max;
//Checks if list is empty
System.out.println("List is empty");
return 0;
}
else {
//Initially, max will store the value of head's data
while(current != null) {
if(current.data > max)
max = current.data;
current = current.next;
}
}
return max;
}
public static void main(String[] args) {
MinMaxNode mmn = new MinMaxNode();
//Prints the minimum value node in the list
System.out.println("Minimum value node in the list: "+ dList.minimumNode());
//Prints the maximum value node in the list
System.out.println("Maximum value node in the list: "+ dList.maximumNode());
}
}
Output:
Minimum value node : 11
Maximum value node : 49``````

#### 71. Wap to add new node at middle of Double Linked List.

``````public class InsertNodeMiddle {
class Node{
int data;
Node previous;
Node next;
public Node(int data) {
this.data = data;
}
}
public int size = 0;
//Create a new node
Node newNode = new Node(data);
//If list is empty
//Both head and tail will point to newNode
//head's previous will point to null
//tail's next will point to null, as it is the last node of the list
tail.next = null;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode's previous will point to tail
newNode.previous = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to null
tail.next = null;
}
//Size will count the number of nodes present in the list
size++;
}
//Create a new node
Node newNode = new Node(data);
//If list is empty
//Both head and tail will point to newNode
//head's previous will point to null
//tail's next point to null, as it is the last node of the list
tail.next = null;
}
else {
Node current = head, temp = null;
//Store the mid position of the list
int mid = (size % 2 == 0) ? (size/2) : ((size+1)/2);
//Iterate through list till current points to mid position
for(int i = 1; i < mid; i++){
current = current.next;
}
//Node temp will point to node next to current
temp = current.next;
temp.previous = current;
//newNode will be added between current and temp
current.next = newNode;
newNode.previous = current;
newNode.next = temp;
temp.previous = newNode;
}
size++;
}
//display() will print out the nodes of the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing the pointer.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
InsertNodeMiddle inm = new InsertNodeMiddle();
System.out.println("Initial list: ");
inm.display();
//Adding node '30' in the middle
System.out.println( "Updated List: ");
inm.display();
//Adding node '40' in the middle
System.out.println("Updated List: ");
inm.display();
//Adding node '50' in the middle
System.out.println("Updated List: ");
inm.display();
}
}
Output:
Initial  list:
10 20
Updated List:
10 30 20
Updated List:
10 30 40 20
Updated List:
10 30 50 40 20 ``````

#### 72. Wap to add new node at the end of Double Linked List.

``````public class BinarySearchTreeImplementation {
private BstNode root;
public boolean isEmpty() {
return (this.root == null);
}
public void insert(Integer data) {
System.out.print("[input: "+data+"]");
if(root == null) {
this.root = new BstNode(data);
System.out.println(" -> inserted: "+data);
return;
}
insertNode(this.root, data);
System.out.print(" -> inserted: "+data);
System.out.println();
}
private BstNode insertNode(BstNode root, Integer data) {
BstNode tmpNode = null;
System.out.print(" ->"+root.getData());
if(root.getData() >= data) {
System.out.print(" [L]");
if(root.getLeft() == null) {
root.setLeft(new BstNode(data));
return root.getLeft();
} else {
tmpNode = root.getLeft();
}
} else {
System.out.print(" [R]");
if(root.getRight() == null) {
root.setRight(new BstNode(data));
return root.getRight();
} else {
tmpNode = root.getRight();
}
}
return insertNode(tmpNode, data);
}
public static void main(String a[]) {
BinarySearchTreeImpl bst = new BinarySearchTreeImpl();
bst.insert(16);
bst.insert(23);
bst.insert(6);
bst.insert(21);
bst.insert(8);
bst.insert(10);
bst.insert(20);
}
}``````

#### 73. Wap to remove node from middle of Double Linked List.

``````Class DeleteNodeMiddle {
class Node{
int data;
Node previous;
Node next;
public Node(int data) {
this.data = data;
}
}
public int size = 0;
//Create a new node
Node newNode = new Node(data);
//If list is empty
//Both head and tail will point to newNode
//head's previous will point to null
//tail's next will point to null, as it is the last node of the list
tail.next = null;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode's previous will point to tail
newNode.previous = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to null
tail.next = null;
}
//Size will count the number of nodes present in the list
size++;
}
//deleteFromMid() will delete a node from middle of the list
public void deleteFromMid() {
//Checks whether list is empty
return;
}
else {
//Store the mid position of the list
int mid = (size % 2 == 0) ? (size/2) : ((size+1)/2);
//Iterate through list till current points to mid position
for(int i = 1; i < mid; i++){
current = current.next;
}
//If middle node is head of the list
}
//If middle node is tail of the list
else if(current == tail) {
tail = tail.previous;
}
else {
current.previous.next = current.next;
current.next.previous = current.previous;
}
//Delete the middle node
current = null;
}
size--;
}
//display() will print out the nodes of the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing the pointer.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
DeleteNodeMiddle dnm = new DeleteNodeMiddle();
//Printing original list
System.out.println("Initial List: ");
dnm.display();
dnm.deleteFromMid();
//Printing updated list
System.out.println("Updated List: ");
dnm.display();
}
}
}
Output:
Initial List:
10 20 30 40 50
Updated List:
10 20 40 50
Updated List:
10 40 50
Updated List:
10 50
Updated List:
50
Updated List:
List is empty``````

#### 74. Wap to remove node at the begining from Double Linked List.

``````public class DeleteNodeStart
{
class Node{
int data;
Node previous;
Node next;
public Node(int data) {
this.data = data;
}
}
//Create a new node
Node newNode = new Node(data);
//If list is empty
//Both head and tail will point to newNode
//head's previous will point to null
//tail's next will point to null, as it is the last node of the list
tail.next = null;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode's previous will point to tail
newNode.previous = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to null
tail.next = null;
}
}
//deleteFromStart() will delete a node from the beginning of the list
public void deleteFromStart() {
//Checks whether list is empty
return;
}
else {
//Checks whether the list contains only one element
//head will point to next node in the list
}
//If the list contains only one element
//then, it will remove node and now both head and tail will point to null
else {
}
}
}
//display() will print out the nodes of the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing the pointer.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
DeleteNodeStart dns = new DeleteNodeStart();
//Printing original list
System.out.println("Initial  List: ");
dns.display();
dns.deleteFromStart();
//Printing updated list
System.out.println("Updated List: ");
dns.display();
}
}
}
Output:
Initial List:
10 20 30 40 50
Updated List:
20 30 40 50
Updated List:
30 40 50
Updated List:
40 50
Updated List:
50
Updated List:
List is empty``````

#### 75. Wap to remove node from the end of Doubly Linked List.

``````public class DeleteNodeEnd {
class Node{
int data;
Node previous;
Node next;
public Node(int data) {
this.data = data;
}
}
//Create a new node
Node newNode = new Node(data);
//If list is empty
//Both head and tail will point to newNode
//head's previous will point to null
//tail's next will point to null, as it is the last node of the list
tail.next = null;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode's previous will point to tail
newNode.previous = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to null
tail.next = null;
}
}
//deleteFromEnd() will delete a node from the end of the list
public void deleteFromEnd() {
//Checks whether list is empty
return;
}
else {
//Checks whether the list contains only one node
//Previous node to the tail will become new tail
tail = tail.previous;
//Node next to current tail will be made null
tail.next = null;
}
//If the list contains only one element
//Then it will remove node and now both head and tail will point to null
else {
}
}
}
//display() will print out the nodes of the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing the pointer.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
DeleteNoteEnd dne = new DeleteEnd();
//Printing Initial list
System.out.println("Initial List: ");
dne.display();
dne.deleteFromEnd();
//Printing updated list
System.out.println("Updated List: ");
dne.display();
}
}
}
Output:
Initial List:
10 20 30 40 50
Updated List:
10 20 30 40
Updated List:
10 20 30
Updated List:
10 20
Updated List:
10
Updated List:
List is empty``````

#### 76. Wap to remove duplicate elements from Doubly Linked List.

``````public class RemoveDuplicateElemenstts {
class Node{
int data;
Node previous;
Node next;
public Node(int data) {
this.data = data;
}
}
Node newNode = new Node(data);
//If list is empty
//Both head and tail will point to newNode
//head's previous will point to null
//tail's next will point to null, as it is the last node of the list
tail.next = null;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode's previous will point to tail
newNode.previous = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to null
tail.next = null;
}
}
//removeDuplicateNode() will remove duplicate nodes from the list
public void removeDuplicateNode() {
//Node current will point to head
Node current, index, temp;
//Checks whether list is empty
return;
}
else {
//Initially, current will point to head node
for(current = head; current != null; current = current.next) {
//index will point to node next to current
for(index = current.next; index != null; index = index.next) {
if(current.data == index.data) {
//Store the duplicate node in temp
temp = index;
//index's previous node will point to node next to index thus, removes the duplicate node
index.previous.next = index.next;
if(index.next != null)
index.next.previous = index.previous;
//Delete duplicate node by making temp to null
temp = null;
}
}
}
}
}
//display() will print out the nodes of the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing the pointer.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
RemoveDuplicateElements rde = new RemoveDuplicateElements();
System.out.println("Initial list: ");
rde.display();
//Removes duplicate nodes
rde.removeDuplicateNode();
System.out.println("List after removing duplicates: ");
rde.display();
}
}
Output:
Initial list:
10 20 30 20 20 40 50 30
List after removing duplicates:
10 20 30 40 50``````

#### 77. Wap to rotate Doubly Linked List by N nodes.

``````public class RotatingList {
class Node{
int data;
Node previous;
Node next;
public Node(int data) {
this.data = data;
}
}
int size = 0;
//Create a new node
Node newNode = new Node(data);
//If list is empty
//Both head and tail will point to newNode
//head's previous will point to null
//tail's next will point to null, as it is the last node of the list
tail.next = null;
}
else {
//newNode will be added after tail such that tail's next will point to newNode
tail.next = newNode;
//newNode's previous will point to tail
newNode.previous = tail;
//newNode will become new tail
tail = newNode;
//As it is last node, tail's next will point to null
tail.next = null;
}
//Size will count the number of nodes present in the list
size++;
}
//rotateList() will rotate the list by given n nodes
public void rotateList(int n) {
//Initially, current will point to head
//n should not be 0 or greater than or equal to number of nodes present in the list
if(n == 0 || n >= size)
return;
else {
//Traverse through the list till current point to nth node
//after this loop, current will point to nth node
for(int i = 1; i < n; i++)
current = current.next;
//Now to move entire list from head to nth node and add it after tail
//Node next to nth node will be new head
//Previous node to head should be null
//nth node will become new tail of the list
tail = current;
//tail's next will point to null
tail.next = null;
}
}
//display() will print out the nodes of the list
public void display() {
//Node current will point to head
System.out.println("List is empty");
return;
}
while(current != null) {
//Prints each node by incrementing the pointer.
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
RotatingList rl = new RotatingList();
System.out.println("Initial List: ");
rl.display();
//Rotates list by 3 nodes
rl.rotateList(3);
System.out.println("Updated List: ");
rl.display();
}
}
Output:
Initial List:
10 20 30 40 50
Updated List:
40 50 10 20 30 ``````

#### 78. Wap to implement Binary Search Tree (BST).

``````ublic class BinarySearchTreeImplementation {
private BstNode root;
public boolean isEmpty() {
return (this.root == null);
}
public void insert(Integer data) {
System.out.print("[input: "+data+"]");
if(root == null) {
this.root = new BstNode(data);
System.out.println(" -> inserted: "+data);
return;
}
insertNode(this.root, data);
System.out.print(" -> inserted: "+data);
System.out.println();
}
private BstNode insertNode(BstNode root, Integer data) {
BstNode tmpNode = null;
System.out.print(" ->"+root.getData());
if(root.getData() >= data) {
System.out.print(" [L]");
if(root.getLeft() == null) {
root.setLeft(new BstNode(data));
return root.getLeft();
} else {
tmpNode = root.getLeft();
}
} else {
System.out.print(" [R]");
if(root.getRight() == null) {
root.setRight(new BstNode(data));
return root.getRight();
} else {
tmpNode = root.getRight();
}
}
return insertNode(tmpNode, data);
}
public static void main(String a[]) {
BinarySearchTreeImpl bst = new BinarySearchTreeImpl();
bst.insert(16);
bst.insert(23);
bst.insert(6);
bst.insert(21);
bst.insert(8);
bst.insert(10);
bst.insert(20);
}
}``````

#### 79. Wap to find maximum width of a binary tree.

``````import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeWidth {
public static class Node{
int data;
Node left;
Node right;
public Node(int data){
//Assigning data to the new node, set left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}
//Representing the root of binary tree
public Node root;
public BinaryTree(){
root = null;
}
//findMaximumWidth() this will find out the maximum width of the given binary tree
public int findMaximumWidth() {
int maxWidth = 0;
//Variable nodesLevel keep tracks of number of nodes in each level
int nodesLevel = 0;
//queue will be used to keep track of nodes of tree level-wise
//Check if root is null, then width will be 0
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else {
//Add root node to queue as it represents the first level
while(queue.size() != 0) {
//Variable nodesLevel will hold the size of queue i.e. number of elements in queue
nodesLevel = queue.size();
//maxWidth will hold maximum width.
//If nodesLevel is greater than maxWidth then, maxWidth will hold the value of nodesLevel
maxWidth = Math.max(maxWidth, nodesLevel);
//If variable nodesLevel contains more than one node
//then, for each node, we'll add left and right child of the node to the queue
while(nodesLevel > 0) {
Node current = queue.remove();
if(current.left != null)
if(current.right != null)
nodesLevel--;
}
}
}
return maxWidth;
}
public static void main(String[] args) {
BinaryTreeWidth bint = new BinaryTreeWidth();
//Adding nodes to the binary tree
bint.root = new Node(10);
bint.root.left = new Node(20);
bint.root.right = new Node(30);
bint.root.left.left = new Node(40);
bint.root.left.right = new Node(50);
bint.root.right.left = new Node(60);
bint.root.right.right = new Node(70);
bint.root.left.left.left = new Node(80);
//Display the maximum width of given tree
System.out.println("Width of the binary tree: " + bint.findMaximumWidth());
}
}
Output:
Width of the binary tree: 4``````

#### 80. Wap to find largest Node in Binary tree.

``````public class LargestNodeBST {
public static class Node{
int data;
Node left;
Node right;
public Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}
//Represent the root of binary tree
public Node root;
public LargestNode(){
root = null;
}
//largestElement() this will find out the largest node in the binary tree
public int largestElement(Node temp){
//Checking whether tree is empty
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else{
int leftMax, rightMax;
//Max will store temp's data
int max = temp.data;
//This will find largest element in left subtree
if(temp.left != null){
leftMax = largestElement(temp.left);
//Comparing max with leftMax and store greater value into max
max = Math.max(max, leftMax);
}
//This will find largest element in right subtree
if(temp.right != null){
rightMax = largestElement(temp.right);
//Comparing max with rightMax and store greater value into max
max = Math.max(max, rightMax);
}
return max;
}
}
public static void main(String[] args) {
LargestNodeBST bint = new LargestNodeBST();
//Adding nodes to the binary tree
bint.root = new Node(5);
bint.root.left = new Node(19);
bint.root.right = new Node(28);
bint.root.left.left = new Node(42);
bint.root.right.left = new Node(68);
bint.root.right.right = new Node(10);
//Display largest node in the binary tree
System.out.println("Largest Node in the binary tree: " + bintt.largestElement(bint.root));
}
}
Output:
Largest Node in the binary tree: 68``````

#### 81. Wap to find smallest node in Binary tree.

``````public class SmallestNodeBST {
public static class Node{
int data;
Node left;
Node right;
public Node(int data){
//Assigning data to the new node, set left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}
//Represents the root of binary tree
public Node root;
public SmallestNode(){
root = null;
}
//smallestElement() this will find out the smallest node in the binary tree
public int smallestElement(Node temp){
//Checking whether tree is empty
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else {
int leftMin, rightMin;
//Min will store temp's data
int min = temp.data;
//This will find smallest element in left subtree
if(temp.left != null){
leftMin = smallestElement(temp.left);
//If min is greater than leftMin then store the value of leftMin into min
min = Math.min(min, leftMin);
}
//This will find smallest element in right subtree
if(temp.right != null){
rightMin = smallestElement(temp.right);
//If min is greater than rightMin then store the value of rightMin into min
min = Math.min(min, rightMin);
}
return min;
}
}
public static void main(String[] args) {
SmallestNodeBST bint = new SmallestNodeBST();
//Adding nodes to the binary tree
bint.root = new Node(8);
bint.root.left = new Node(20);
bint.root.right = new Node(15);
bint.root.left.left = new Node(12);
bint.root.right.left = new Node(25);
bint.root.right.right = new Node(36);
//Displays smallest node in the binary tree
System.out.println("Smallest node in the binary tree: " + bint.smallestElement(bint.root));
}
}
Output:
Smallest node in the binary tree: 8``````

#### 82. Wap to find sum of all node in Binary Tree.

``````public class SumNodes {
public static class Node{
int data;
Node left;
Node right;
public Node(int data){
//Assigning data to the new node, set left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}
//Represent the root of binary tree
public Node root;
public SumOfNodes(){
root = null;
}
//calculateSum() this will calculate the sum of all the nodes present in the binary tree
public int calculateSum(Node temp){
int sum, sumLeft, sumRight;
sum = sumRight = sumLeft = 0;
//Check whether tree is empty
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else {
//Calculate the sum of nodes present in left subtree
if(temp.left != null)
sumLeft = calculateSum(temp.left);
//Calculate the sum of nodes present in right subtree
if(temp.right != null)
sumRight = calculateSum(temp.right);
//Calculate the sum of all nodes by adding sumLeft, sumRight and root node's data
sum = temp.data + sumLeft + sumRight;
return sum;
}
}
public static void main(String[] args) {
SumNodes bint = new SumNodes();
//Add nodes to the binary tree
bint.root = new Node(8);
bint.root.left = new Node(6);
bint.root.right = new Node(4);
bint.root.left.left = new Node(10);
bint.root.right.left = new Node(15);
//Displays the sum of all the nodes in the given binary tree
System.out.println("Sum of all nodes of binary tree: " + bint.calculateSum(bint.root));
}
}
Output:
Sum of all nodes of binary tree: 43``````

#### 83. Wap to find maximum depth or height of a tree.

``````public class BinaryTreeDepth {
//Represent the node of binary tree
public static class Node{
int data;
Node left;
Node right;
public Node(int data){
//Assigning data to the new node, set left and right children to null
this.data = data;
this.left = null;
this.right = null;
}
}
public Node root;
public BinaryTree(){
root = null;
}
//findHeight() this will determine the maximum height of the binary tree
public int findHeight(Node temp){
//Check whether tree is empty
if(root == null) {
System.out.println("Tree is empty");
return 0;
}
else {
int leftHeight = 0, rightHeight = 0;
//Calculate the height of left subtree
if(temp.left != null)
leftHeight = findHeight(temp.left);
//Calculate the height of right subtree
if(temp.right != null)
rightHeight = findHeight(temp.right);
//Compare height of left subtree and right subtree
//and store maximum of two in variable max
int max = (leftHeight > rightHeight) ? leftHeight : rightHeight;
//Calculate the total height of tree by adding height of root
return (max + 1);
}
}
public static void main(String[] args) {
BinaryTreeDepth bint = new BinaryTreeDepth();
//Adding nodes to the binary tree
bint.root = new Node(10);
bint.root.left = new Node(20);
bint.root.right = new Node(30);
bint.root.left.left = new Node(40);
bint.root.right.left = new Node(50);
bint.root.right.right = new Node(60);
bint.root.right.right.right= new Node(70);
bint.root.right.right.right.right = new Node(80);
//Displays the maximum height of the given binary tree
System.out.println("Height of given binary tree: " + bint.findHeight(bint.root));
}
}
Output:
Height of given binary tree: 5``````

#### 84. Wap to Connect Java Application with mysql database.

``````import java.sql.*;
class MysqlCon
{
public static void main(String args[])
{
try
{
Class.forName("com.mysql.jdbc.Driver");
Connection con=DriverManager.getConnection(
"jdbc:mysql://localhost:3306/Employees","root","root");
Statement stmt=con.createStatement();
ResultSet rs=stmt.executeQuery("select * from emp");
while(rs.next())
System.out.println(rs.getInt(1)+"  "+rs.getString(2)+"  "+rs.getString(3));
con.close();
}
catch(Exception e)
{
System.out.println(e);
}
}
}
``````

#### 85. Wap to get the object of ResultSetMetaData.

The getMetaData() method of ResultSet interface returns the object of ResultSetMetaData. Syntax:

``````import java.sql.*;
class Rsmd{
public static void main(String args[]){
try{
Class.forName("oracle.jdbc.driver.OracleDriver");
Connection con=DriverManager.getConnection(
"jdbc:oracle:thin:@localhost:1521:xe","system","oracle");
PreparedStatement ps=con.prepareStatement("select * from emp");
ResultSet rs=ps.executeQuery();
System.out.println("Total columns: "+rsmd.getColumnCount());
System.out.println("Column Name of 1st column: "+rsmd.getColumnName(1));
System.out.println("Column Type Name of 1st column: "+rsmd.getColumnTypeName(1));
con.close();
}catch(Exception e){ System.out.println(e);}
}
}
``````

#### 86. Wap to create table in database.

``````import java.sql.*;
public class JDBCExample
{
static final String JDBC_DRIVER = "com.mysql.jdbc.Driver";
static final String URL = "jdbc:mysql://localhost/STUDENTS";
static final String USER = "username";
static final String PASS = "password";
public static void main(String[] args)
{
Connection con = null;
Statement stmt = null;
Try
{
Class.forName("com.mysql.jdbc.Driver");
con = DriverManager.getConnection(URL, USER, PASS);
stmt = con.createStatement();
String sql = "CREATE TABLE REGISTRATION " +
"(id INTEGER not NULL, " +
" first VARCHAR(255), " +
" last VARCHAR(255), " +
" age INTEGER, " +
" PRIMARY KEY ( id ))";
stmt.executeUpdate(sql);
}
catch(Exception e)
{
e.printStackTrace();
}
finally
{
try
{
con.close();
stmt.close();
}
catch(Exception e)
{
e.printStackTrace();
}
}
}
}
``````

#### 87. Wap to insert record in to table in the Database.

``````import java.sql.*;
public class JDBCExample {
String URL = "jdbc:mysql://localhost:3306/STUDENTS";
public static void main(String[] args)
{
Connection conn = null;
Statement stmt = null;
try
{
Class.forName("com.mysql.jdbc.Driver");
conn = DriverManager.getConnection(URL, USER, PASS);
stmt = conn.createStatement();
String sql = "INSERT INTO Registration " +
"VALUES (100, 'Zara', 'Ali', 18)";
stmt.executeUpdate(sql);
sql = "INSERT INTO Registration " +
"VALUES (101, 'Mahnaz', 'Fatma', 25)";
stmt.executeUpdate(sql);
sql = "INSERT INTO Registration " +
"VALUES (102, 'Zaid', 'Khan', 30)";
stmt.executeUpdate(sql);
sql = "INSERT INTO Registration " +
"VALUES(103, 'Sumit', 'Mittal', 28)";
stmt.executeUpdate(sql);
}
catch(Exception e)
{
e.printStackTrace();
}
finally
{
try
{
con.close();
stmt.close();
}
catch(Exception e)
{
e.printStackTrace();
}
}
}
}
``````

#### 88. Wap to Delete records in to a table in the database.

``````public class JDBCExample
{
String URL = "jdbc:mysql://localhost:3306/STUDENTS";
public static void main(String[] args)
{
Connection conn = null;
Statement stmt = null;
try{
Class.forName("com.mysql.jdbc.Driver");
conn = DriverManager.getConnection(URL, USER, PASS);
stmt = conn.createStatement();
String sql = "DELETE FROM Registration " +
"WHERE id = 101";
stmt.executeUpdate(sql);
sql = "SELECT id, first, last, age FROM Registration";
ResultSet rs = stmt.executeQuery(sql);
while(rs.next())
{
int id  = rs.getInt("id");
int age = rs.getInt("age");
String first = rs.getString("first");
String last = rs.getString("last");
System.out.print(" ID:  " + id);
System.out.print(" , Age: " + age);
System.out.print(" , First: " + first);
System.out.println(" , Last: " + last);
}
}
catch(Exception e)
{
e.printStackTrace();
}
finally
{
try
{
con.close();
stmt.close();
rs.close();
}
catch(Exception e)
{
e.printStackTrace();
}
}
}
}
``````

#### 89. Wap to update records in to a table in the database.

``````import java.sql.*;
public class JDBCExample
{
static final String DB_URL = "jdbc:mysql://localhost:3306/STUDENTS";
static final String USER = "username";
static final String PASS = "password";
public static void main(String[] args)
{
Connection conn = null;
Statement stmt = null;
try
{
Class.forName("com.mysql.jdbc.Driver");
conn = DriverManager.getConnection(DB_URL, USER, PASS);
stmt = conn.createStatement();
String sql = "UPDATE Registration " +
"SET age = 30 WHERE id in (100, 101)";
stmt.executeUpdate(sql);
sql = "SELECT id, first, last, age FROM Registration";
ResultSet rs = stmt.executeQuery(sql);
while(rs.next())
{
int id  = rs.getInt("id");
int age = rs.getInt("age");
String first = rs.getString("first");
String last = rs.getString("last");
System.out.print("ID: " + id);
System.out.print(", Age: " + age);
System.out.print(", First: " + first);
System.out.println(", Last: " + last);
}
}
catch(Exception e)
{
e.printStackTrace();
}
finally
{
try
{
con.close();
stmt.close();
rs.close();
}
catch(Exception e)
{
e.printStackTrace();
}
}
}
}
``````

#### 90. Wap to print half pyramid using \$.

\$
\$ \$
\$ \$ \$
\$ \$ \$ \$
\$ \$ \$ \$ \$

``````public class Pattern {
public static void main(String[] args) {
int rows = 5;
for(int i = 1; i <= rows; ++i) {
for(int j = 1; j <= i; ++j) {
System.out.print("\$ ");
}
System.out.println();
}
}
}``````

#### 91. Wap to print half triangle using numbers.

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5

``````public class Pattern {
public static void main(String[] args) {
int rows = 5;
for(int i = 1; i <= rows; ++i) {
for(int j = 1; j <= i; ++j) {
System.out.print(j + " ");
}
System.out.println();
}
}
}``````

#### 92. Wap to print half triangle using alphabet.

A
B B
C C C
D D D D
E E E E E

``````public class Pattern {
public static void main(String[] args) {
char last = 'E', alphabet = 'A';
for(int i = 1; i <= (last-'A'+1); ++i) {
for(int j = 1; j <= i; ++j) {
System.out.print(alphabet + " ");
}
++alphabet;
System.out.println();
}
}
}``````

#### 93. Wap to print inverted half triangle using \$

\$ \$ \$ \$ \$
\$ \$ \$ \$
\$ \$ \$
\$ \$
\$

``````public class Pattern {
public static void main(String[] args) {
int rows = 5;
for(int i = rows; i >= 1; --i) {
for(int j = 1; j <= i; ++j) {
System.out.print("\$ ");
}
System.out.println();
}
}
}``````

#### 94. Wap to print inverted half triangle using numbers.

1 2 3 4 5
1 2 3 4
1 2 3
1 2
1

``````public class Pattern {
public static void main(String[] args) {
int rows = 5;
for(int i = rows; i >= 1; --i) {
for(int j = 1; j <= i; ++j) {
System.out.print(j + " ");
}
System.out.println();
}
}
}``````

#### 95. Wap to print full triangle using \$.

\$
\$ \$ \$
\$ \$ \$ \$ \$
\$ \$ \$ \$ \$ \$ \$
\$ \$ \$ \$ \$ \$ \$ \$ \$

``````public class Pattern {
public static void main(String[] args) {
int rows = 5, k = 0;
for(int i = 1; i <= rows; ++i, k = 0) {
for(int space = 1; space <= rows - i; ++space) {
System.out.print("  ");
}
while(k != 2 * i - 1) {
System.out.print("\$ ");
++k;
}
System.out.println();
}
}
}``````

#### 96. Wap to print full pyramid using number

1
2 3 2
3 4 5 4 3
4 5 6 7 6 5 4
5 6 7 8 9 8 7 6 5

``````public class Pattern {
public static void main(String[] args) {
int rows = 5, k = 0, count = 0, count1 = 0;
for(int i = 1; i <= rows; ++i) {
for(int space = 1; space <= rows - i; ++space) {
System.out.print("  ");
++count;
}
while(k != 2 * i - 1) {
if (count <= rows - 1) {
System.out.print((i + k) + " ");
++count;
}
else {
++count1;
System.out.print((i + k - 2 * count1) + " ");
}
++k;
}
count1 = count = k = 0;
System.out.println();
}
}
}``````

#### 97. Wap to print inverted full pyramid using \$.

\$ \$ \$ \$ \$ \$ \$ \$ \$
\$ \$ \$ \$ \$ \$ \$
\$ \$ \$ \$ \$
\$ \$ \$
\$

``````public class Pattern {
public static void main(String[] args) {
int rows = 5;
for(int i = rows; i >= 1; --i) {
for(int space = 1; space <= rows - i; ++space) {
System.out.print("  ");
}
for(int j=i; j <= 2 * i - 1; ++j) {
System.out.print("\$ ");
}
for(int j = 0; j < i - 1; ++j) {
System.out.print("\$ ");
}
System.out.println();
}
}
}
``````

#### 98. Wap to print Pascal’s Triangle.

1
1 1
1 2 1
1 3 3 1

``````public class Pattern {
public static void main(String[] args) {
int rows = 4, cof = 1;
for(int i = 0; i < rows; i++) {
for(int space = 1; space < rows - i; ++space) {
System.out.print("  ");
}
for(int j = 0; j <= i; j++) {
if (j == 0 || i == 0)
cof = 1;
else
cof = cof * (i - j + 1) / j;
System.out.printf("%4d", cof);
}
System.out.println();
}
}
}``````

#### 99. Wap to print Flyod triangle.

1
2 3
4 5 6

``````public class Pattern {
public static void main(String[] args) {
int rows = 3, number = 1;
for(int i = 1; i <= rows; i++) {
for(int j = 1; j <= i; j++) {
System.out.print(number + " ");
++number;
}
System.out.println();
}
}
}``````

#### 100. Wap to print the following pattern.

1
2 2
3 3 3
4 4 4 4
5 5 5 5 5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows ");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= i; j++)
{
System.out.print(i + " ");
}
System.out.println();
}
}
}``````

#### 101. Wap to print following pattern.

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4
1 2 3
1 2
1

``````public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows  ");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= i; j++)
{
System.out.print(j + " ");
}
System.out.println();
}
for (int i = rows; i >= 1; i--)
{
for (int j = 1; j < i; j++)
{
System.out.print(j + " ");
}
System.out.println();
}
}
}``````

#### 102. Wap to print the following pattern.

1 2 3 4 5
1 2 3 4
1 2 3
1 2
1
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows ");
int rows = sc.nextInt();
for (int i = rows; i >= 1; i--)
{
for (int j = 1; j <= i; j++)
{
System.out.print(j + " ");
}
System.out.println();
}
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= i; j++)
{
System.out.print(j + " ");
}
System.out.println();
}
}
}``````

#### 103. Wap to print following pattern.

5 4 3 2 1
4 3 2 1
3 2 1
2 1
1
1
2 1
3 2 1
4 3 2 1
5 4 3 2 1

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows ");
int rows = sc.nextInt();
for (int i = rows; i >= 1; i--)
{
for (int j = i; j >= 1; j--)
{
System.out.print(j + " ");
}
System.out.println();
}
for (int i = 1; i <= rows; i++)
{
for (int j = i; j >= 1; j--)
{
System.out.print(j + " ");
}
System.out.println();
}
}
}``````

#### 104. Wap to print following pattern.

5 4 3 2 1
5 4 3 2
5 4 3
5 4
5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows  ");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = rows; j >= i; j--)
{
System.out.print(j + " ");
}
System.out.println();
}
}
}``````

#### 105. Wap to print following pattern.

5
5 4
5 4 3
5 4 3 2
5 4 3 2 1

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = rows; i >= 1; i--)
{
for (int j = rows; j >= i; j--)
{
System.out.print(j + " ");
}
System.out.println();
}
}
}``````

#### 106. Wap to print following pattern.

1
2 1
3 2 1
4 3 2 1
5 4 3 2 1

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = i; j >= 1; j--)
{
System.out.print(j + " ");
}
System.out.println();
}
}
}``````

#### 107. Wap to print following pattern.

1
2 7
3 8 13
4 9 14 19
5 10 15 20 25

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
int temp = i;
for (int j = i; j >= 1; j--)
{
System.out.print(temp + " ");
temp = temp + rows;
}
System.out.println();
}
}
}``````

#### 108. Wap to print following pattern.

1
1 2 1
1 2 3 2 1
1 2 3 4 3 2 1
1 2 3 4 5 4 3 2 1

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= i; j++)
{
System.out.print(j + " ");
}
for (int k = i - 1; k >= 1; k--)
{
System.out.print(k + " ");
}
System.out.println();
}
}
}``````

#### 109. Wap to print following pattern.

1 2 3 4 5
1 2 3 4
1 2 3
1 2
1

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j < i; j++)
{
System.out.print(" ");
}
for (int k = 1; k <= rows - i + 1; k++)
{
System.out.print(k + " ");
}
System.out.println();
}
}
}``````

#### 110. Wap to print following pattern.

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4
1 2 3
1 2
1

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = rows; j > i; j--)
{
System.out.print(" ");
}
for (int k = 1; k <= i; k++)
{
System.out.print(k + " ");
}
System.out.println();
}
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= i; j++)
{
System.out.print(" ");
}
for (int k = 1; k <= rows - i; k++)
{
System.out.print(k + " ");
}
System.out.println();
}
}
}``````

#### 111. Wap to print following pattern.

12345
2345
345
45
5
5
45
345
2345
12345

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j < i; j++)
{
System.out.print(" ");
}
for (int k = i; k <= rows; k++)
{
System.out.print(k);
}
System.out.println();
}
for (int i = rows; i >= 1; i--)
{
for (int j = 1; j < i; j++)
{
System.out.print(" ");
}
for (int k = i; k <= rows; k++)
{
System.out.print(k);
}
System.out.println();
}
}
}``````

#### 112. Wap to print following pattern.

1 2 3 4 5
2 3 4 5
3 4 5
4 5
5
5
4 5
3 4 5
2 3 4 5
1 2 3 4 5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j < i; j++)
{
System.out.print(" ");
}
for (int k = i; k <= rows; k++)
{
System.out.print(k + " ");
}
System.out.println();
}
for (int i = rows; i >= 1; i--)
{
for (int j = 1; j < i; j++)
{
System.out.print(" ");
}
for (int k = i; k <= rows; k++)
{
System.out.print(k + " ");
}
System.out.println();
}
}
}``````

#### 113. Wap to print following pattern.

5
4 5
3 4 5
2 3 4 5
1 2 3 4 5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = rows; i >= 1; i--)
{
for (int j = 1; j < i; j++)
{
System.out.print(" ");
}
for (int k = i; k <= rows; k++)
{
System.out.print(k + " ");
}
System.out.println();
}
}
}``````

#### 114. Wap to print following pattern.

1
1 0
1 0 1
1 0 1 0
1 0 1 0 1

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= i; j++)
{
System.out.print(j % 2 + " ");
}
System.out.println();
}
}
}``````

#### 115. Wap to print following pattern.

1 0 0 0 0
0 2 0 0 0
0 0 3 0 0
0 0 0 4 0
0 0 0 0 5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j < i; j++)
{
System.out.print("0 ");
}
System.out.print(i + " ");
for (int k = i; k < rows; k++)
{
System.out.print("0 ");
}
System.out.println();
}
}
}``````

#### 116. Wap to print following pattern.

1 1 1 1 1
1 1 1 2 2
1 1 3 3 3
1 4 4 4 4
5 5 5 5 5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = rows; j > i; j--)
{
System.out.print(1 + " ");
}
for (int k = 1; k <= i; k++)
{
System.out.print(i + " ");
}
System.out.println();
}
}
}``````

#### 117. Wap to print following pattern.

1 2 3 4 5 4 3 2 1
2 3 4 5 4 3 2
3 4 5 4 3
4 5 4
5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = i; j <= rows; j++)
{
System.out.print(j + " ");
}
for (int k = rows - 1; k >= i; k--)
{
System.out.print(k + " ");
}
System.out.println();
}
}
}``````

#### 118. Wap to print following pattern.

1
2 2
3 3 3
4 4 4 4
5 5 5 5 5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = rows; j > i; j--)
{
System.out.print(" ");
}
for (int k = 1; k <= i; k++)
{
System.out.print(i + " ");
}
System.out.println();
}
}
}``````

#### 119. Wap to print following pattern.

5 5 5 5 5
4 5 5 5 5
3 4 5 5 5
2 3 4 5 5
1 2 3 4 5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = rows; i >= 1; i--)
{
for (int j = i; j < rows; j++)
{
System.out.print(j + " ");
}
for (int k = rows - i; k < rows; k++)
{
System.out.print(5 + " ");
}
System.out.println();
}
}
}``````

#### 120. Wap to print following pattern.

1
2 6
3 7 10
4 8 11 13
5 9 12 14 15

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
int k = 1;
for (int i = 1; i <= rows; i++)
{
k=i;
for (int j = 1; j <= i; j++)
{
System.out.print(k + " ");
k = k + rows - j;
}
System.out.println();
}
}
}``````

#### 121. Wap to print following pattern.

1
2 4
3 6 9
4 8 12 16
5 10 15
6 12
7

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
int temp = 1;
for(int i=1; i<=rows/2+1; i++)
{
for(int j=1;j<=i;j++)
{
System.out.print(temp*j+" ");
}
System.out.println();
temp++;
}
for(int i=1; i<=rows/2; i++)
{
for(int j=1;j<=rows/2+1-i;j++)
{
System.out.print(temp*j+" ");
}
System.out.println();
temp++;
}
}
}``````

#### 122. Wap to print following pattern.

1
2 9
3 8 10
4 7 11 14
5 6 12 13 15

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 0; i < rows; i++)
{
for (int j = 0; j <= i; j++)
{
if (j % 2 == 0)
{
System.out.print(1 + j * rows - (j - 1) * j / 2 + i - j + " ");
} else
{
System.out.print(1 + j * rows - (j - 1) * j / 2 + rows - 1 - i + " ");
}
}
System.out.println();
}
}
}``````

#### 123. Wap to print following pattern.

1 10 11 20 21
2 9 12 19 22
3 8 13 18 23
4 7 14 17 24
5 6 15 16 25

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < rows; j++)
{
if (j % 2 == 0)
System.out.print((rows * (j)) + i + 1 + " ");
else
System.out.print((rows * (j + 1)) - i + " ");
}
System.out.print("\n");
}
}
}``````

#### 124. Wap to print following pattern.

5 5 5 5 5
5 4 4 4 4
5 4 3 3 3
5 4 3 2 2
5 4 3 2 1

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
int temp = 0;
for (int i = rows; i >= 1; i--)
{
for (int j = rows ; j >= i; j--)
{
System.out.print(j + " ");
temp =j;
}
for (int k = rows - i+1; k < rows; k++)
{
System.out.print(temp + " ");
}
System.out.println();
}
}
}``````

#### 125. Wap to print following pattern.

5
4 5 4
3 4 5 4 3
2 3 4 5 4 3 2
1 2 3 4 5 4 3 2 1
2 3 4 5 4 3 2
3 4 5 4 3
4 5 4
5

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = rows; i >= 1; i--)
{
for (int j = i; j <= rows; j++)
{
System.out.print(j + " ");
}
for (int k = rows-1; k >= i; k--)
{
System.out.print(k + " ");
}
System.out.println();
}
for (int i = 2; i <= rows; i++)
{
for (int j = i; j <= rows; j++)
{
System.out.print(j + " ");
}
for (int k = rows-1; k >= i; k--)
{
System.out.print(k + " ");
}
System.out.println();
}
}
}``````

#### 126. Wap to print following pattern.

1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
int j = i;
for (int k = 1; k <= rows; k++)
{
System.out.print(j + " ");
j++;
if (j > rows)
j = 1;
}
System.out.println();
}
sc.close();
}
}``````

#### 127. Wap to print following pattern.

1 3 5 7 9
3 5 7 9 1
5 7 9 1 3
7 9 1 3 5
9 1 3 5 7

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
int j = (i * 2) - 1;
for (int k = 1; k <= rows; k++)
{
System.out.print(j + " ");
j += 2;
if (j > (rows * 2) - 1)
j = 1;
}
System.out.println();
}
sc.close();
}
}``````

#### 128. Wap to print following pattern.

1 1
12 21
123 321
1234 4321
1234554321

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i = 1; i <= rows; i++)
{
for (int j = 1; j <= i; j++)
{
System.out.print(j);
}
for (int j= i*2 ; j < rows*2; j++)
{
System.out.print(" ");
}
for (int l = i; l >= 1; l--)
{
System.out.print(l);
}
System.out.println();
}
sc.close();
}
}``````

#### 129. Wap to print following pattern.

1
2 3
6 5 4
7 8 9 10
15 14 13 12 11

``````import java.util.Scanner;
public class Pattern
{
public static void main(String[] args)
{
int curRow = 1;
int counter = 1;
// Create a new Scanner object
Scanner sc = new Scanner(System.in);
// Get the number of rows from the user
System.out.println("Enter the number of rows");
int rows = sc.nextInt();
for (int i=1; i<= rows; i++)
{
if (i % 2 == 0)
{
for (int j = 1; j<=i; j++)
{
System.out.print(counter  +" ");
counter++;
}
}
else
{
int reverse = curRow + counter - 1;
for (int j = 0; j<i; j++)
{
System.out.print(reverse--  +" ");
counter++;
}
}
System.out.println();
curRow++;
}
}
}``````

#### 130. Bubble Sort

Bubble sorting is one of the simplest sorts. The general idea is to swap small numbers to the front by comparing and exchanging with adjacent elements. This process is similar to the fact that the blisters rise, hence the name. Take a chestnut and sort the unordered sequences of 5, 3, 8, 6, and 4. First, bubbling from the back to the front, 4 and 6 comparison, swapping 4 to the front, and the sequence becomes 5, 3, 8, 4, 6. In the same way, 4 and 8 are exchanged, and 5, 3, 4, 8, 6, 3, and 4 are exchanged. 5 and 3 exchange, become 3,5,4,8,6,3. This time the bubbling is finished, the smallest number 3 is discharged to the front. Bubbling the remaining sequences in turn yields an ordered sequence. The time complexity of bubble sorting is O(n^2).

``````Public  class  BubbleSort {
Public  static  void  bubbleSort ( int [] arr ) {
if (arr ==  null  || arr . length ==  0 )
return ;
for ( int i = 0 ; i < arr . length - 1 ; i ++ ) {
for ( Int j = arr . length - 1 ; j > i; j-- ) {
if (arr[j] < arr[j - 1 ]) {
Swap(arr, j - 1 , j);
}
}
}
}
Public  static  void  swap ( int [] arr , int  i , int  j ) {
int temp = arr[i];
Arr[i] = arr[j];
Arr[j] = temp;
}
}
``````

#### 131. Select Sort

The idea of ​​choosing sorting is actually similar to bubble sorting, which puts the smallest element to the front after a sort. But the process is different, bubble sorting is through adjacent comparisons and exchanges. The choice of sorting is through the choice of the whole. For a chestnut, simple sorting of the unordered sequence of 5, 3, 8, 6, 4, first choose the smallest number other than 5 to exchange with 5, that is, select 3 and 5 exchanges, after a sorting becomes 3,5,8,6,4. Select and exchange the remaining sequences at once, and finally get an ordered sequence. In fact, the choice of sorting can be seen as the optimization of the bubble sorting, because the purpose is the same, but the sorting is only exchanged under the premise of determining the minimum number, which greatly reduces the number of exchanges. The time complexity of selecting sorting is O(n^2)

``````public class SelectSort {
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex = 0;
for(int i=0; i<arr.length-1; i++) {
minIndex = i;
for(int j=i+1; j<arr.length; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) {
swap(arr, i, minIndex);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
``````

#### 132. Insert Sort

Insert sorting does not achieve sorting by swapping locations but by finding the appropriate location insert elements. I believe that everyone has had the experience of playing cards, especially the number of cards. You may have to sort out your cards when you split the cards. How do you sort them out when you have more cards? Just get a card and find a suitable place to insert. This principle is actually the same as insert sorting. For a chestnut, simply insert the 5, 3, 8, 6, 4 unordered sequence, first assume that the position of the first number is correct. Think about the first card when you get it. . Then 3 is to be inserted in front of 5, and 5 is moved back to 3, 5, 8, 6, and 4. It should be the same when thinking about finishing cards. Then 8 does not move, 6 is inserted in front of 8, 8 is shifted back by one, 4 is inserted in front of 5, and one is moved backward from 5 to one. Note that when inserting a number, make sure that the number before the number is already ordered. The time complexity of simple insert sorting is also O(n^2).

``````public class InsertSort {
public static void insertSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=1; i<arr.length; i++) {
int j = i;
int target = arr[i];
while(j > 0 && target < arr[j-1]) {
arr[j] = arr[j-1];
j --;
}
arr[j] = target;
}
}
}
``````

#### 133. Quick Sort

Quick sorting is very high-end when listening to a name. Quick sorting is actually the best performing sorting algorithm in practical applications. Quick sorting is high-end, but in fact its idea is from bubble sorting. Bubble sorting is to minimize the bubbling to the top by comparing and swapping adjacent elements, while fast sorting is to compare and exchange decimals and large numbers. Not only will the decimals bubble up to the top but also the big numbers below.

Give a chestnut: Quickly sort the unordered sequence of 5, 3, 8, 6, 4. The idea is that the right pointer is smaller than the reference number, and the left pointer is larger than the reference number and exchanged.

5,3,8,6,4 Use 5 as the benchmark for comparison. Finally, move 5 small to the left of 5, and move to the right of 5 by 5.

5,3,8,6,4 First set i, j two pointers point to the two ends, j pointer scan first (think why?) 4 to 5 small stop. Then i scan, 8 to 5 stop. Exchange i, j position.

5,3,4,6,8 Then the j pointer is scanned again. At this time, when j scans 4, the two pointers meet. stop. Then exchange 4 and the reference number.

4,3,5,6,8 After one division, the goal of the left side is smaller than 5 and the right side is larger than 5. The left and right subsequences are then recursively sorted to finally obtain an ordered sequence.

There is a question left on it. Why do you have to move the pointer first? First of all, this is not absolute, depending on the position of the reference number, because when the last two pointers meet, the reference number is exchanged to the position of the encounter. Generally, the first number is selected as the reference number, then it is on the left side, so the number of the last encounters must be exchanged with the reference number, so the number of encounters must be smaller than the reference number. So the j pointer moves first to find a number smaller than the base number.

Quick sorting is unstable, and its time average time complexity is O(nlgn).

``````public class QuickSort {
//一次划分
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
int pivotPointer = left;
while(left < right) {
while(left < right && arr[right] >= pivotKey)
right --;
while(left < right && arr[left] <= pivotKey)
left ++;
swap(arr, left, right); //把大的交换到右边，把小的交换到左边。
}
swap(arr, pivotPointer, left); //最后把pivot交换到中间
return left;
}
public static void quickSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos-1);
quickSort(arr, pivotPos+1, right);
}
public static void sort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
quickSort(arr, 0, arr.length-1);
}
public static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
``````

#### 134. Heap Sorting

Heap sorting is a sorting of choices implemented by means of heaps, and the idea is sorted with simple choices. The following is an example of a large top heap. Note: If you want to sort in ascending order, use the big top heap, and vice versa. The reason is that the top element of the heap needs to be swapped to the end of the sequence.

First, implementing heap sorting requires solving two problems:

How to make a heap from an unordered sequence key?

How do you adjust the remaining elements to a new heap after outputting the top element?

The first problem is that you can directly use a linear array to represent a heap. Building a heap from the initial unordered sequence requires a bottom-up adjustment from the first non-leaf element to a heap.

The second question, how to adjust to piles? The first is to exchange the top and bottom elements. Then compare the left and right child nodes of the current top element, because in addition to the current heap top element, the left and right child heaps satisfy the condition, then the current top top element needs to be exchanged with the larger (large top heap) of the left and right child nodes until Leaf node. We call this adjustment from the top of the pile to the screen.

The process of building a heap from an unordered sequence is a process of repeated screening. If this sequence is considered to be a complete binary tree, then the last non-terminal node is n/2 to take the bottom element, and thus can be filtered. Give a chestnut:

The stacking of 49, 38, 65, 97, 76, 13, 27, 49 sequences The initial heap and adjustment process is as follows:

``````public class HeapSort {
public static void heapAdjust(int[] arr, int start, int end) {
int temp = arr[start];
for(int i=2*start+1; i<=end; i*=2) {
if(i < end && arr[i] < arr[i+1]) {
i ++;
}
if(temp >= arr[i]) {
break;
}
arr[start] = arr[i];
start = i;
}
arr[start] = temp;
}
public static void heapSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=arr.length/2; i>=0; i--) {
}
for(int i=arr.length-1; i>=0; i--) {
swap(arr, 0, i);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
``````

#### 135. Hill Sorting

Hill sorting is an efficient implementation of insert sorting, also called downsizing incremental sorting. In simple insert sorting, if the sequence to be sorted is positive, the time complexity is O(n). If the sequence is basically ordered, the efficiency of using direct insert sorting is very high. Hill sorting takes advantage of this feature. The basic idea is: first divide the entire sequence to be recorded into several sub-sequences for direct insertion sorting, and then perform a direct insertion sorting on all records when the records in the entire sequence are basically ordered.

Give a chestnut:

As can be seen from the above sorting process, the feature of the Hill sorting is that the subsequence is not simply segmented by segment, but a record separated by an increment is composed into a subsequence. As in the example above, the increment of the first sort is 5, and the increment of the second sort is 3. Since the keywords recorded in the first two insertions are compared with the keywords of the previous record in the same subsequence, the smaller records are not moved step by step, but jumped to Moving forward, so that when the last order is sorted, the entire sequence has been basically ordered, as long as a small amount of comparison and movement of the record is made. Therefore, Hill sorting is more efficient than direct insert sorting.

The analysis of Hill sorting is complex, and time complexity is a function of the increment taken, which involves some mathematical problems. However, based on a large number of experiments, when n is in a certain range, the time complexity can reach O(n^1.3).

``````public class ShellSort {
public static void shellInsert(int[] arr, int d) {
for(int i=d; i<arr.length; i++) {
int j = i - d;
int temp = arr[i];
while (j>=0 && arr[j]>temp) {
arr[j+d] = arr[j];
j -= d;
}
if (j != i - d)
arr[j+d] = temp;
}
}
public static void shellSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int d = arr.length / 2;
while(d >= 1) {
shellInsert(arr, d);
d /= 2;
}
}
}
``````

#### 136. Merge Sort

Merging and sorting is another different sorting method, because the merge sorting uses the idea of ​​recursive partitioning, so it is easier to understand. The basic idea is to recursively sub-problems and then merge the results. The sequence to be sorted is treated as two ordered subsequences, then the two subsequences are merged, and the subsequences are then treated as two ordered sequences. . . . . Looking backwards, in fact, it is the first two or two mergers, and then the four or four mergers. . . Eventually an ordered sequence is formed. The space complexity is O(n) and the time complexity is O(nlogn).

``````public class MergeSort {
public static void mergeSort(int[] arr) {
mSort(arr, 0, arr.length-1);
}
public static void mSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int mid = (left + right) / 2;
mSort(arr, left, mid);
mSort(arr, mid+1, right);
merge(arr, left, mid, right);
}
public static void merge(int[] arr, int left, int mid, int right) {
//[left, mid] [mid+1, right]
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while(i <= mid && j <= right) {
if(arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while(i <= mid) {
temp[k++] = arr[i++];
}
while(j <= right) {
temp[k++] = arr[j++];
}
for(int p=0; p<temp.length; p++) {
arr[left + p] = temp[p];
}
}
}
``````

#### 137. Count Sort

If an interviewer asks you to write an O(n) time complexity sorting algorithm during the interview, you should never say: This is impossible! Although the lower limit of the previous sort based on comparison is O(nlogn). However, there is indeed a linear time complexity ordering, except that there is a premise that the number to be sorted must satisfy a certain range of integers, and counting sorting requires more auxiliary space. The basic idea is to count the number of each number by using the number to be sorted as the subscript of the count array. Then output sequentially to get an ordered sequence.

``````public class CountSort {
public static void countSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int max = max(arr);
int[] count = new int[max+1];
Arrays.fill(count, 0);
for(int i=0; i<arr.length; i++) {
count[arr[i]] ++;
}
int k = 0;
for(int i=0; i<=max; i++) {
for(int j=0; j<count[i]; j++) {
arr[k++] = i;
}
}
}
public static int max(int[] arr) {
int max = Integer.MIN_VALUE;
for(int ele : arr) {
if(ele > max)
max = ele;
}
return max;
}
}
``````

#### 138. Bucket Sort

Bucket sorting is an improvement and promotion of counting sorting, but there are many materials on the Internet that confuse counting sorting and bucket sorting. In fact, bucket sorting is much more complicated than counting sorting.

The basic idea of ​​bucket sorting:

Suppose there is a set of key sequence K[1….n] of length N. First divide this sequence into M subintervals (barrels). Then, based on a mapping function, the keyword k of the sequence to be sorted is mapped into the i-th bucket (ie, the subscript i of the bucket array B), then the keyword k is taken as an element in B[i] (each Bucket B[i] is a set of sequences of size N/M). Then compare and sort all the elements in each bucket B[i] (you can use fast queue). Then enumerate all the contents of the output B….B[M] in sequence, which is an ordered sequence. Bindex=f(key) where bindex is the subscript of the bucket array B (ie, the bindex bucket), and k is the key of the sequence to be sorted. The key to bucket sorting efficiency is the mapping function, which must be done: if the keyword k1 < k2, then f(k1) <= f(k2).

In other words, the minimum data in B(i) is greater than the largest data in B(i-1). Obviously, the determination of the mapping function has a lot to do with the characteristics of the data itself.

Give a chestnut:

Suppose the sequence K = {49, 38, 35, 97, 76, 73, 27, 49}. These data are all between 1 and 100. So we customize 10 buckets and then determine the mapping function f(k) = k/10. Then the first keyword 49 will be located in the 4th bucket (49/10=4). All the keywords are piled into the bucket in turn, and quickly sorted in each non-empty bucket to get the figure as shown. An ordered sequence can be obtained by sequentially outputting the data in each B[i].

Bucket sorting analysis:

Bucket sorting utilizes the mapping of functions, reducing almost all comparison work. In fact, the calculation of the f(k) value of bucket sorting is equivalent to the division in the fast row, the subsequence in the hill sorting, the subproblem in the merge sorting, and the large amount of data has been segmented into basically ordered. Data block (bucket). Then you only need to do advanced comparison sorting on a small amount of data in the bucket.

The time complexity of bucket sorting for N keywords is divided into two parts:

(1) Cycle calculation of the bucket mapping function for each keyword. This time complexity is O(N).

(2) Using the advanced comparison sorting algorithm to sort all the data in each bucket, the time complexity is ∑ O(Ni*logNi). Where Ni is the amount of data for the i-th bucket.

Obviously, part (2) is the decisive factor in the performance of the barrel sorting. Minimizing the amount of data in the bucket is the only way to increase efficiency (because the best average time complexity based on comparison sorting can only reach O(N*logN)). Therefore, we need to do the following two things:

(1) The mapping function f(k) can evenly distribute N data into M buckets, so that each bucket has [N/M] data amount.

(2) Try to increase the number of buckets. In the limit case, only one data can be obtained per bucket, which completely avoids the “comparison” sorting operation of the data in the bucket. Of course, it is not easy to do this. In the case of a large amount of data, the f(k) function will make the number of bucket collections huge and the space was wasted. This is a trade-off between time and space costs.

For N rows of data to be queued, M buckets, the average bucket sorting average time complexity of each bucket [N/M] data is:

O(N)+O(M*(N/M) log(N/M))=O(N+N (logN-logM))=O(N+N logN-N logM) When N=M, That is, in the limit case, there is only one data per bucket. The best efficiency of bucket sorting can reach O(N).

Summary: The average time complexity of bucket sorting is linear O(N+C), where C=N*(logN-logM). If the number of buckets M is larger with respect to the same N, the efficiency is higher, and the best time complexity reaches O(N). Of course, the space complexity of bucket sorting is O(N+M). If the input data is very large and the number of buckets is very large, the space cost is undoubtedly expensive. In addition, bucket sorting is stable.

``````public class BucketSort {
public static void bucketSort(int[] arr) {
if(arr == null && arr.length == 0)
return ;
int bucketNums = 10;
List<List<Integer>> buckets = new ArrayList<List<Integer>>();
for(int i=0; i<10; i++) {
}
for(int i=0; i<arr.length; i++) {
}
for(int i=0; i<buckets.size(); i++) {
if(!buckets.get(i).isEmpty()) {
Collections.sort(buckets.get(i);
}
}
int k = 0;
for(List<Integer> bucket : buckets) {
for(int ele : bucket) {
arr[k++] = ele;
}
}
}
public static int f(int x) {
return x / 10;
}
}
``````

#### 139. Cardinality Sort

The cardinality sorting is a sorting method different from the previous sorting method, and the cardinality sorting does not require comparison between the recording keywords. Cardinality sorting is a method of sorting single logical keywords by means of multi-keyword sorting. The so-called multi-keyword sorting is to have multiple keywords with different priorities. For example, if the scores of the two people are the same, the higher the language is in the front and the higher in the Chinese language, the higher the mathematics is in the front. . . If the numbers are sorted, the ones, tens, and hundreds are the keywords of different priorities. If the sort is to be sorted, the ones, tens, and hundreds are incremented at a time. The cardinality sorting is achieved by multiple allocations and collections, and the keywords with low priority are assigned and collected first.

``````Public  class  RadixSort {
Public  static  void  radixSort ( int [] arr ) {
if (arr ==  null  && arr . length ==  0 )
return ;
Int maxBit = getMaxBit(arr);
For ( int i = 1 ; i <= maxBit; i ++ ) {
List< List< Integer > > buf = distribute(arr, i); // Assign
collecte(arr, buf); // Collection
}
}
public static List< List< Integer > > distribute ( int [] arr , int iBit ) {
List< List< Integer > > buf = new ArrayList< List< Integer > > ();
for ( int j = 0 ; j
< 10 ; j ++ ) {
}
For ( int i = 0 ; i < arr . length; i ++ ) {
Buf . get(getNBit(arr[i], iBit)) . add(arr[i]);
}
Return buf;
}
public static void collecte ( int [] arr , List< List< Integer > > buf ) {
int k = 0 ;
for ( List< Integer > bucket : buf) {
for ( int ele : bucket) {
Arr[k ++ ] = ele;
}
}
}
public static int getMaxBit ( int [] arr ) {
int max = Integer . MIN_VALUE ;
for ( int ele : arr) {
int len = (ele + " " ) . length();
if (len > max)
Max = len;
}
public static int getNBit ( int x , int n ) {
String sx = x +  " " ;
if (sx . length() < n)
return  0 ;
else
return sx . charAt(sx . length() - n) -  ' 0 ' ;
}
}
``````

## Core Java

1. What are primitive types in Java ? byte, short, int, long, float, double, char, boolean… 2. What are tokens? Name the 5 types of tokens available in Java with an example…

## C Programming

1. Wap to check if the given number is armstrong number or not. #include<stdio.h> #include<conio.h> void main(){ int a,t,l,sum=0; printf(“\nPlease enter your number\n”); scanf(“%d”,&a); t=a;…

## Core Java

1. Wap to print Fibonnaci series eg 1 1 2 3 5 8 …. up to a given number 2. Wap to check if given…

## Hackerearth-General Programming

1. Challenge: Solve Me First Complete the function solveMeFirst to compute the sum of two integers. Function prototype: int solveMeFirst(int a, int b); where, a is the…

## Hackerearth-Algorithm

1. Challenge: Quicksort 1 – Partition The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with a running…