Its not just for interview, to boost your confidence as a developer it is important to practice problem-solving question that will definitely help you to familiar with Java.
Solving programming questions helps improve your problem-solving abilities. You'll learn to analyze problems, break them down into smaller steps, and devise efficient solutions.Solving programming questions provides valuable learning experiences, hones your programming skills, and prepares you for various coding challenges, including technical interview. It is an essential practice for any programmer seeking to improve their abilities and succeed in the field.
Here is a list of 50 Java coding interview questions suitable for candidates with 3+ years of experience:
1. Write a program to find the maximum element in an array.
package com.tech.eyes.world4u;
public class MaximumElementInArray {
public static int findMaximum(int[] arr) {
if (arr.length == 0) {
return -1; // Return -1 for empty array
}
int maximum = arr[0]; // Assume the first element is the maximum
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maximum) {
maximum = arr[i];
}
}
return maximum;
}
public static void main(String[] args) {
int[] array = { 3, 8, 2, 10, 5 };
int maximumElement = findMaximum(array);
System.out.println("The maximum element in the array is: " + maximumElement);
}
}
Output:
The maximum element in the array is: 12
In this Java program, the findMaximum method takes an integer array (arr) as input and initializes the maximum variable with the first element of the array. Then, it iterates over each element in the array, starting from the second element, and compares it with the current maximum. If an element is found to be greater than the current maximum, it replaces the maximum value with the new element. Finally, the method returns the maximum element.
In the main method, an integer array [3, 8, 2, 10, 5] is created, and the findMaximum method is called to find the maximum element in the array. The result is then printed as output using System.out.println().
2. Write a program to reverse a string.
package com.tech.eyes.world4u;
public class StringReversal {
public static String reverseString(String input) {
if (input == null || input.isEmpty()) {
return input;
}
char[] characters = input.toCharArray();
int start = 0;
int end = characters.length - 1;
while (start < end) {
char temp = characters[start];
characters[start] = characters[end];
characters[end] = temp;
start++;
end--;
}
return new String(characters);
}
public static void main(String[] args) {
String inputString = "Hello, World!";
String reversedString = reverseString(inputString);
System.out.println("Reversed string: " + reversedString);
}
}
Output:
Reversed string: !dlroW ,olleH
In this Java program, the reverseString method takes a string (input) as input. It checks if the input is null or empty and returns it as is if true. Otherwise, it converts the string into a character array for in-place manipulation.
The method uses two pointers (start and end) to swap characters from the beginning and end of the array until they meet in the middle. The swapping is performed using a temporary variable.
After the characters are reversed, a new string is created from the reversed character array using the String constructor. The reversed string is then returned.
In the main method, a string "Hello, World!" is passed to the reverseString method. The reversed string is stored in the reversedString variable and printed as output using System.out.println().
The time and space complexity of the program are as follows:
Time Complexity:
The time complexity of the program is O(n), where n is the length of the input string. This is because the program iterates through each character in the string once in the reverseString method. The swapping of characters within the while loop occurs for half of the string length, resulting in a linear time complexity.
Space Complexity:
The space complexity of the program is O(n) as well. It is due to the creation of a character array (characters) to store the characters of the input string. The size of the character array is proportional to the length of the input string. Additionally, the space required to store the reversed string using the new String(characters) constructor is also proportional to the length of the input string.
In summary, the program has a linear time complexity of O(n) and a linear space complexity of O(n), where n is the length of the input string.
3. Write a program to check if a string is a palindrome.
package com.tech.eyes.world4u;
public class PalindromeChecker {
public static boolean isPalindrome(String input) {
if (input == null || input.isEmpty()) {
return true;
}
int start = 0;
int end = input.length() - 1;
while (start < end) {
if (input.charAt(start) != input.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
public static void main(String[] args) {
String inputString = "radar";
boolean isPalindrome = isPalindrome(inputString);
System.out.println("Is the string a palindrome? " + isPalindrome);
}
}
Output:
In this Java program, the isPalindrome method takes a string (input) as input and checks if it is a palindrome. It first handles the cases where the input is null or empty by returning true since an empty string or a single character is considered a palindrome.
The method uses two pointers (start and end) to compare characters from the beginning and end of the string. If the characters are not equal, it immediately returns false indicating that the string is not a palindrome. The pointers move towards the center of the string until they meet or cross each other.
After the loop completes without finding any mismatches, the method returns true indicating that the string is a palindrome.
In the main method, a string "radar" is passed to the isPalindrome method. The result is stored in the isPalindrome variable and printed as output using System.out.println().
Time Complexity:
The time complexity of the program is O(n), where n is the length of the input string. This is because the program iterates through half of the string, comparing characters from both ends. In the worst case, it checks all the characters once, resulting in linear time complexity.
Space Complexity:
The space complexity of the program is O(1), as it does not require any additional data structures that grow with the size of the input. The space usage remains constant regardless of the length of the input string.
In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the length of the input string.
4. Write a program to find the factorial of a number.
package com.tech.eyes.world4u;
public class FactorialCalculator {
public static long factorial(int n) {
if (n < 0) {
throw new IllegalArgumentException("Input cannot be negative");
}
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
public static void main(String[] args) {
int number = 5;
long factorialResult = factorial(number);
System.out.println("Factorial of " + number + " is: " + factorialResult);
}
}
Output:
Factorial of 5 is: 120
In this Java program, the factorial method takes an integer n as input and calculates its factorial. It first checks if the input is negative and throws an IllegalArgumentException if it is, as factorial is defined only for non-negative integers.
The method initializes a variable result to 1. It then iterates from 2 up to n, multiplying each number to the result. The final result value is the factorial of the input number.
In the main method, the program calculates the factorial of the number 5 using the factorial method. The result is stored in the factorialResult variable and printed as output using System.out.println().
Time Complexity:
The time complexity of the program is O(n), where n is the input number. This is because the program iterates through the numbers from 2 to n in the for loop, performing a constant-time multiplication operation for each iteration. As the loop runs n - 2 times, the time complexity is linear with respect to n.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the input number.
In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the input number.
5. Write a program to check if a number is prime.
package com.tech.eyes.world4u;
public class PrimeChecker {
public static boolean isPrime(int number) {
if (number <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int number = 37;
boolean isPrime = isPrime(number);
System.out.println("Is " + number + " a prime number? " + isPrime);
}
}
Output:
Is 37 a prime number? true
In this Java program, the isPrime method takes an integer number as input and checks if it is a prime number. It first handles the cases where the number is less than or equal to 1, returning false as prime numbers are defined to be greater than 1.
The method uses a for loop to iterate from 2 up to the square root of the number. It checks if the number is divisible by any integer in this range. If it is, the method immediately returns false since a divisor other than 1 and the number itself is found.
If no divisors are found within the loop, the method returns true indicating that the number is prime.
In the main method, the program checks if the number 37 is prime by calling the isPrime method. The result is stored in the isPrime variable and printed as output using System.out.println().
Time Complexity:
The time complexity of the program is O(sqrt(n)), where n is the given number. This is because the program iterates up to the square root of the number in the for loop. The number of iterations in the loop is proportional to the square root of the number, resulting in a square root time complexity.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the input number.
In summary, the program has a time complexity of O(sqrt(n)) and a space complexity of O(1), where n is the given number.
6. Write a program to find the Fibonacci series up to a given number.
package com.tech.eyes.world4u;
public class FibonacciSeries {
public static void printFibonacciSeries(int limit) {
if (limit < 1) {
return;
}
long first = 0;
long second = 1;
long next;
System.out.print("Fibonacci Series up to " + limit + ": " + first + " " + second);
while ((next = first + second) <= limit) {
System.out.print(" " + next);
first = second;
second = next;
}
System.out.println();
}
public static void main(String[] args) {
int limit = 100;
printFibonacciSeries(limit);
}
}
Output:
Fibonacci Series up to 100: 0 1 1 2 3 5 8 13 21 34 55 89
In this Java program, the printFibonacciSeries method takes an integer limit as input and generates the Fibonacci series up to that limit. It first handles the case where the limit is less than 1 by simply returning from the method.
The method initializes three variables: first (initialized to 0), second (initialized to 1), and next. It then prints the initial values of first and second as the start of the Fibonacci series.
Inside the while loop, the next Fibonacci number (next) is calculated by summing the previous two numbers (first and second). If the next number is less than or equal to the limit, it is printed, and the values of first and second are updated for the next iteration.
The while loop continues until the next Fibonacci number exceeds the given limit. Finally, a newline is printed to separate the output.
In the main method, the program generates the Fibonacci series up to the limit of 100 by calling the printFibonacciSeries method.
Time Complexity:
The time complexity of the program is O(log n), where n is the given limit. This is because the number of Fibonacci numbers generated up to the limit is proportional to the logarithm of the limit. The calculation of each Fibonacci number takes constant time.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the input limit.
In summary, the program has a time complexity of O(log n) and a space complexity of O(1), where n is the given limit.
7. Write a program to find the duplicate elements in an array.
package com.tech.eyes.world4u;
import java.util.HashSet;
public class DuplicateFinder {
public static void findDuplicates(int[] arr) {
if (arr.length < 2) {
return;
}
HashSet uniqueElements = new HashSet<>();
HashSet duplicateElements = new HashSet<>();
for (int num : arr) {
if (!uniqueElements.add(num)) {
duplicateElements.add(num);
}
}
System.out.println("Duplicate elements in the array: " + duplicateElements);
}
public static void main(String[] args) {
int[] array = { 3, 7, 2, 7, 3, 9, 1, 2, 1, 6 };
findDuplicates(array);
}
}
Output:
Duplicate elements in the array: [1, 2, 3, 7]
In this Java program, the findDuplicates method takes an integer array arr as input and finds the duplicate elements in it. It first checks if the length of the array is less than 2, in which case there cannot be any duplicates, so it returns early.
The method uses two HashSet data structures: uniqueElements and duplicateElements. The uniqueElements set is used to keep track of unique elements encountered so far. The duplicateElements set is used to store the duplicate elements found.
The program iterates through each element in the array. For each element, it attempts to add it to the uniqueElements set using the add method. If the element is already present in the set (i.e., it returns false), it means it's a duplicate, and the element is added to the duplicateElements set.
Finally, the program prints the duplicate elements using System.out.println().
In the main method, an integer array [3, 7, 2, 7, 3, 9, 1, 2, 1, 6] is created, and the findDuplicates method is called to find the duplicate elements in the array.
Time Complexity:
The time complexity of the program is O(n), where n is the length of the input array. The program iterates through each element in the array once, performing constant-time operations such as set lookups and insertions.
Space Complexity:
The space complexity of the program is O(k), where k is the number of duplicate elements in the array. The program uses two HashSet data structures: uniqueElements and duplicateElements. The space required by these sets is proportional to the number of duplicate elements found in the array.
In summary, the program has a linear time complexity of O(n) and a linear space complexity of O(k), where n is the length of the input array and k is the number of duplicate elements.
8. Write a program to sort an array in ascending order.
package com.tech.eyes.world4u;
public class ArraySorter {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were swapped in the inner loop, the array is already sorted
if (!swapped) {
break;
}
}
}
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = { 7, 2, 1, 6, 8, 5, 3, 4 };
System.out.println("Array before sorting:");
printArray(array);
bubbleSort(array);
System.out.println("Array after sorting in ascending order:");
printArray(array);
}
}
Output:
Array before sorting:
7 2 1 6 8 5 3 4
Array after sorting in ascending order:
1 2 3 4 5 6 7 8
In this Java program, the bubbleSort method takes an integer array arr as input and sorts it in ascending order using the bubble sort algorithm. The method iterates through the array multiple times, comparing adjacent elements and swapping them if they are in the wrong order.
The program uses two nested for loops. The outer loop runs from i = 0 to n - 1, where n is the length of the array. The inner loop runs from j = 0 to n - i - 1. In each iteration of the inner loop, adjacent elements are compared, and if they are out of order, they are swapped.
The inner loop continues until the end of the array, and after each iteration of the outer loop, the largest element moves to the end of the array. If no swaps are made in the inner loop, it means the array is already sorted, and the outer loop can be terminated early.
The printArray method is used to print the elements of the array.
In the main method, an integer array [7, 2, 1, 6, 8, 5, 3, 4] is created. The array is printed before sorting, then the bubbleSort method is called to sort the array. Finally, the sorted array is printed.
Time Complexity:
The time complexity of the program is O(n^2), where n is the length of the input array. This is because the program uses a nested loop structure, and in the worst case, it needs to iterate through the array multiple times.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the size of the input array.
In summary, the program has a quadratic time complexity of O(n^2) and constant space complexity of O(1), where n is the length of the input array.
9. Write a program to implement a binary search algorithm.
package com.tech.eyes.world4u;
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Element not found
}
public static void main(String[] args) {
int[] array = { 1, 3, 5, 7, 9, 11, 13 };
int target = 9;
int index = binarySearch(array, target);
if (index != -1) {
System.out.println("Element " + target + " found at index " + index);
} else {
System.out.println("Element " + target + " not found in the array");
}
}
}
Output:
Element 9 found at index 4
In this Java program, the binarySearch method takes a sorted integer array arr and a target value as input. It performs a binary search to find the index of the target element in the array. If the element is found, it returns the index. Otherwise, it returns -1 to indicate that the element is not present.
The binary search algorithm maintains two pointers, left and right, initially set to the first and last indices of the array, respectively. It repeatedly divides the search space in half by calculating the middle index (mid). It compares the element at the middle index with the target value.
If the element at mid is equal to the target, the method returns the index of mid. If the element is less than the target, the search range is narrowed to the right half of the array by updating left to mid + 1. If the element is greater than the target, the search range is narrowed to the left half of the array by updating right to mid - 1.
The search continues until the search range is exhausted (left > right), at which point the element is not found, and -1 is returned.
In the main method, an integer array [1, 3, 5, 7, 9, 11, 13] is created and the target value 9 is searched using the binarySearch method. The result is stored in the index variable, and the output is printed accordingly using System.out.println().
Time Complexity:
The time complexity of the binary search algorithm is O(log n), where n is the size of the sorted array. This is because the algorithm halves the search space in each iteration, leading to a logarithmic time complexity.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the size of the input array.
In summary, the program has a logarithmic time complexity of O(log n) and constant space complexity of O(1), where n is the size of the sorted array.
10. Write a program to find the second largest element in an array.
package com.tech.eyes.world4u;
public class SecondLargestElement {
public static int findSecondLargest(int[] arr) {
int n = arr.length;
if (n < 2) {
System.out.println("Array should have at least two elements.");
return -1;
}
int largest = Integer.MIN_VALUE;
int secondLargest = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
} else if (arr[i] > secondLargest && arr[i] != largest) {
secondLargest = arr[i];
}
}
return secondLargest;
}
public static void main(String[] args) {
int[] array = { 9, 5, 2, 7, 12, 6, 8 };
int secondLargest = findSecondLargest(array);
if (secondLargest != -1) {
System.out.println("The second largest element in the array is: " + secondLargest);
}
}
}
Output:
The second largest element in the array is: 9
In this Java program, the findSecondLargest method takes an integer array arr as input and finds the second largest element in the array. The method initializes two variables, largest and secondLargest, to the minimum integer value.
The method then iterates through the array, comparing each element with the current largest and second largest values. If an element is greater than the current largest, it updates the largest and second largest accordingly. If an element is greater than the current second largest but not equal to the largest element, it updates the second largest value.
Finally, the method returns the second largest element found in the array.
Time Complexity:
The time complexity of the program is O(n), where n is the size of the array. This is because the program iterates through the array once to find the second largest element. The time complexity increases linearly with the size of the input array.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the size of the input array.
In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the size of the array.
11. Write a program to remove duplicates from an ArrayList.
package com.tech.eyes.world4u;
import java.util.ArrayList;
import java.util.HashSet;
public class RemoveDuplicates {
public static void removeDuplicates(ArrayList list) {
HashSet uniqueElements = new HashSet<>() ;
ArrayList result = new ArrayList<>() ;
for (Integer num : list) {
if (uniqueElements.add(num)) {
result.add(num);
}
}
list.clear();
list.addAll(result);
}
public static void main(String[] args) {
ArrayList list = new ArrayList<>() ;
list.add(3);
list.add(7);
list.add(2);
list.add(7);
list.add(3);
list.add(9);
list.add(1);
list.add(2);
list.add(1);
list.add(6);
System.out.println("ArrayList before removing duplicates:");
System.out.println(list);
removeDuplicates(list);
System.out.println("ArrayList after removing duplicates:");
System.out.println(list);
}
}
Output:
ArrayList before removing duplicates:
[3, 7, 2, 7, 3, 9, 1, 2, 1, 6]
ArrayList after removing duplicates:
[3, 7, 2, 9, 1, 6]
In this Java program, the removeDuplicates method takes an ArrayList of integers as input and removes duplicates from it. It uses a HashSet to keep track of unique elements encountered so far. It also creates a new ArrayList called result to store the elements without duplicates.
The method iterates through each element in the input ArrayList. For each element, it attempts to add it to the HashSet. If the element is not already present (i.e., the add operation returns true), it adds the element to the result ArrayList.
After processing all the elements, the method clears the input ArrayList and adds all the elements from the result ArrayList back into it, effectively removing the duplicates.
In the main method, an ArrayList is created and initialized with some elements containing duplicates. The original ArrayList is printed before removing duplicates. Then, the removeDuplicates method is called to remove the duplicates from the ArrayList. Finally, the modified ArrayList is printed after removing duplicates.
Time Complexity:
The time complexity of the program is O(n), where n is the size of the input ArrayList. This is because the program iterates through each element in the ArrayList once, performing constant-time operations such as set lookups and insertions.
Space Complexity:
The space complexity of the program is O(k), where k is the number of unique elements in the input ArrayList. The program uses a HashSet to store the unique elements encountered, and the space required by the set is proportional to the number of unique elements.
In summary, the program has a linear time complexity of O(n) and linear space complexity of O(k), where n is the size of the input ArrayList and k is the number of unique elements.
12. Write a program to reverse a linked list.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public void reverse() {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
public void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next = new Node(3);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(5);
System.out.println("Linked List before reversing:");
list.printList();
list.reverse();
System.out.println("Linked List after reversing:");
list.printList();
}
}
Output:
Linked List before reversing:
1 2 3 4 5
Linked List after reversing:
5 4 3 2 1
In this Java program, we define a Node class representing a single node of the linked list. The LinkedList class contains the logic for reversing the linked list. It has a reverse method that reverses the order of the nodes in the linked list.
The reverse method uses three pointers: prev, current, and next. Initially, prev is set to null, current is set to the head of the linked list, and next is set to null. The method iterates through the linked list, changing the next pointer of each node to its previous node. This effectively reverses the order of the nodes. Finally, the head of the linked list is updated to the last node of the original linked list.
The printList method is used to print the elements of the linked list.
In the main method, we create a linked list with nodes containing data values 1, 2, 3, 4, and 5. We print the linked list before reversing it, then call the reverse method to reverse the linked list. Finally, we print the reversed linked list.
Time Complexity:
The time complexity of the program is O(n), where n is the number of nodes in the linked list. This is because the program iterates through each node of the linked list once, performing constant-time operations such as pointer assignments.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of extra space. The space required for the program remains the same, regardless of the size of the linked list.
In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the number of nodes in the linked list.
13. Write a program to implement a stack using an array.
package com.tech.eyes.world4u;
public class Stack {
private int maxSize;
private int top;
private int[] stackArray;
public Stack(int size) {
maxSize = size;
top = -1;
stackArray = new int[maxSize];
}
public void push(int value) {
if (isFull()) {
System.out.println("Stack is full. Cannot push element " + value);
return;
}
stackArray[++top] = value;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty. Cannot pop element.");
return -1;
}
return stackArray[top--];
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty. Cannot peek element.");
return -1;
}
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);
System.out.println("Stack elements:");
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
Output:
Stack elements:
50
40
30
20
10
Time Complexity:
The time complexity of the push, pop, and peek operations in the stack implemented using an array is O(1). These operations involve accessing or modifying the top element of the stack, which can be done in constant time.
Space Complexity:
The space complexity of the program is O(n), where n is the maximum size of the stack. This is because the program uses an array of size maxSize to store the stack elements.
In summary, the program has constant time complexity of O(1) for push, pop, and peek operations, and linear space complexity of O(n) where n is the maximum size of the stack.
14. Write a program to find the missing number in an array.
package com.tech.eyes.world4u;
public class MissingNumber {
public static int findMissingNumber(int[] arr) {
int n = arr.length;
int expectedSum = (n + 1) * (n + 2) / 2;
int actualSum = 0;
for (int i = 0; i < n; i++) {
actualSum += arr[i];
}
return expectedSum - actualSum;
}
public static void main(String[] args) {
int[] array = { 1, 2, 4, 5, 6 };
int missingNumber = findMissingNumber(array);
System.out.println("Missing number: " + missingNumber);
}
}
Output:
Missing number: 3
In this Java program, the findMissingNumber method takes an integer array arr as input and finds the missing number in the array. The method calculates the expected sum of numbers from 1 to n+1 (where n is the length of the array) using the formula (n+1) * (n+2) / 2. It then calculates the actual sum of the numbers in the array by iterating through the array and summing up all the elements. Finally, it returns the difference between the expected sum and the actual sum, which represents the missing number.
In the main method, an integer array [1, 2, 4, 5, 6] is created, and the findMissingNumber method is called to find the missing number. The missing number is then printed using System.out.println().
Time Complexity:
The time complexity of the program is O(n), where n is the length of the input array. This is because the program iterates through the array once to calculate the actual sum. The time complexity increases linearly with the size of the input array.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the size of the input array.
In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the length of the array.
15. Write a program to check if two strings are anagrams.
package com.tech.eyes.world4u;
import java.util.Arrays;
public class AnagramCheck {
public static boolean areAnagrams(String str1, String str2) {
// Removing whitespaces and converting to lowercase
str1 = str1.replaceAll("\\s", "").toLowerCase();
str2 = str2.replaceAll("\\s", "").toLowerCase();
// If lengths are different, strings cannot be anagrams
if (str1.length() != str2.length()) {
return false;
}
// Converting strings to char arrays and sorting them
char[] charArr1 = str1.toCharArray();
char[] charArr2 = str2.toCharArray();
Arrays.sort(charArr1);
Arrays.sort(charArr2);
// Checking if sorted arrays are equal
return Arrays.equals(charArr1, charArr2);
}
public static void main(String[] args) {
String str1 = "listen";
String str2 = "silent";
if (areAnagrams(str1, str2)) {
System.out.println(str1 + " and " + str2 + " are anagrams.");
} else {
System.out.println(str1 + " and " + str2 + " are not anagrams.");
}
}
}
Output:
listen and silent are anagrams.
In this Java program, the areAnagrams method takes two strings, str1 and str2, as input and checks if they are anagrams of each other.
First, the method removes whitespaces from the strings and converts them to lowercase using the replaceAll and toLowerCase methods.
Next, the method compares the lengths of the two strings. If they are not equal, the strings cannot be anagrams, so the method returns false.
Then, the strings are converted to character arrays using the toCharArray method. The character arrays are sorted using the Arrays.sort method.
Finally, the method compares the sorted character arrays using the Arrays.equals method. If the sorted arrays are equal, the strings are anagrams, and the method returns true. Otherwise, it returns false.
Time Complexity:
The time complexity of the program is O(n log n), where n is the length of the longer input string. This is because the program sorts the character arrays, which has a time complexity of O(n log n), where n is the length of the character array.
Space Complexity:
The space complexity of the program is O(n), where n is the length of the longer input string. This is because the program creates character arrays to store the modified strings, and the space required is proportional to the length of the strings.
In summary, the program has a time complexity of O(n log n) and a space complexity of O(n), where n is the length of the longer input string.
16. Write a program to implement a queue using two stacks.
package com.tech.eyes.world4u;
import java.util.Stack;
public class QueueUsingStack {
private Stack stack1;
private Stack stack2;
public QueueUsingStack() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void enqueue(int value) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
stack1.push(value);
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue element.");
return -1;
}
return stack1.pop();
}
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot peek element.");
return -1;
}
return stack1.peek();
}
public boolean isEmpty() {
return stack1.isEmpty();
}
public static void main(String[] args) {
QueueUsingStack queue = new QueueUsingStack();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
System.out.println("Dequeued element: " + queue.dequeue());
System.out.println("Peeked element: " + queue.peek());
queue.enqueue(40);
System.out.println("Dequeued element: " + queue.dequeue());
System.out.println("Dequeued element: " + queue.dequeue());
System.out.println("Is queue empty? " + queue.isEmpty());
}
}
Output:
Dequeued element: 10
Peeked element: 20
Dequeued element: 20
Dequeued element: 30
Is queue empty? false
In this Java program, the QueueUsingStack class represents a queue implemented using two stacks. It has two private member variables stack1 and stack2, which are stacks used for enqueueing and dequeueing elements.
The QueueUsingStack class provides the following methods:
- enqueue(value): Adds an element to the queue. It transfers all the elements from stack1 to stack2, pushes the new element to stack1, and then transfers all the elements back to stack1.
- dequeue(): Removes and returns the front element from the queue. If the queue is empty, it displays an error message and returns -1.
- peek(): Returns the front element of the queue without removing it. If the queue is empty, it displays an error message and returns -1.
- isEmpty(): Checks if the queue is empty and returns a boolean value.
In the main method, a QueueUsingStack object is created. Three elements (10, 20, 30) are enqueued using the enqueue method. Then, an element is dequeued and its value is printed using the dequeue method. The front element is peeked using the peek method. Another element (40) is enqueued, and two elements are dequeued and printed. Finally, the isEmpty method is used to check if the queue is empty.
Time Complexity
The time complexity for enqueue and dequeue operations in this implementation is O(n), where n is the number of elements in the queue. The enqueue operation involves transferring elements between stacks, which takes linear time. The dequeue operation involves popping an element from stack1, which takes constant time.
Space Complexity
The space complexity of the program is O(n), where n is the number of elements in the queue. This is because the program uses two stacks to store the elements.
17. Write a program to find the common elements between two arrays.
package com.tech.eyes.world4u;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class CommonElements {
public static List findCommonElements(int[] array1, int[] array2) {
Set set = new HashSet<>();
List commonElements = new ArrayList<>();
for (int num : array1) {
set.add(num);
}
for (int num : array2) {
if (set.contains(num)) {
commonElements.add(num);
}
}
return commonElements;
}
public static void main(String[] args) {
int[] array1 = { 1, 2, 3, 4, 5 };
int[] array2 = { 4, 5, 6, 7, 8 };
List commonElements = findCommonElements(array1, array2);
System.out.println("Common elements:");
for (int num : commonElements) {
System.out.println(num);
}
}
}
Output:
Common elements:
4
5
In this Java program, the findCommonElements method takes two integer arrays, array1 and array2, as input and finds the common elements between them. It uses a HashSet to store the elements of array1. Then, it iterates through array2 and checks if each element exists in the HashSet. If it does, the element is added to the commonElements list.
In the main method, two integer arrays, array1 and array2, are created with some elements. The findCommonElements method is called to find the common elements between the arrays. The common elements are then printed using System.out.println().
Time Complexity:
The time complexity of the program is O(m + n), where m is the length of array1 and n is the length of array2. The program iterates through both arrays once to create the HashSet and find the common elements. The time complexity increases linearly with the sizes of the input arrays.
Space Complexity:
The space complexity of the program is O(m), where m is the length of array1. This is because the program uses a HashSet to store the elements of array1. The space required is proportional to the size of array1.
In summary, the program has a time complexity of O(m + n) and a space complexity of O(m), where m is the length of array1 and n is the length of array2.
18. Write a program to find the longest palindrome in a given string.
package com.tech.eyes.world4u;
public class LongestPalindrome {
public static String findLongestPalindrome(String str) {
if (str == null || str.length() < 2) {
return str;
}
int maxLength = 1;
int start = 0;
for (int i = 0; i < str.length(); i++) {
int len1 = expandFromCenter(str, i, i); // odd-length palindromes
int len2 = expandFromCenter(str, i, i + 1); // even-length palindromes
int currentLength = Math.max(len1, len2);
if (currentLength > maxLength) {
maxLength = currentLength;
start = i - (currentLength - 1) / 2;
}
}
return str.substring(start, start + maxLength);
}
private static int expandFromCenter(String str, int left, int right) {
int length = 0;
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
length = right - left + 1;
left--;
right++;
}
return length;
}
public static void main(String[] args) {
String input = "babad";
String longestPalindrome = findLongestPalindrome(input);
System.out.println("Longest Palindrome: " + longestPalindrome);
}
}
Output:
Longest Palindrome: bab
In this Java program, the findLongestPalindrome method takes a string str as input and finds the longest palindrome within it. The program uses the concept of expanding around centers to find palindromes. It iterates through each character in the string and considers it as a center. It expands from the center character outward in both directions to find the longest palindrome. The method expandFromCenter is used to perform the expansion and return the length of the palindrome. The start and end indices of the longest palindrome are tracked, and the substring is extracted using the substring method.
In the main method, a string "babad" is provided as input, and the findLongestPalindrome method is called to find the longest palindrome within it. The longest palindrome is then printed using System.out.println().
Time Complexity:
The time complexity of the program is O(n^2), where n is the length of the input string. This is because for each character in the string, the program expands around it in both directions to find palindromes. In the worst case, when all characters are the same, the program will have to expand from the center for each character, resulting in n^2 iterations.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of extra space. The space required for the program remains the same, regardless of the size of the input string.
In summary, the program has a time complexity of O(n^2) and a constant space complexity of O(1), where n is the length of the input string.
19. Write a program to check if a number is a perfect square.
package com.tech.eyes.world4u;
public class PerfectSquareChecker {
public static boolean isPerfectSquare(int num) {
if (num < 0) {
return false;
}
if (num == 0 || num == 1) {
return true;
}
long start = 1;
long end = num;
while (start <= end) {
long mid = start + (end - start) / 2;
long square = mid * mid;
if (square == num) {
return true;
} else if (square < num) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return false;
}
public static void main(String[] args) {
int number1 = 16;
int number2 = 25;
int number3 = 14;
System.out.println(number1 + " is a perfect square? " + isPerfectSquare(number1));
System.out.println(number2 + " is a perfect square? " + isPerfectSquare(number2));
System.out.println(number3 + " is a perfect square? " + isPerfectSquare(number3));
}
}
Output:
16 is a perfect square? true
25 is a perfect square? true
14 is a perfect square? false
In this Java program, the isPerfectSquare method takes an integer num as input and checks if it is a perfect square. The program uses a binary search approach to find the square root of the number. It initializes start as 1 and end as the given number. It calculates the middle value, squares it, and compares it with the given number. If the square is equal to the given number, it returns true. If the square is less than the given number, it updates the start value to mid + 1 to search in the higher range. If the square is greater than the given number, it updates the end value to mid - 1 to search in the lower range. The loop continues until the start value is less than or equal to the end value. If the loop finishes without finding a perfect square, it returns false.
In the main method, three numbers (number1, number2, number3) are checked using the isPerfectSquare method, and the results are printed using System.out.println().
Time Complexity:
The time complexity of the program is O(log n), where n is the given number. This is because the program uses a binary search approach to find the square root of the number. It repeatedly halves the search range until it finds the square root or exhausts the range.
Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of extra space. The space required for the program remains the same, regardless of the size of the input number.
In summary, the program has a time complexity of O(log n) and a constant space complexity of O(1), where n is the given number.
20. Write a program to calculate the sum of digits of a number.
package com.tech.eyes.world4u;
public class SumOfDigits {
public static int calculateSumOfDigits(int number) {
int sum = 0;
while (number != 0) {
int digit = number % 10;
sum += digit;
number /= 10;
}
return sum;
}
public static void main(String[] args) {
int number = 12345;
int sum = calculateSumOfDigits(number);
System.out.println("Sum of digits of " + number + ": " + sum);
}
}
Output:
Sum of digits of 12345: 15
In this Java program, the calculateSumOfDigits method takes an integer number as input and calculates the sum of its digits. The program uses a while loop to iterate until the number becomes 0. In each iteration, the last digit of the number is obtained by using the modulus operator %. This digit is added to the sum variable. Then, the number is divided by 10 to remove the last digit. The loop continues until all digits have been processed. Finally, the sum of the digits is returned.
In the main method, an integer number is set to 12345. The calculateSumOfDigits method is called with this number, and the sum is stored in the sum variable. The sum of the digits is then printed using System.out.println().
21. Write a program to find the intersection of two linked lists.
package com.tech.eyes.world4u;
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class IntersectionLinkedList {
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode currA = headA;
ListNode currB = headB;
while (currA != currB) {
currA = (currA == null) ? headB : currA.next;
currB = (currB == null) ? headA : currB.next;
}
return currA;
}
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
ListNode headA = node1;
headA.next = node2;
headA.next.next = node3;
headA.next.next.next = node4;
ListNode headB = node5;
headB.next = node3;
ListNode intersectionNode = getIntersectionNode(headA, headB);
System.out.println("Intersection Node: " + intersectionNode.val);
}
}
Output:
Intersection Node: 3
In this Java program, there is a ListNode class representing a node in a linked list. Each node has an integer value and a next reference pointing to the next node in the list.
The getIntersectionNode method takes two linked lists headA and headB as input and finds the intersection node between them. It iterates through both lists simultaneously, moving each pointer forward. When one pointer reaches the end of a list, it is redirected to the head of the other list. If there is an intersection, both pointers will eventually meet at the intersection node. If there is no intersection, both pointers will reach the end of the lists, i.e., null.
In the main method, two linked lists are created with nodes node1, node2, node3, node4, and node5. headA and headB are assigned the respective heads of the lists. Node node3 is the intersection point of both lists. The getIntersectionNode method is called to find the intersection node, and the value of the intersection node is printed using System.out.println().
22. Write a program to count the occurrences of each element in an array.
package com.tech.eyes.world4u;
import java.util.HashMap;
import java.util.Map;
public class ElementOccurrences {
public static void countElementOccurrences(int[] arr) {
Map entry : occurrences.entrySet()) {
System.out.println("Element " + entry.getKey() + " occurs " + entry.getValue() + " times.");
}
}
public static void main(String[] args) {
int[] arr = {2, 5, 2, 7, 4, 5, 7, 2, 4, 4, 5};
countElementOccurrences(arr);
}
}
Output:
Element 2 occurs 3 times.
Element 4 occurs 3 times.
Element 5 occurs 3 times.
Element 7 occurs 2 times.
In this Java program, the countElementOccurrences method takes an array arr as input and counts the occurrences of each element in the array. It uses a HashMap to store the elements as keys and their respective occurrences as values. The program iterates through the array and checks if the element already exists in the occurrences map. If it exists, the occurrence count is incremented. If it doesn't exist, a new entry is added with an occurrence count of 1. Finally, the program iterates through the occurrences map and prints each element along with its occurrence count.
In the main method, an array arr is initialized with some numbers. The countElementOccurrences method is called with this array, and it counts the occurrences of each element in the array. The occurrences are then printed using System.out.println().
23. Write a program to reverse a sentence word by word.
package com.tech.eyes.world4u;
public class ReverseSentence {
public static String reverseSentence(String sentence) {
String[] words = sentence.split(" ");
StringBuilder reversedSentence = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
reversedSentence.append(words[i]);
if (i > 0) {
reversedSentence.append(" ");
}
}
return reversedSentence.toString();
}
public static void main(String[] args) {
String sentence = "Hello world! How are you?";
String reversedSentence = reverseSentence(sentence);
System.out.println("Original sentence: " + sentence);
System.out.println("Reversed sentence: " + reversedSentence);
}
}
Output:
Original sentence: Hello world! How are you?
Reversed sentence: you? are How world! Hello
In this Java program, the reverseSentence method takes a sentence as input and reverses it word by word. The sentence is split into individual words using the split method, with the delimiter as a space (" "). The program then iterates over the words array from the last index to the first index. Each word is appended to a StringBuilder named reversedSentence, with a space added between words. Finally, the reversedSentence is converted back to a string using the toString method and returned.
In the main method, a sentence "Hello world! How are you?" is given as input. The reverseSentence method is called with this sentence, and the reversed sentence is stored in the reversedSentence variable. The original sentence and the reversed sentence are then printed using System.out.println().
24. Write a program to implement a binary tree and perform an in order traversal.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class BinaryTree {
public static void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.print(root.val + " ");
inOrderTraversal(root.right);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.print("In-order traversal: ");
inOrderTraversal(root);
}
}
Output:
In-order traversal: 4 2 5 1 3
In this Java program, there is a TreeNode class representing a node in a binary tree. Each node has an integer value, and it has references to its left and right child nodes.
The inOrderTraversal method takes a TreeNoderoot as input and performs an in-order traversal of the binary tree. The method uses recursion to traverse the tree in the order: left subtree, current node, right subtree. It first checks if the root is null, and if so, it returns. Then, it recursively calls the inOrderTraversal method on the left subtree, prints the value of the current node, and recursively calls the method on the right subtree.
In the main method, a binary tree is created with nodes and connections. The inOrderTraversal method is called with the root of the tree, and it performs the in-order traversal. The values of the nodes are printed during the traversal using System.out.print().
25. Write a program to find the maximum sum subarray in an array.
package com.tech.eyes.world4u;
public class MaximumSubarraySum {
public static int findMaximumSubarraySum(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int num : nums) {
currentSum = Math.max(num, currentSum + num);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int maxSum = findMaximumSubarraySum(nums);
System.out.println("Maximum sum of a subarray: " + maxSum);
}
}
Output:
Maximum sum of a subarray: 6
In this Java program, the findMaximumSubarraySum method takes an integer array nums as input and finds the maximum sum of a subarray using Kadane's algorithm. The algorithm initializes two variables: maxSum to track the maximum sum found so far (initialized with the minimum possible value) and currentSum to track the sum of the current subarray (initialized with 0). It then iterates through each element in the array, updating currentSum by taking the maximum of the current element or the sum of the current element and the previous currentSum. It also updates maxSum by taking the maximum of the current maxSum and the updated currentSum. Finally, it returns maxSum.
In the main method, an array nums is initialized with values. The findMaximumSubarraySum method is called with this array, and the maximum sum of a subarray is stored in the maxSum variable. The maximum sum is then printed using System.out.println().
26. Write a program to check if a string is a valid parentheses expression.
package com.tech.eyes.world4u;
import java.util.Stack;
public class ValidParentheses {
public static boolean isValid(String s) {
Stack
In this Java program, the isValid method takes a string s as input and checks if it is a valid parentheses expression. It uses a stack to keep track of opening parentheses. It iterates through each character in the string. If the character is an opening parentheses ((, [, or {), it is pushed onto the stack. If the character is a closing parentheses (), ], or }), it is checked if the stack is not empty and the top of the stack corresponds to the matching opening parentheses. If they match, the opening parentheses is popped from the stack. If any other character is encountered or there is a mismatch between the closing and opening parentheses, the expression is considered invalid, and false is returned. After iterating through all characters, it is checked if the stack is empty. If it is empty, the expression is valid; otherwise, it is invalid.
In the main method, several test cases are given as input strings (s1, s2, s3, s4, s5). The isValid method is called with each string, and the result of validity is printed using System.out.println().
The program checks if each input string is a valid parentheses expression and prints the validity result. In this example, s1, s2, and s5 are valid expressions, while s3 and s4 are invalid expressions.
27. Write a program to implement a circular linked list.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedList {
private Node head;
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
head.next = head;
} else {
Node current = head;
while (current.next != head) {
current = current.next;
}
current.next = newNode;
newNode.next = head;
}
}
public void display() {
if (head == null) {
System.out.println("Circular Linked List is empty.");
return;
}
Node current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList circularLinkedList = new CircularLinkedList();
circularLinkedList.insert(1);
circularLinkedList.insert(2);
circularLinkedList.insert(3);
circularLinkedList.insert(4);
System.out.println("Circular Linked List:");
circularLinkedList.display();
}
}
Output:
Circular Linked List:
1 2 3 4
In this Java program, a circular linked list is implemented using the Node class to represent each node in the list. The CircularLinkedList class has methods for insertion and display of the circular linked list.
The insert method is used to insert a new node at the end of the circular linked list. If the list is empty, the new node becomes the head and points to itself. Otherwise, it iterates through the list until it reaches the last node (whose next points to the head), and then inserts the new node.
The display method is used to print the elements of the circular linked list. It starts from the head and traverses the list until it reaches the head again, printing the data of each node.
In the main method, a CircularLinkedList object is created, and some elements (1, 2, 3, and 4) are inserted into the list using the insert method. Finally, the elements of the circular linked list are displayed using the display method.
28. Write a program to find the largest prime factor of a number.
package com.tech.eyes.world4u;
public class LargestPrimeFactor {
public static long findLargestPrimeFactor(long number) {
long largestPrimeFactor = 1;
while (number % 2 == 0) {
largestPrimeFactor = 2;
number /= 2;
}
for (int i = 3; i <= Math.sqrt(number); i += 2) {
while (number % i == 0) {
largestPrimeFactor = i;
number /= i;
}
}
if (number > 2) {
largestPrimeFactor = number;
}
return largestPrimeFactor;
}
public static void main(String[] args) {
long number = 13195;
long largestPrimeFactor = findLargestPrimeFactor(number);
System.out.println("Largest prime factor of " + number + " is: " + largestPrimeFactor);
}
}
Output:
Largest prime factor of 13195 is: 29
In this Java program, the findLargestPrimeFactor method takes a long number as input and finds the largest prime factor of that number. It uses a loop to divide the number by 2 until it is no longer divisible by 2, updating the largestPrimeFactor to 2 each time. Then, it iterates from 3 to the square root of the number, checking if the number is divisible by each odd number.
If it is divisible, it updates the largestPrimeFactor to that divisor and divides the number by that divisor. Finally, if the remaining number is greater than 2, it updates the largestPrimeFactor to that remaining number. The method returns the largestPrimeFactor.
In the main method, a test number (number) is given as input. The findLargestPrimeFactor method is called with this number, and the largest prime factor is stored in the largestPrimeFactor variable. The largest prime factor is then printed using System.out.println().
29. Write a program to check if a binary tree is balanced.
package com.tech.eyes.world4u;
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class BalancedBinaryTree {
public static boolean isBalanced(Node root) {
if (root == null) {
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
return true;
}
return false;
}
public static int getHeight(Node node) {
if (node == null) {
return 0;
}
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
boolean isBalanced = isBalanced(root);
System.out.println("Is the binary tree balanced? " + isBalanced);
}
}
Output:
Is the binary tree balanced? false
In this Java program, a binary tree is represented using the Node class, which has an int data value, and references to the left and right child nodes. The BalancedBinaryTree class has methods to check if a binary tree is balanced and to calculate the height of a node.
The isBalanced method takes a Node root as input and recursively checks if the tree is balanced by comparing the heights of the left and right subtrees. It calls the getHeight method to calculate the height of each node. If the absolute difference between the heights is less than or equal to 1, and both the left and right subtrees are balanced, it returns true. Otherwise, it returns false.
The getHeight method calculates the height of a node by recursively calculating the height of its left and right subtrees. It returns the maximum height between the left and right subtrees plus 1.
In the main method, a binary tree is created with some sample nodes. The isBalanced method is called with the root of the tree, and the result of whether the binary tree is balanced or not is stored in the isBalanced variable. The result is then printed using System.out.println().
30. Write a program to find the intersection of two sorted arrays.
package com.tech.eyes.world4u;
import java.util.ArrayList;
import java.util.List;
public class IntersectionOfArrays {
public static List findIntersection(int[] arr1, int[] arr2) {
List intersection = findIntersection(arr1, arr2);
System.out.println("Intersection of the two arrays: " + intersection);
}
}
Output:
Intersection of the two arrays: [2, 4]
In this Java program, the findIntersection method takes two sorted arrays (arr1 and arr2) as input and finds their intersection. It uses two pointers, i and j, to iterate through the arrays. The method compares the elements at the current positions of the pointers. If the element in arr1 is less than the element in arr2, i is incremented.
If the element in arr1 is greater than the element in arr2, j is incremented. If the elements are equal, the element is added to the intersection list, and both i and j are incremented. This process continues until either array reaches its end.
In the main method, two sorted arrays (arr1 and arr2) are given as input. The findIntersection method is called with these arrays, and the intersection is stored in the intersection list. The intersection of the two arrays is then printed using System.out.println().
31. Write a program to find the minimum element in a rotated sorted array.
package com.tech.eyes.world4u;
public class MinimumInRotatedArray {
public static int findMinimum(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
}
}
return nums[left];
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
int minimum = findMinimum(nums);
System.out.println("Minimum element in the rotated sorted array: " + minimum);
}
}
Output:
Minimum element in the rotated sorted array: 0
In this Java program, the findMinimum method takes a rotated sorted array (nums) as input and finds the minimum element in it. It uses a modified version of the binary search algorithm to perform the search. The method initializes the left pointer to the beginning of the array and the right pointer to the end of the array.
The method repeatedly divides the array into two halves and checks if the mid element is greater than the rightmost element. If it is, it means the minimum element lies in the right half of the array, so the left pointer is moved to mid + 1. If the mid element is less than the rightmost element, it means the minimum element lies in the left half of the array, so the right pointer is moved to mid. This process continues until the left and right pointers converge, indicating that the minimum element has been found.
In the main method, a rotated sorted array (nums) is given as input. The findMinimum method is called with this array, and the minimum element is stored in the minimum variable. The minimum element in the rotated sorted array is then printed using System.out.println().
32. Write a program to check if a string is a valid palindrome ignoring non-alphanumeric characters.
package com.tech.eyes.world4u;
public class ValidPalindrome {
public static boolean isPalindrome(String str) {
// Remove non-alphanumeric characters and convert to lowercase
String processedStr = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
// Check if the processed string is a palindrome
int left = 0;
int right = processedStr.length() - 1;
while (left < right) {
if (processedStr.charAt(left) != processedStr.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
String str = "A man, a plan, a canal: Panama";
boolean isPalindrome = isPalindrome(str);
System.out.println("Is the string a valid palindrome? " + isPalindrome);
}
}
Output:
Is the string a valid palindrome? true
In this Java program, the isPalindrome method takes a string (str) as input and checks if it is a valid palindrome while ignoring non-alphanumeric characters. First, it removes all non-alphanumeric characters from the string using the replaceAll method and regular expression [^a-zA-Z0-9]. Then, it converts the processed string to lowercase.
The method uses two pointers, left and right, to compare characters from the start and end of the processed string. It iterates until the left pointer is less than the right pointer. If the characters at the left and right pointers are not equal, it means the string is not a palindrome and returns false. If all characters are equal, it returns true.
In the main method, a string (str) is given as input. The isPalindrome method is called with this string, and the result of whether the string is a valid palindrome or not is stored in the isPalindrome variable. The result is then printed using System.out.println().
33. Write a program to implement a queue using a linked list.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class Queue {
private Node front;
private Node rear;
public Queue() {
this.front = null;
this.rear = null;
}
public boolean isEmpty() {
return front == null;
}
public void enqueue(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
System.out.println("Enqueued: " + data);
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
int data = front.data;
front = front.next;
if (front == null) {
rear = null;
}
System.out.println("Dequeued: " + data);
return data;
}
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
Node temp = front;
System.out.print("Queue: ");
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
}
public class QueueUsingLinkedList {
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.display();
queue.dequeue();
queue.dequeue();
queue.display();
queue.enqueue(40);
queue.display();
}
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue: 10 20 30
Dequeued: 10
Dequeued: 20
Queue: 30
Enqueued: 40
Queue: 30 40
In this Java program, a linked list is used to implement a queue. The Node class represents each node in the linked list, containing an int data value and a reference to the next node. The Queue class represents the queue and contains methods to enqueue, dequeue, check if the queue is empty, and display the elements of the queue.
The enqueue method adds an element to the rear of the queue by creating a new node and updating the rear pointer accordingly.
The dequeue method removes the element from the front of the queue and updates the front pointer accordingly.
The display method prints the elements of the queue.
In the main method, a Queue object is created, and various operations are performed on the queue, such as enqueueing elements (10, 20, 30), dequeuing elements, and displaying the queue after each operation.
34. Write a program to reverse a number.
package com.tech.eyes.world4u;
public class ReverseNumber {
public static int reverse(int number) {
int reversed = 0;
while (number != 0) {
int digit = number % 10;
reversed = reversed * 10 + digit;
number /= 10;
}
return reversed;
}
public static void main(String[] args) {
int number = 12345;
int reversedNumber = reverse(number);
System.out.println("Original number: " + number);
System.out.println("Reversed number: " + reversedNumber);
}
}
Output:
Original number: 12345
Reversed number: 54321
In this Java program, the reverse method takes an integer (number) as input and reverses the digits of the number. It initializes a variable reversed to 0. It then iteratively extracts the last digit of the number using the modulus operator % and appends it to the reversed variable by multiplying it by 10 and adding the digit. Finally, it divides the number by 10 to discard the last digit. This process continues until the number becomes 0.
In the main method, an integer (number) is given as input. The reverse method is called with this number, and the reversed number is stored in the reversedNumber variable. The original number and the reversed number are then printed using System.out.println().
35. Write a program to find the power of a number using recursion.
package com.tech.eyes.world4u;
public class PowerOfNumber {
public static double power(double base, int exponent) {
if (exponent == 0) {
return 1;
} else if (exponent > 0) {
return base * power(base, exponent - 1);
} else {
return 1 / (base * power(base, -exponent - 1));
}
}
public static void main(String[] args) {
double base = 2.5;
int exponent = 3;
double result = power(base, exponent);
System.out.println(base + " raised to the power of " + exponent + " is: " + result);
}
}
Output:
2.5 raised to the power of 3 is: 15.625
In this Java program, the power method calculates the power of a number using recursion. The method takes a base number (base) and an exponent (exponent) as input.
If the exponent is 0, the method returns 1 (any number raised to the power of 0 is 1).
If the exponent is positive, the method recursively multiplies the base with the result of power(base, exponent - 1), reducing the exponent by 1 in each recursive call.
If the exponent is negative, the method recursively calculates the reciprocal of the base multiplied by the result of power(base, -exponent - 1), reducing the absolute value of the exponent by 1 in each recursive call.
In the main method, a base number (base) of 2.5 and an exponent (exponent) of 3 are given as input. The power method is called with these values, and the result of the power operation is stored in the result variable. The base number, exponent, and the calculated result are then printed using System.out.println().
36. Write a program to implement a binary search tree and perform an in order traversal.
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
private Node root;
public BinarySearchTree() {
this.root = null;
}
public void insert(int data) {
root = insertRecursive(root, data);
}
private Node insertRecursive(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data) {
root.left = insertRecursive(root.left, data);
} else if (data > root.data) {
root.right = insertRecursive(root.right, data);
}
return root;
}
public void inOrderTraversal() {
inOrderTraversalRecursive(root);
}
private void inOrderTraversalRecursive(Node root) {
if (root != null) {
inOrderTraversalRecursive(root.left);
System.out.print(root.data + " ");
inOrderTraversalRecursive(root.right);
}
}
}
public class BinarySearchTreeExample {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
System.out.print("In-order traversal: ");
bst.inOrderTraversal();
}
}
Output:
In-order traversal: 20 30 40 50 60 70 80
In this Java program, a binary search tree (BST) is implemented using the BinarySearchTree class. Each node of the tree is represented by the Node class, which contains an int data value and references to its left and right child nodes.
The BinarySearchTree class has methods for inserting nodes (insert) and performing an in-order traversal (inOrderTraversal).
The insertRecursive method recursively inserts a new node with the given data into the BST. It compares the data value with the current node and decides whether to go left or right in the tree until it finds an appropriate position for insertion.
The inOrderTraversalRecursive method performs an in-order traversal of the BST recursively. It traverses the left subtree, visits the current node, and then traverses the right subtree.
In the main method, a BinarySearchTree object (bst) is created, and several nodes with different data values are inserted into the BST. The in-order traversal of the BST is then performed using the inOrderTraversal method, and the output is printed using System.out.print.
37. Write a program to find the maximum depth of a binary tree.
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
private Node root;
public BinaryTree() {
this.root = null;
}
public int maxDepth() {
return maxDepthRecursive(root);
}
private int maxDepthRecursive(Node root) {
if (root == null) {
return 0;
} else {
int leftDepth = maxDepthRecursive(root.left);
int rightDepth = maxDepthRecursive(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
}
public class MaxDepthBinaryTree {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.root = new Node(1);
binaryTree.root.left = new Node(2);
binaryTree.root.right = new Node(3);
binaryTree.root.left.left = new Node(4);
binaryTree.root.left.right = new Node(5);
int maxDepth = binaryTree.maxDepth();
System.out.println("Maximum Depth of the Binary Tree: " + maxDepth);
}
}
Output:
Maximum Depth of the Binary Tree: 3
In this Java program, a binary tree is implemented using the BinaryTree class. Each node of the tree is represented by the Node class, which contains an int data value and references to its left and right child nodes.
The BinaryTree class has a method maxDepth that calculates the maximum depth of the binary tree. The maxDepthRecursive method is a recursive helper function that traverses the tree and calculates the depth of each subtree. It returns the maximum depth of the left and right subtrees and adds 1 for the current node.
In the main method, a BinaryTree object (binaryTree) is created, and a binary tree is constructed with several nodes. The maxDepth method is called on the binary tree object to calculate the maximum depth of the tree. The result is then printed using System.out.println.
38. Write a program to find the first non-repeated character in a string.
package com.tech.eyes.world4u;
import java.util.HashMap;
import java.util.Map;
public class FirstNonRepeatedCharacter {
public static char findFirstNonRepeatedCharacter(String str) {
// Create a HashMap to store the frequency of each character
Map charFrequency = new HashMap<>();
// Iterate through the string and count the frequency of each character
for (char c : str.toCharArray()) {
charFrequency.put(c, charFrequency.getOrDefault(c, 0) + 1);
}
// Find the first non-repeated character
for (char c : str.toCharArray()) {
if (charFrequency.get(c) == 1) {
return c;
}
}
// If no non-repeated character found, return a default value
return '\0';
}
public static void main(String[] args) {
String str = "aabbcdeeffggh";
char firstNonRepeatedChar = findFirstNonRepeatedCharacter(str);
if (firstNonRepeatedChar != '\0') {
System.out.println("First non-repeated character: " + firstNonRepeatedChar);
} else {
System.out.println("No non-repeated character found.");
}
}
}
Output:
First non-repeated character: c
In this Java program, the findFirstNonRepeatedCharacter method takes a string (str) as input and finds the first non-repeated character in the string.
The method uses a HashMap to store the frequency of each character in the string. It iterates through the string and counts the frequency of each character by updating the corresponding entry in the charFrequency map.
Then, it iterates through the string again and checks the frequency of each character in the charFrequency map. It returns the first character with a frequency of 1, which is the first non-repeated character.
In the main method, a string (str) is given as input, and the findFirstNonRepeatedCharacter method is called with this string. If a non-repeated character is found, it is printed as output. Otherwise, a message is printed indicating that no non-repeated character is found.
39. Write a program to check if a number is a perfect number.
package com.tech.eyes.world4u;
public class PerfectNumber {
public static boolean isPerfectNumber(int number) {
if (number <= 1) {
return false;
}
int sum = 1; // Initialize sum as 1 (since 1 is a proper divisor of all numbers)
// Find all the proper divisors of the number and add them to the sum
for (int i = 2; i * i <= number; i++) {
if (number % i == 0) {
sum += i;
if (i != number / i) {
sum += number / i;
}
}
}
// Check if the sum of proper divisors is equal to the number
return sum == number;
}
public static void main(String[] args) {
int number = 28;
boolean isPerfect = isPerfectNumber(number);
if (isPerfect) {
System.out.println(number + " is a perfect number.");
} else {
System.out.println(number + " is not a perfect number.");
}
}
}
Output:
28 is a perfect number.
In this Java program, the isPerfectNumber method takes an integer (number) as input and checks if it is a perfect number.
A perfect number is a positive integer that is equal to the sum of its proper divisors (excluding the number itself). For example, 6 is a perfect number because the sum of its proper divisors (1, 2, and 3) is equal to 6.
The method checks if the input number is less than or equal to 1, in which case it returns false since 1 is not considered a perfect number.
Then, it initializes a variable sum to 1 since 1 is always a proper divisor of any number. It iterates through the numbers from 2 to the square root of the input number and checks if the number is divisible by the current iteration value (i). If it is divisible, it adds i to the sum and also adds the corresponding divisor (number / i) to the sum if it's different from i.
Finally, the method compares the sum of the proper divisors with the input number and returns true if they are equal, indicating that the number is a perfect number. Otherwise, it returns false.
In the main method, an integer (number) is given as input, and the isPerfectNumber method is called with this number. If the number is a perfect number, it is printed as output. Otherwise, a message is printed indicating that the number is not a perfect number.
40. Write a program to implement a priority queue using a heap.
package com.tech.eyes.world4u;
import java.util.Arrays;
class PriorityQueue {
private int[] heap;
private int size;
private int capacity;
public PriorityQueue(int capacity) {
this.heap = new int[capacity];
this.size = 0;
this.capacity = capacity;
}
public void insert(int value) {
if (size == capacity) {
System.out.println("Priority queue is full. Cannot insert value: " + value);
return;
}
heap[size] = value;
heapifyUp(size);
size++;
}
public int remove() {
if (isEmpty()) {
throw new IllegalStateException("Priority queue is empty. Cannot remove element.");
}
int removedValue = heap[0];
heap[0] = heap[size - 1];
size--;
heapifyDown(0);
return removedValue;
}
public boolean isEmpty() {
return size == 0;
}
private void heapifyUp(int index) {
int parent = (index - 1) / 2;
while (index > 0 && heap[parent] < heap[index]) {
swap(parent, index);
index = parent;
parent = (index - 1) / 2;
}
}
private void heapifyDown(int index) {
int maxChild;
while (index < size) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
if (leftChild < size && heap[leftChild] > heap[index]) {
maxChild = leftChild;
} else {
maxChild = index;
}
if (rightChild < size && heap[rightChild] > heap[maxChild]) {
maxChild = rightChild;
}
if (maxChild == index) {
break;
}
swap(index, maxChild);
index = maxChild;
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public void print() {
if (isEmpty()) {
System.out.println("Priority queue is empty.");
return;
}
System.out.print("Priority queue: ");
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
}
package com.tech.eyes.world4u;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue priorityQueue = new PriorityQueue(10);
priorityQueue.insert(5);
priorityQueue.insert(3);
priorityQueue.insert(8);
priorityQueue.insert(1);
priorityQueue.insert(10);
priorityQueue.print();
int removedValue = priorityQueue.remove();
System.out.println("Removed value: " + removedValue);
priorityQueue.print();
}
}
Output:
Priority queue: 10 5 8 1 3
Removed value: 10
Priority queue: 8 5 3 1
In this Java program, a priority queue is implemented using a heap. The PriorityQueue class has methods to insert elements, remove elements, check if the priority queue is empty, and print the contents of the priority queue.
The insert method inserts an element into the priority queue. It first checks if the priority queue is full. If not, it adds the element to the end of the heap, performs a heapify-up operation to maintain the heap property, and increments the size.
The remove method removes and returns the highest priority element from the priority queue. It first checks if the priority queue is empty. If not, it replaces the root element with the last element in the heap, performs a heapify-down operation to maintain the heap property, decrements the size, and returns the removed value.
The isEmpty method checks if the priority queue is empty.
The heapifyUp method is used during insertion to move the inserted element up the heap until it reaches its correct position based on its priority.
The heapifyDown method is used during removal to move the new root element down the heap until it reaches its correct position based on its priority.
The swap method is a utility method to swap two elements in the heap.
The print method is used to print the contents of the priority queue.
In the main method, a PriorityQueue object is created with a capacity of 10. Several elements are inserted into the priority queue, and then the priority queue is printed. One element is removed from the priority queue, and the updated priority queue is printed again.
41. Write a program to find the longest common prefix in an array of strings.
package com.tech.eyes.world4u;
public class LongestCommonPrefix {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
// Find the minimum length among all strings in the array
int minLength = Integer.MAX_VALUE;
for (String str : strs) {
minLength = Math.min(minLength, str.length());
}
StringBuilder prefix = new StringBuilder();
for (int i = 0; i < minLength; i++) {
char currentChar = strs[0].charAt(i);
// Check if all characters at the current index are equal across all strings
for (int j = 1; j < strs.length; j++) {
if (strs[j].charAt(i) != currentChar) {
return prefix.toString();
}
}
prefix.append(currentChar);
}
return prefix.toString();
}
public static void main(String[] args) {
String[] strings = { "flower", "flow", "flight" };
String longestPrefix = longestCommonPrefix(strings);
System.out.println("Longest common prefix: " + longestPrefix);
}
}
Output:
Longest common prefix: fl
In this Java program, the longestCommonPrefix method takes an array of strings (strs) as input and returns the longest common prefix among the strings.
The method first checks if the input array is null or empty. If so, it returns an empty string.
Then, it finds the minimum length among all the strings in the array. This is necessary because the longest common prefix cannot be longer than the shortest string in the array.
Next, it iterates over the characters at each index (from 0 to the minimum length) in the first string (strs[0]). For each character, it checks if all the other strings in the array have the same character at the corresponding index. If not, it returns the current prefix.
If all characters at the current index are equal across all strings, the current character is appended to the prefix StringBuilder.
Finally, the method returns the prefix StringBuilder converted to a string.
In the main method, an array of strings (strings) is given as input, and the longestCommonPrefix method is called with this array. The longest common prefix is then printed as output.
42. Write a program to implement a hash table.
package com.tech.eyes.world4u;
class Entry {
private final K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
class HashTable {
private static final int DEFAULT_CAPACITY = 16;
private Entry[] table;
private int size;
public HashTable() {
table = new Entry[DEFAULT_CAPACITY];
size = 0;
}
public void put(K key, V value) {
int index = hash(key);
Entry entry = new Entry<>(key, value);
if (table[index] == null) {
table[index] = entry;
size++;
} else {
Entry current = table[index];
while (current != null) {
if (current.getKey().equals(key)) {
current.setValue(value);
return;
}
current = current.getNext();
}
entry.setNext(table[index]);
table[index] = entry;
size++;
}
}
public V get(K key) {
int index = hash(key);
Entry current = table[index];
while (current != null) {
if (current.getKey().equals(key)) {
return current.getValue();
}
current = current.getNext();
}
return null;
}
public void remove(K key) {
int index = hash(key);
Entry current = table[index];
Entry previous = null;
while (current != null) {
if (current.getKey().equals(key)) {
if (previous == null) {
table[index] = current.getNext();
} else {
previous.setNext(current.getNext());
}
size--;
return;
}
previous = current;
current = current.getNext();
}
}
public int size() {
return size;
}
private int hash(K key) {
return Math.abs(key.hashCode() % DEFAULT_CAPACITY);
}
}
public class Main {
public static void main(String[] args) {
HashTable hashTable = new HashTable<>();
// Insert elements into the hash table
hashTable.put("Apple", 5);
hashTable.put("Banana", 3);
hashTable.put("Cherry", 8);
hashTable.put("Mango", 10);
// Get the value for a specific key
System.out.println("Value for 'Banana': " + hashTable.get("Banana"));
// Remove an entry from the hash table
hashTable.remove("Cherry");
// Check the size of the hash table
System.out.println("Size of the hash table: " + hashTable.size());
}
}
Output:
Value for 'Banana': 3
Size of the hash table: 3
In this program, we first define the Entry class, representing an entry in the hash table. Each entry contains a key and a value.
Next, we define the HashTable class, which is the implementation of the hash table. It uses an array of Entry objects as the underlying data structure. The put method is used to insert key-value pairs into the hash table. The get method retrieves the value for a given key, and the remove method removes an entry from the hash table. The size method returns the number of entries in the hash table.
In the main method, we create an instance of the HashTable class and perform various operations on it. We insert elements with keys "Apple", "Banana", "Cherry", and "Mango" into the hash table, retrieve the value for the key "Banana", remove the entry with the key "Cherry", and finally check the size of the hash table.
43. Write a program to reverse a doubly linked list.
class Node {
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
}
public void reverse() {
if (head == null || head.next == null) {
return;
}
Node current = head;
Node temp = null;
// Swap the prev and next pointers of each node
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
// Update the head pointer to the last node
if (temp != null) {
head = temp.prev;
}
}
public void display() {
Node current = head;
if (current == null) {
System.out.println("Doubly linked list is empty.");
return;
}
System.out.print("Doubly linked list: ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
package com.tech.eyes.world4u;
public class DoublyLinkedListExample {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.insert(1);
dll.insert(2);
dll.insert(3);
dll.insert(4);
dll.insert(5);
System.out.println("Before reversing:");
dll.display();
dll.reverse();
System.out.println("After reversing:");
dll.display();
}
}
Output:
Before reversing:
Doubly linked list: 1 2 3 4 5
After reversing:
Doubly linked list: 5 4 3 2 1
In this Java program, a Node class is defined to represent each node of the doubly linked list. It contains data, a reference to the previous node (prev), and a reference to the next node (next).
A DoublyLinkedList class is also defined, which contains the head pointer of the doubly linked list. It has methods to insert nodes, reverse the doubly linked list, and display the doubly linked list.
The insert method inserts a new node at the end of the doubly linked list.
The reverse method reverses the doubly linked list by swapping the prev and next pointers of each node. It starts from the head node and iterates through the list, swapping the pointers until it reaches the end. It also updates the head pointer to point to the last node after reversing.
The display method is used to print the elements of the doubly linked list.
In the main method, a DoublyLinkedList object (dll) is created, and several elements are inserted into the doubly linked list. The original doubly linked list is displayed. Then, the reverse method is called to reverse the doubly linked list. Finally, the reversed doubly linked list is displayed.
44. Write a program to find the maximum product subarray in an array.
package com.tech.eyes.world4u;
public class MaximumProductSubarray {
public static int maxProductSubarray(int[] nums) {
int n = nums.length;
// Variables to track the maximum and minimum product subarrays
int maxProduct = nums[0];
int minProduct = nums[0];
int maxResult = nums[0];
for (int i = 1; i < n; i++) {
// If the current element is negative, swap the maximum and minimum products
if (nums[i] < 0) {
int temp = maxProduct;
maxProduct = minProduct;
minProduct = temp;
}
// Update the maximum and minimum product subarrays
maxProduct = Math.max(nums[i], maxProduct * nums[i]);
minProduct = Math.min(nums[i], minProduct * nums[i]);
// Update the maximum result
maxResult = Math.max(maxResult, maxProduct);
}
return maxResult;
}
public static void main(String[] args) {
int[] nums = { 2, 3, -2, 4 };
int maxProduct = maxProductSubarray(nums);
System.out.println("Maximum product subarray: " + maxProduct);
}
}
Output:
Maximum product subarray: 6
In this Java program, the maxProductSubarray method takes an array of integers (nums) as input and returns the maximum product of a subarray within the array.
The method uses three variables to keep track of the maximum product (maxProduct), minimum product (minProduct), and the maximum result (maxResult) seen so far.
The method iterates over the array starting from the second element. For each element, it checks if the element is negative. If so, it swaps the maximum and minimum products because multiplying a negative number with the current maximum product can yield a larger product.
Then, it updates the maximum and minimum product subarrays based on the current element. It takes the maximum of the current element or the current element multiplied by the maximum product so far (maxProduct). Similarly, it takes the minimum of the current element or the current element multiplied by the minimum product so far (minProduct).
Finally, it updates the maximum result (maxResult) by taking the maximum of the maximum result and the current maximum product.
In the main method, an array of integers (nums) is given as input, and the maxProductSubarray method is called with this array. The maximum product subarray is then printed as output.
45. Write a program to check if a string is a valid palindrome using a stack.
package com.tech.eyes.world4u;
import java.util.Stack;
public class PalindromeCheck {
public static boolean isPalindrome(String str) {
// Remove non-alphanumeric characters and convert to lowercase
String cleanedStr = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
Stack stack = new Stack<>();
// Push characters onto the stack
for (char ch : cleanedStr.toCharArray()) {
stack.push(ch);
}
// Compare characters from the stack with the string
for (char ch : cleanedStr.toCharArray()) {
if (ch != stack.pop()) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String str = "A man, a plan, a canal: Panama";
boolean isPalindrome = isPalindrome(str);
System.out.println("Is the string a palindrome? " + isPalindrome);
}
}
Output:
Is the string a palindrome? true
In this Java program, the isPalindrome method takes a string (str) as input and returns true if the string is a valid palindrome and false otherwise.
The method first removes all non-alphanumeric characters from the string and converts it to lowercase using regular expressions.
It creates a stack (stack) to store the characters of the cleaned string.
It then iterates over the characters of the cleaned string and pushes each character onto the stack.
Next, it iterates over the characters of the cleaned string again and compares each character with the character popped from the stack. If there is a mismatch, it returns false as the string is not a palindrome.
If all characters match, it returns true as the string is a valid palindrome.
In the main method, a string (str) is given as input, and the isPalindrome method is called with this string. The program then prints whether the string is a palindrome or not.
46. Write a program to implement a breadth-first search (BFS) algorithm.
package com.tech.eyes.world4u;
import java.util.*;
class Graph {
private int V;
private LinkedList[] adjacencyList;
public Graph(int V) {
this.V = V;
adjacencyList = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjacencyList[i] = new LinkedList<>();
}
}
public void addEdge(int v, int w) {
adjacencyList[v].add(w);
}
public void BFS(int startVertex) {
boolean[] visited = new boolean[V];
LinkedList queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
while (queue.size() != 0) {
startVertex = queue.poll();
System.out.print(startVertex + " ");
Iterator iterator = adjacencyList[startVertex].listIterator();
while (iterator.hasNext()) {
int nextVertex = iterator.next();
if (!visited[nextVertex]) {
visited[nextVertex] = true;
queue.add(nextVertex);
}
}
}
}
}
public class BFSExample {
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
System.out.println("Breadth-First Traversal (starting from vertex 0):");
graph.BFS(0);
}
}
Output:
Breadth-First Traversal (starting from vertex 0):
0 1 2 3 4 5
In this Java program, a Graph class is defined to represent a graph data structure. It has a constructor that initializes the number of vertices (V) and an array of linked lists (adjacencyList) to store the adjacency list representation of the graph.
The addEdge method is used to add an edge between two vertices.
The BFS method implements the breadth-first search algorithm. It takes a starting vertex as input and performs the BFS traversal of the graph. It uses a boolean array (visited) to keep track of visited vertices and a queue (queue) to process the vertices in a FIFO manner.
The method starts by marking the starting vertex as visited and enqueueing it. It then enters a loop that dequeues a vertex from the queue, prints it, and enqueues all its unvisited neighbors. This process continues until the queue becomes empty.
In the main method, a Graph object (graph) is created, and several edges are added to the graph using the addEdge method. The breadth-first traversal is then performed starting from vertex 0 using the BFS method.
47. Write a program to find the kth smallest element in an array.
package com.tech.eyes.world4u;
import java.util.Arrays;
public class KthSmallestElement {
public static int findKthSmallest(int[] nums, int k) {
Arrays.sort(nums);
return nums[k - 1];
}
public static void main(String[] args) {
int[] nums = { 5, 8, 2, 9, 1 };
int k = 3;
int kthSmallest = findKthSmallest(nums, k);
System.out.println("The " + k + "th smallest element is: " + kthSmallest);
}
}
Output:
The 3rd smallest element is: 5
In this Java program, the findKthSmallest method takes an array of integers (nums) and an integer (k) as input and returns the kth smallest element in the array.
The method first sorts the array in ascending order using the Arrays.sort() method. Then, it retrieves the element at the k-1 index, as arrays are zero-indexed.
In the main method, an array of integers (nums) and an integer (k) are given as input. The findKthSmallest method is called with these inputs, and the kth smallest element is printed as output.
48. Write a program to convert a binary tree to its mirror image.
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
TreeNode root;
public BinaryTree() {
root = null;
}
public void mirror() {
mirrorHelper(root);
}
private void mirrorHelper(TreeNode node) {
if (node == null) {
return;
}
// Swap the left and right subtrees
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
// Recursively mirror the left and right subtrees
mirrorHelper(node.left);
mirrorHelper(node.right);
}
public void inorderTraversal(TreeNode node) {
if (node == null) {
return;
}
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
}
package com.tech.eyes.world4u;
public class MirrorBinaryTree {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
System.out.println("Original Binary Tree (Inorder Traversal):");
tree.inorderTraversal(tree.root);
tree.mirror();
System.out.println("\nMirror Binary Tree (Inorder Traversal):");
tree.inorderTraversal(tree.root);
}
}
Output:
Original Binary Tree (Inorder Traversal):
4 2 5 1 3
Mirror Binary Tree (Inorder Traversal):
3 1 5 2 4
In this Java program, we define a TreeNode class to represent each node in the binary tree. Each node has a data value, and references to its left and right child nodes.
The BinaryTree class represents the binary tree. It has a mirror method that serves as the entry point for converting the binary tree to its mirror image. The mirrorHelper method is a private helper method that recursively swaps the left and right subtrees of a given node.
The inorderTraversal method performs an inorder traversal of the binary tree to display its elements in order.
In the main method, a binary tree is created with some sample nodes. The original binary tree is displayed using inorder traversal, then the mirror method is called to convert the binary tree to its mirror image. Finally, the mirror binary tree is displayed using inorder traversal.
49. Write a program to implement a merge sort algorithm.
package com.tech.eyes.world4u;
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
int[] temp = new int[n];
mergeSortHelper(arr, temp, 0, n - 1);
}
private static void mergeSortHelper(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSortHelper(arr, temp, left, mid);
mergeSortHelper(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
while (i <= mid) {
arr[k] = temp[i];
i++;
k++;
}
}
public static void main(String[] args) {
int[] arr = { 6, 3, 8, 5, 2 };
System.out.println("Original Array: " + Arrays.toString(arr));
mergeSort(arr);
System.out.println("Sorted Array: " + Arrays.toString(arr));
}
}
Output:
Original Array: [6, 3, 8, 5, 2]
Sorted Array: [2, 3, 5, 6, 8]
In this Java program, the mergeSort method is used to sort an array using the merge sort algorithm. It first checks if the array is null or has only one element, in which case it returns early. Otherwise, it initializes a temporary array temp and calls the mergeSortHelper method to perform the recursive merge sort on the array.
The mergeSortHelper method implements the divide-and-conquer approach of the merge sort algorithm. It recursively divides the array into smaller subarrays until each subarray has one element. Then it calls the merge method to merge and sort the subarrays.
The merge method merges two sorted subarrays into a single sorted array. It uses a temporary array temp to store the elements of the subarrays while merging them.
In the main method, an array of integers (arr) is given as input. The original array is displayed, then the mergeSort method is called to sort the array using merge sort. Finally, the sorted array is displayed.
50. Write a program to find the length of the longest increasing subarray in an array.
package com.tech.eyes.world4u;
public class LongestIncreasingSubarray {
public static int findLongestIncreasingSubarray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxLength = 1;
int currentLength = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
currentLength++;
} else {
maxLength = Math.max(maxLength, currentLength);
currentLength = 1;
}
}
return Math.max(maxLength, currentLength);
}
public static void main(String[] args) {
int[] nums = { 3, 1, 5, 2, 4, 7, 6, 8 };
int longestIncreasingSubarrayLength = findLongestIncreasingSubarray(nums);
System.out.println("Length of the Longest Increasing Subarray: " + longestIncreasingSubarrayLength);
}
}
Output:
Length of the Longest Increasing Subarray: 4
In this Java program, the findLongestIncreasingSubarray method takes an array of integers (nums) as input and returns the length of the longest increasing subarray.
The method iterates through the array and keeps track of the current length of the increasing subarray. If the next element is greater than the previous element, the current length is incremented. If the next element is not greater, the current length is compared with the maximum length so far (maxLength), and if it is greater, the maxLength is updated. The current length is then reset to 1, as the increasing subarray ends at that point.
In the main method, an array of integers (nums) is given as input. The findLongestIncreasingSubarray method is called with this input, and the length of the longest increasing subarray is printed as output.
These coding questions cover a variety of data structures, algorithms, and problem-solving techniques. It's important to practice coding these questions to enhance your problem-solving skills and familiarity with Java programming.
Here is a list of 50 Java coding interview questions suitable for candidates with 3+ years of experience:
1. Write a program to find the maximum element in an array.
package com.tech.eyes.world4u;
public class MaximumElementInArray {
public static int findMaximum(int[] arr) {
if (arr.length == 0) {
return -1; // Return -1 for empty array
}
int maximum = arr[0]; // Assume the first element is the maximum
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maximum) {
maximum = arr[i];
}
}
return maximum;
}
public static void main(String[] args) {
int[] array = { 3, 8, 2, 10, 5 };
int maximumElement = findMaximum(array);
System.out.println("The maximum element in the array is: " + maximumElement);
}
}
Output:
The maximum element in the array is: 12
In this Java program, the findMaximum method takes an integer array (arr) as input and initializes the maximum variable with the first element of the array. Then, it iterates over each element in the array, starting from the second element, and compares it with the current maximum. If an element is found to be greater than the current maximum, it replaces the maximum value with the new element. Finally, the method returns the maximum element.
In the main method, an integer array [3, 8, 2, 10, 5] is created, and the findMaximum method is called to find the maximum element in the array. The result is then printed as output using System.out.println().2. Write a program to reverse a string.
package com.tech.eyes.world4u;
public class StringReversal {
public static String reverseString(String input) {
if (input == null || input.isEmpty()) {
return input;
}
char[] characters = input.toCharArray();
int start = 0;
int end = characters.length - 1;
while (start < end) {
char temp = characters[start];
characters[start] = characters[end];
characters[end] = temp;
start++;
end--;
}
return new String(characters);
}
public static void main(String[] args) {
String inputString = "Hello, World!";
String reversedString = reverseString(inputString);
System.out.println("Reversed string: " + reversedString);
}
}
Output:
Reversed string: !dlroW ,olleH
In this Java program, the reverseString method takes a string (input) as input. It checks if the input is null or empty and returns it as is if true. Otherwise, it converts the string into a character array for in-place manipulation.
The method uses two pointers (start and end) to swap characters from the beginning and end of the array until they meet in the middle. The swapping is performed using a temporary variable.
After the characters are reversed, a new string is created from the reversed character array using the String constructor. The reversed string is then returned.
In the main method, a string "Hello, World!" is passed to the reverseString method. The reversed string is stored in the reversedString variable and printed as output using System.out.println().
The time and space complexity of the program are as follows:
Time Complexity:
The time complexity of the program is O(n), where n is the length of the input string. This is because the program iterates through each character in the string once in the reverseString method. The swapping of characters within the while loop occurs for half of the string length, resulting in a linear time complexity.
Space Complexity:
The space complexity of the program is O(n) as well. It is due to the creation of a character array (characters) to store the characters of the input string. The size of the character array is proportional to the length of the input string. Additionally, the space required to store the reversed string using the new String(characters) constructor is also proportional to the length of the input string.
In summary, the program has a linear time complexity of O(n) and a linear space complexity of O(n), where n is the length of the input string.
3. Write a program to check if a string is a palindrome.
package com.tech.eyes.world4u;
public class PalindromeChecker {
public static boolean isPalindrome(String input) {
if (input == null || input.isEmpty()) {
return true;
}
int start = 0;
int end = input.length() - 1;
while (start < end) {
if (input.charAt(start) != input.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
public static void main(String[] args) {
String inputString = "radar";
boolean isPalindrome = isPalindrome(inputString);
System.out.println("Is the string a palindrome? " + isPalindrome);
}
}
Output:
In this Java program, the isPalindrome method takes a string (input) as input and checks if it is a palindrome. It first handles the cases where the input is null or empty by returning true since an empty string or a single character is considered a palindrome.
The method uses two pointers (start and end) to compare characters from the beginning and end of the string. If the characters are not equal, it immediately returns false indicating that the string is not a palindrome. The pointers move towards the center of the string until they meet or cross each other.
After the loop completes without finding any mismatches, the method returns true indicating that the string is a palindrome.
In the main method, a string "radar" is passed to the isPalindrome method. The result is stored in the isPalindrome variable and printed as output using System.out.println().
Time Complexity:
The time complexity of the program is O(n), where n is the length of the input string. This is because the program iterates through half of the string, comparing characters from both ends. In the worst case, it checks all the characters once, resulting in linear time complexity.
Space Complexity:
The space complexity of the program is O(1), as it does not require any additional data structures that grow with the size of the input. The space usage remains constant regardless of the length of the input string.
In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the length of the input string.
4. Write a program to find the factorial of a number.
package com.tech.eyes.world4u;
public class FactorialCalculator {
public static long factorial(int n) {
if (n < 0) {
throw new IllegalArgumentException("Input cannot be negative");
}
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
public static void main(String[] args) {
int number = 5;
long factorialResult = factorial(number);
System.out.println("Factorial of " + number + " is: " + factorialResult);
}
}
Output:
Factorial of 5 is: 120
In this Java program, the factorial method takes an integer n as input and calculates its factorial. It first checks if the input is negative and throws an IllegalArgumentException if it is, as factorial is defined only for non-negative integers.
The method initializes a variable result to 1. It then iterates from 2 up to n, multiplying each number to the result. The final result value is the factorial of the input number.
In the main method, the program calculates the factorial of the number 5 using the factorial method. The result is stored in the factorialResult variable and printed as output using System.out.println().
Time Complexity:
The time complexity of the program is O(n), where n is the input number. This is because the program iterates through the numbers from 2 to n in the for loop, performing a constant-time multiplication operation for each iteration. As the loop runs n - 2 times, the time complexity is linear with respect to n.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the input number.In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the input number.
5. Write a program to check if a number is prime.
package com.tech.eyes.world4u;
public class PrimeChecker {
public static boolean isPrime(int number) {
if (number <= 1) {
return false;
}
for (int i = 2; i <= Math.sqrt(number); i++) {
if (number % i == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int number = 37;
boolean isPrime = isPrime(number);
System.out.println("Is " + number + " a prime number? " + isPrime);
}
}
Output:
Is 37 a prime number? true
In this Java program, the isPrime method takes an integer number as input and checks if it is a prime number. It first handles the cases where the number is less than or equal to 1, returning false as prime numbers are defined to be greater than 1.
The method uses a for loop to iterate from 2 up to the square root of the number. It checks if the number is divisible by any integer in this range. If it is, the method immediately returns false since a divisor other than 1 and the number itself is found.
If no divisors are found within the loop, the method returns true indicating that the number is prime.
In the main method, the program checks if the number 37 is prime by calling the isPrime method. The result is stored in the isPrime variable and printed as output using System.out.println().
Time Complexity:
The time complexity of the program is O(sqrt(n)), where n is the given number. This is because the program iterates up to the square root of the number in the for loop. The number of iterations in the loop is proportional to the square root of the number, resulting in a square root time complexity.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the input number.In summary, the program has a time complexity of O(sqrt(n)) and a space complexity of O(1), where n is the given number.
6. Write a program to find the Fibonacci series up to a given number.
package com.tech.eyes.world4u;
public class FibonacciSeries {
public static void printFibonacciSeries(int limit) {
if (limit < 1) {
return;
}
long first = 0;
long second = 1;
long next;
System.out.print("Fibonacci Series up to " + limit + ": " + first + " " + second);
while ((next = first + second) <= limit) {
System.out.print(" " + next);
first = second;
second = next;
}
System.out.println();
}
public static void main(String[] args) {
int limit = 100;
printFibonacciSeries(limit);
}
}
Output:
Fibonacci Series up to 100: 0 1 1 2 3 5 8 13 21 34 55 89
In this Java program, the printFibonacciSeries method takes an integer limit as input and generates the Fibonacci series up to that limit. It first handles the case where the limit is less than 1 by simply returning from the method.
The method initializes three variables: first (initialized to 0), second (initialized to 1), and next. It then prints the initial values of first and second as the start of the Fibonacci series.
Inside the while loop, the next Fibonacci number (next) is calculated by summing the previous two numbers (first and second). If the next number is less than or equal to the limit, it is printed, and the values of first and second are updated for the next iteration.
The while loop continues until the next Fibonacci number exceeds the given limit. Finally, a newline is printed to separate the output.
In the main method, the program generates the Fibonacci series up to the limit of 100 by calling the printFibonacciSeries method.
Time Complexity:
The time complexity of the program is O(log n), where n is the given limit. This is because the number of Fibonacci numbers generated up to the limit is proportional to the logarithm of the limit. The calculation of each Fibonacci number takes constant time.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the input limit.In summary, the program has a time complexity of O(log n) and a space complexity of O(1), where n is the given limit.
7. Write a program to find the duplicate elements in an array.
package com.tech.eyes.world4u;
import java.util.HashSet;
public class DuplicateFinder {
public static void findDuplicates(int[] arr) {
if (arr.length < 2) {
return;
}
HashSet uniqueElements = new HashSet<>();
HashSet duplicateElements = new HashSet<>();
for (int num : arr) {
if (!uniqueElements.add(num)) {
duplicateElements.add(num);
}
}
System.out.println("Duplicate elements in the array: " + duplicateElements);
}
public static void main(String[] args) {
int[] array = { 3, 7, 2, 7, 3, 9, 1, 2, 1, 6 };
findDuplicates(array);
}
}
Output:
Duplicate elements in the array: [1, 2, 3, 7]
In this Java program, the findDuplicates method takes an integer array arr as input and finds the duplicate elements in it. It first checks if the length of the array is less than 2, in which case there cannot be any duplicates, so it returns early.
The method uses two HashSet data structures: uniqueElements and duplicateElements. The uniqueElements set is used to keep track of unique elements encountered so far. The duplicateElements set is used to store the duplicate elements found.
The program iterates through each element in the array. For each element, it attempts to add it to the uniqueElements set using the add method. If the element is already present in the set (i.e., it returns false), it means it's a duplicate, and the element is added to the duplicateElements set.
Finally, the program prints the duplicate elements using System.out.println(). In the main method, an integer array [3, 7, 2, 7, 3, 9, 1, 2, 1, 6] is created, and the findDuplicates method is called to find the duplicate elements in the array.
Time Complexity:
The time complexity of the program is O(n), where n is the length of the input array. The program iterates through each element in the array once, performing constant-time operations such as set lookups and insertions.Space Complexity:
The space complexity of the program is O(k), where k is the number of duplicate elements in the array. The program uses two HashSet data structures: uniqueElements and duplicateElements. The space required by these sets is proportional to the number of duplicate elements found in the array.In summary, the program has a linear time complexity of O(n) and a linear space complexity of O(k), where n is the length of the input array and k is the number of duplicate elements.
8. Write a program to sort an array in ascending order.
package com.tech.eyes.world4u;
public class ArraySorter {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were swapped in the inner loop, the array is already sorted
if (!swapped) {
break;
}
}
}
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = { 7, 2, 1, 6, 8, 5, 3, 4 };
System.out.println("Array before sorting:");
printArray(array);
bubbleSort(array);
System.out.println("Array after sorting in ascending order:");
printArray(array);
}
}
Output:
Array before sorting:
7 2 1 6 8 5 3 4
Array after sorting in ascending order:
1 2 3 4 5 6 7 8
In this Java program, the bubbleSort method takes an integer array arr as input and sorts it in ascending order using the bubble sort algorithm. The method iterates through the array multiple times, comparing adjacent elements and swapping them if they are in the wrong order.
The program uses two nested for loops. The outer loop runs from i = 0 to n - 1, where n is the length of the array. The inner loop runs from j = 0 to n - i - 1. In each iteration of the inner loop, adjacent elements are compared, and if they are out of order, they are swapped.
The inner loop continues until the end of the array, and after each iteration of the outer loop, the largest element moves to the end of the array. If no swaps are made in the inner loop, it means the array is already sorted, and the outer loop can be terminated early.
The printArray method is used to print the elements of the array.
In the main method, an integer array [7, 2, 1, 6, 8, 5, 3, 4] is created. The array is printed before sorting, then the bubbleSort method is called to sort the array. Finally, the sorted array is printed.
Time Complexity:
The time complexity of the program is O(n^2), where n is the length of the input array. This is because the program uses a nested loop structure, and in the worst case, it needs to iterate through the array multiple times.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the size of the input array.In summary, the program has a quadratic time complexity of O(n^2) and constant space complexity of O(1), where n is the length of the input array.
9. Write a program to implement a binary search algorithm.
package com.tech.eyes.world4u;
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Element not found
}
public static void main(String[] args) {
int[] array = { 1, 3, 5, 7, 9, 11, 13 };
int target = 9;
int index = binarySearch(array, target);
if (index != -1) {
System.out.println("Element " + target + " found at index " + index);
} else {
System.out.println("Element " + target + " not found in the array");
}
}
}
Output:
Element 9 found at index 4
In this Java program, the binarySearch method takes a sorted integer array arr and a target value as input. It performs a binary search to find the index of the target element in the array. If the element is found, it returns the index. Otherwise, it returns -1 to indicate that the element is not present.
The binary search algorithm maintains two pointers, left and right, initially set to the first and last indices of the array, respectively. It repeatedly divides the search space in half by calculating the middle index (mid). It compares the element at the middle index with the target value.
If the element at mid is equal to the target, the method returns the index of mid. If the element is less than the target, the search range is narrowed to the right half of the array by updating left to mid + 1. If the element is greater than the target, the search range is narrowed to the left half of the array by updating right to mid - 1.
The search continues until the search range is exhausted (left > right), at which point the element is not found, and -1 is returned.
In the main method, an integer array [1, 3, 5, 7, 9, 11, 13] is created and the target value 9 is searched using the binarySearch method. The result is stored in the index variable, and the output is printed accordingly using System.out.println().
Time Complexity:
The time complexity of the binary search algorithm is O(log n), where n is the size of the sorted array. This is because the algorithm halves the search space in each iteration, leading to a logarithmic time complexity.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the size of the input array.In summary, the program has a logarithmic time complexity of O(log n) and constant space complexity of O(1), where n is the size of the sorted array.
10. Write a program to find the second largest element in an array.
package com.tech.eyes.world4u;
public class SecondLargestElement {
public static int findSecondLargest(int[] arr) {
int n = arr.length;
if (n < 2) {
System.out.println("Array should have at least two elements.");
return -1;
}
int largest = Integer.MIN_VALUE;
int secondLargest = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
if (arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
} else if (arr[i] > secondLargest && arr[i] != largest) {
secondLargest = arr[i];
}
}
return secondLargest;
}
public static void main(String[] args) {
int[] array = { 9, 5, 2, 7, 12, 6, 8 };
int secondLargest = findSecondLargest(array);
if (secondLargest != -1) {
System.out.println("The second largest element in the array is: " + secondLargest);
}
}
}
Output:
The second largest element in the array is: 9
In this Java program, the findSecondLargest method takes an integer array arr as input and finds the second largest element in the array. The method initializes two variables, largest and secondLargest, to the minimum integer value.
The method then iterates through the array, comparing each element with the current largest and second largest values. If an element is greater than the current largest, it updates the largest and second largest accordingly. If an element is greater than the current second largest but not equal to the largest element, it updates the second largest value.
Finally, the method returns the second largest element found in the array.
Time Complexity:
The time complexity of the program is O(n), where n is the size of the array. This is because the program iterates through the array once to find the second largest element. The time complexity increases linearly with the size of the input array.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the size of the input array.In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the size of the array.
11. Write a program to remove duplicates from an ArrayList.
package com.tech.eyes.world4u;
import java.util.ArrayList;
import java.util.HashSet;
public class RemoveDuplicates {
public static void removeDuplicates(ArrayList list) {
HashSet uniqueElements = new HashSet<>() ;
ArrayList result = new ArrayList<>() ;
for (Integer num : list) {
if (uniqueElements.add(num)) {
result.add(num);
}
}
list.clear();
list.addAll(result);
}
public static void main(String[] args) {
ArrayList list = new ArrayList<>() ;
list.add(3);
list.add(7);
list.add(2);
list.add(7);
list.add(3);
list.add(9);
list.add(1);
list.add(2);
list.add(1);
list.add(6);
System.out.println("ArrayList before removing duplicates:");
System.out.println(list);
removeDuplicates(list);
System.out.println("ArrayList after removing duplicates:");
System.out.println(list);
}
}
Output:
ArrayList before removing duplicates:
[3, 7, 2, 7, 3, 9, 1, 2, 1, 6]
ArrayList after removing duplicates:
[3, 7, 2, 9, 1, 6]
In this Java program, the removeDuplicates method takes an ArrayList of integers as input and removes duplicates from it. It uses a HashSet to keep track of unique elements encountered so far. It also creates a new ArrayList called result to store the elements without duplicates.
The method iterates through each element in the input ArrayList. For each element, it attempts to add it to the HashSet. If the element is not already present (i.e., the add operation returns true), it adds the element to the result ArrayList.
After processing all the elements, the method clears the input ArrayList and adds all the elements from the result ArrayList back into it, effectively removing the duplicates.
In the main method, an ArrayList is created and initialized with some elements containing duplicates. The original ArrayList is printed before removing duplicates. Then, the removeDuplicates method is called to remove the duplicates from the ArrayList. Finally, the modified ArrayList is printed after removing duplicates.
Time Complexity:
The time complexity of the program is O(n), where n is the size of the input ArrayList. This is because the program iterates through each element in the ArrayList once, performing constant-time operations such as set lookups and insertions.Space Complexity:
The space complexity of the program is O(k), where k is the number of unique elements in the input ArrayList. The program uses a HashSet to store the unique elements encountered, and the space required by the set is proportional to the number of unique elements.In summary, the program has a linear time complexity of O(n) and linear space complexity of O(k), where n is the size of the input ArrayList and k is the number of unique elements.
12. Write a program to reverse a linked list.
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
public void reverse() {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
public void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next = new Node(3);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(5);
System.out.println("Linked List before reversing:");
list.printList();
list.reverse();
System.out.println("Linked List after reversing:");
list.printList();
}
}
Output:
Linked List before reversing:
1 2 3 4 5
Linked List after reversing:
5 4 3 2 1
In this Java program, we define a Node class representing a single node of the linked list. The LinkedList class contains the logic for reversing the linked list. It has a reverse method that reverses the order of the nodes in the linked list.
The reverse method uses three pointers: prev, current, and next. Initially, prev is set to null, current is set to the head of the linked list, and next is set to null. The method iterates through the linked list, changing the next pointer of each node to its previous node. This effectively reverses the order of the nodes. Finally, the head of the linked list is updated to the last node of the original linked list.
The printList method is used to print the elements of the linked list.
In the main method, we create a linked list with nodes containing data values 1, 2, 3, 4, and 5. We print the linked list before reversing it, then call the reverse method to reverse the linked list. Finally, we print the reversed linked list.
Time Complexity:
The time complexity of the program is O(n), where n is the number of nodes in the linked list. This is because the program iterates through each node of the linked list once, performing constant-time operations such as pointer assignments.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of extra space. The space required for the program remains the same, regardless of the size of the linked list. In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the number of nodes in the linked list.13. Write a program to implement a stack using an array.
package com.tech.eyes.world4u;
public class Stack {
private int maxSize;
private int top;
private int[] stackArray;
public Stack(int size) {
maxSize = size;
top = -1;
stackArray = new int[maxSize];
}
public void push(int value) {
if (isFull()) {
System.out.println("Stack is full. Cannot push element " + value);
return;
}
stackArray[++top] = value;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty. Cannot pop element.");
return -1;
}
return stackArray[top--];
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty. Cannot peek element.");
return -1;
}
return stackArray[top];
}
public boolean isEmpty() {
return (top == -1);
}
public boolean isFull() {
return (top == maxSize - 1);
}
public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);
stack.push(50);
System.out.println("Stack elements:");
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
Output:
Stack elements:
50
40
30
20
10
Time Complexity:
The time complexity of the push, pop, and peek operations in the stack implemented using an array is O(1). These operations involve accessing or modifying the top element of the stack, which can be done in constant time.Space Complexity:
The space complexity of the program is O(n), where n is the maximum size of the stack. This is because the program uses an array of size maxSize to store the stack elements.In summary, the program has constant time complexity of O(1) for push, pop, and peek operations, and linear space complexity of O(n) where n is the maximum size of the stack.
14. Write a program to find the missing number in an array.
package com.tech.eyes.world4u;
public class MissingNumber {
public static int findMissingNumber(int[] arr) {
int n = arr.length;
int expectedSum = (n + 1) * (n + 2) / 2;
int actualSum = 0;
for (int i = 0; i < n; i++) {
actualSum += arr[i];
}
return expectedSum - actualSum;
}
public static void main(String[] args) {
int[] array = { 1, 2, 4, 5, 6 };
int missingNumber = findMissingNumber(array);
System.out.println("Missing number: " + missingNumber);
}
}
Output:
Missing number: 3
In this Java program, the findMissingNumber method takes an integer array arr as input and finds the missing number in the array. The method calculates the expected sum of numbers from 1 to n+1 (where n is the length of the array) using the formula (n+1) * (n+2) / 2. It then calculates the actual sum of the numbers in the array by iterating through the array and summing up all the elements. Finally, it returns the difference between the expected sum and the actual sum, which represents the missing number.
In the main method, an integer array [1, 2, 4, 5, 6] is created, and the findMissingNumber method is called to find the missing number. The missing number is then printed using System.out.println().
Time Complexity:
The time complexity of the program is O(n), where n is the length of the input array. This is because the program iterates through the array once to calculate the actual sum. The time complexity increases linearly with the size of the input array.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of space. The space required for the program remains the same, regardless of the size of the input array. In summary, the program has a linear time complexity of O(n) and constant space complexity of O(1), where n is the length of the array.15. Write a program to check if two strings are anagrams.
package com.tech.eyes.world4u;
import java.util.Arrays;
public class AnagramCheck {
public static boolean areAnagrams(String str1, String str2) {
// Removing whitespaces and converting to lowercase
str1 = str1.replaceAll("\\s", "").toLowerCase();
str2 = str2.replaceAll("\\s", "").toLowerCase();
// If lengths are different, strings cannot be anagrams
if (str1.length() != str2.length()) {
return false;
}
// Converting strings to char arrays and sorting them
char[] charArr1 = str1.toCharArray();
char[] charArr2 = str2.toCharArray();
Arrays.sort(charArr1);
Arrays.sort(charArr2);
// Checking if sorted arrays are equal
return Arrays.equals(charArr1, charArr2);
}
public static void main(String[] args) {
String str1 = "listen";
String str2 = "silent";
if (areAnagrams(str1, str2)) {
System.out.println(str1 + " and " + str2 + " are anagrams.");
} else {
System.out.println(str1 + " and " + str2 + " are not anagrams.");
}
}
}
Output:
listen and silent are anagrams.
In this Java program, the areAnagrams method takes two strings, str1 and str2, as input and checks if they are anagrams of each other.
First, the method removes whitespaces from the strings and converts them to lowercase using the replaceAll and toLowerCase methods.
Next, the method compares the lengths of the two strings. If they are not equal, the strings cannot be anagrams, so the method returns false.
Then, the strings are converted to character arrays using the toCharArray method. The character arrays are sorted using the Arrays.sort method.
Finally, the method compares the sorted character arrays using the Arrays.equals method. If the sorted arrays are equal, the strings are anagrams, and the method returns true. Otherwise, it returns false.
Time Complexity:
The time complexity of the program is O(n log n), where n is the length of the longer input string. This is because the program sorts the character arrays, which has a time complexity of O(n log n), where n is the length of the character array.Space Complexity:
The space complexity of the program is O(n), where n is the length of the longer input string. This is because the program creates character arrays to store the modified strings, and the space required is proportional to the length of the strings.In summary, the program has a time complexity of O(n log n) and a space complexity of O(n), where n is the length of the longer input string.
16. Write a program to implement a queue using two stacks.
package com.tech.eyes.world4u;
import java.util.Stack;
public class QueueUsingStack {
private Stack stack1;
private Stack stack2;
public QueueUsingStack() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void enqueue(int value) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
stack1.push(value);
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue element.");
return -1;
}
return stack1.pop();
}
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot peek element.");
return -1;
}
return stack1.peek();
}
public boolean isEmpty() {
return stack1.isEmpty();
}
public static void main(String[] args) {
QueueUsingStack queue = new QueueUsingStack();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
System.out.println("Dequeued element: " + queue.dequeue());
System.out.println("Peeked element: " + queue.peek());
queue.enqueue(40);
System.out.println("Dequeued element: " + queue.dequeue());
System.out.println("Dequeued element: " + queue.dequeue());
System.out.println("Is queue empty? " + queue.isEmpty());
}
}
Output:
Dequeued element: 10
Peeked element: 20
Dequeued element: 20
Dequeued element: 30
Is queue empty? false
In this Java program, the QueueUsingStack class represents a queue implemented using two stacks. It has two private member variables stack1 and stack2, which are stacks used for enqueueing and dequeueing elements.
The QueueUsingStack class provides the following methods:
- enqueue(value): Adds an element to the queue. It transfers all the elements from stack1 to stack2, pushes the new element to stack1, and then transfers all the elements back to stack1.
- dequeue(): Removes and returns the front element from the queue. If the queue is empty, it displays an error message and returns -1.
- peek(): Returns the front element of the queue without removing it. If the queue is empty, it displays an error message and returns -1.
- isEmpty(): Checks if the queue is empty and returns a boolean value.
In the main method, a QueueUsingStack object is created. Three elements (10, 20, 30) are enqueued using the enqueue method. Then, an element is dequeued and its value is printed using the dequeue method. The front element is peeked using the peek method. Another element (40) is enqueued, and two elements are dequeued and printed. Finally, the isEmpty method is used to check if the queue is empty.
Time Complexity
The time complexity for enqueue and dequeue operations in this implementation is O(n), where n is the number of elements in the queue. The enqueue operation involves transferring elements between stacks, which takes linear time. The dequeue operation involves popping an element from stack1, which takes constant time.Space Complexity
The space complexity of the program is O(n), where n is the number of elements in the queue. This is because the program uses two stacks to store the elements.17. Write a program to find the common elements between two arrays.
package com.tech.eyes.world4u;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class CommonElements {
public static List findCommonElements(int[] array1, int[] array2) {
Set set = new HashSet<>();
List commonElements = new ArrayList<>();
for (int num : array1) {
set.add(num);
}
for (int num : array2) {
if (set.contains(num)) {
commonElements.add(num);
}
}
return commonElements;
}
public static void main(String[] args) {
int[] array1 = { 1, 2, 3, 4, 5 };
int[] array2 = { 4, 5, 6, 7, 8 };
List commonElements = findCommonElements(array1, array2);
System.out.println("Common elements:");
for (int num : commonElements) {
System.out.println(num);
}
}
}
Output:
Common elements:
4
5
In this Java program, the findCommonElements method takes two integer arrays, array1 and array2, as input and finds the common elements between them. It uses a HashSet to store the elements of array1. Then, it iterates through array2 and checks if each element exists in the HashSet. If it does, the element is added to the commonElements list.
In the main method, two integer arrays, array1 and array2, are created with some elements. The findCommonElements method is called to find the common elements between the arrays. The common elements are then printed using System.out.println().
Time Complexity:
The time complexity of the program is O(m + n), where m is the length of array1 and n is the length of array2. The program iterates through both arrays once to create the HashSet and find the common elements. The time complexity increases linearly with the sizes of the input arrays.Space Complexity:
The space complexity of the program is O(m), where m is the length of array1. This is because the program uses a HashSet to store the elements of array1. The space required is proportional to the size of array1.In summary, the program has a time complexity of O(m + n) and a space complexity of O(m), where m is the length of array1 and n is the length of array2.
18. Write a program to find the longest palindrome in a given string.
package com.tech.eyes.world4u;
public class LongestPalindrome {
public static String findLongestPalindrome(String str) {
if (str == null || str.length() < 2) {
return str;
}
int maxLength = 1;
int start = 0;
for (int i = 0; i < str.length(); i++) {
int len1 = expandFromCenter(str, i, i); // odd-length palindromes
int len2 = expandFromCenter(str, i, i + 1); // even-length palindromes
int currentLength = Math.max(len1, len2);
if (currentLength > maxLength) {
maxLength = currentLength;
start = i - (currentLength - 1) / 2;
}
}
return str.substring(start, start + maxLength);
}
private static int expandFromCenter(String str, int left, int right) {
int length = 0;
while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {
length = right - left + 1;
left--;
right++;
}
return length;
}
public static void main(String[] args) {
String input = "babad";
String longestPalindrome = findLongestPalindrome(input);
System.out.println("Longest Palindrome: " + longestPalindrome);
}
}
Output:
Longest Palindrome: bab
In this Java program, the findLongestPalindrome method takes a string str as input and finds the longest palindrome within it. The program uses the concept of expanding around centers to find palindromes. It iterates through each character in the string and considers it as a center. It expands from the center character outward in both directions to find the longest palindrome. The method expandFromCenter is used to perform the expansion and return the length of the palindrome. The start and end indices of the longest palindrome are tracked, and the substring is extracted using the substring method.
In the main method, a string "babad" is provided as input, and the findLongestPalindrome method is called to find the longest palindrome within it. The longest palindrome is then printed using System.out.println().
Time Complexity:
The time complexity of the program is O(n^2), where n is the length of the input string. This is because for each character in the string, the program expands around it in both directions to find palindromes. In the worst case, when all characters are the same, the program will have to expand from the center for each character, resulting in n^2 iterations.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of extra space. The space required for the program remains the same, regardless of the size of the input string.In summary, the program has a time complexity of O(n^2) and a constant space complexity of O(1), where n is the length of the input string.
19. Write a program to check if a number is a perfect square.
package com.tech.eyes.world4u;
public class PerfectSquareChecker {
public static boolean isPerfectSquare(int num) {
if (num < 0) {
return false;
}
if (num == 0 || num == 1) {
return true;
}
long start = 1;
long end = num;
while (start <= end) {
long mid = start + (end - start) / 2;
long square = mid * mid;
if (square == num) {
return true;
} else if (square < num) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return false;
}
public static void main(String[] args) {
int number1 = 16;
int number2 = 25;
int number3 = 14;
System.out.println(number1 + " is a perfect square? " + isPerfectSquare(number1));
System.out.println(number2 + " is a perfect square? " + isPerfectSquare(number2));
System.out.println(number3 + " is a perfect square? " + isPerfectSquare(number3));
}
}
Output:
16 is a perfect square? true
25 is a perfect square? true
14 is a perfect square? false
In this Java program, the isPerfectSquare method takes an integer num as input and checks if it is a perfect square. The program uses a binary search approach to find the square root of the number. It initializes start as 1 and end as the given number. It calculates the middle value, squares it, and compares it with the given number. If the square is equal to the given number, it returns true. If the square is less than the given number, it updates the start value to mid + 1 to search in the higher range. If the square is greater than the given number, it updates the end value to mid - 1 to search in the lower range. The loop continues until the start value is less than or equal to the end value. If the loop finishes without finding a perfect square, it returns false.
In the main method, three numbers (number1, number2, number3) are checked using the isPerfectSquare method, and the results are printed using System.out.println().
Time Complexity:
The time complexity of the program is O(log n), where n is the given number. This is because the program uses a binary search approach to find the square root of the number. It repeatedly halves the search range until it finds the square root or exhausts the range.Space Complexity:
The space complexity of the program is O(1), as it only uses a constant amount of extra space. The space required for the program remains the same, regardless of the size of the input number.In summary, the program has a time complexity of O(log n) and a constant space complexity of O(1), where n is the given number.
20. Write a program to calculate the sum of digits of a number.
package com.tech.eyes.world4u;
public class SumOfDigits {
public static int calculateSumOfDigits(int number) {
int sum = 0;
while (number != 0) {
int digit = number % 10;
sum += digit;
number /= 10;
}
return sum;
}
public static void main(String[] args) {
int number = 12345;
int sum = calculateSumOfDigits(number);
System.out.println("Sum of digits of " + number + ": " + sum);
}
}
Output:
Sum of digits of 12345: 15
In this Java program, the calculateSumOfDigits method takes an integer number as input and calculates the sum of its digits. The program uses a while loop to iterate until the number becomes 0. In each iteration, the last digit of the number is obtained by using the modulus operator %. This digit is added to the sum variable. Then, the number is divided by 10 to remove the last digit. The loop continues until all digits have been processed. Finally, the sum of the digits is returned.
In the main method, an integer number is set to 12345. The calculateSumOfDigits method is called with this number, and the sum is stored in the sum variable. The sum of the digits is then printed using System.out.println().
21. Write a program to find the intersection of two linked lists.
package com.tech.eyes.world4u;
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class IntersectionLinkedList {
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode currA = headA;
ListNode currB = headB;
while (currA != currB) {
currA = (currA == null) ? headB : currA.next;
currB = (currB == null) ? headA : currB.next;
}
return currA;
}
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
ListNode node4 = new ListNode(4);
ListNode node5 = new ListNode(5);
ListNode headA = node1;
headA.next = node2;
headA.next.next = node3;
headA.next.next.next = node4;
ListNode headB = node5;
headB.next = node3;
ListNode intersectionNode = getIntersectionNode(headA, headB);
System.out.println("Intersection Node: " + intersectionNode.val);
}
}
Output:
Intersection Node: 3
In this Java program, there is a ListNode class representing a node in a linked list. Each node has an integer value and a next reference pointing to the next node in the list.
The getIntersectionNode method takes two linked lists headA and headB as input and finds the intersection node between them. It iterates through both lists simultaneously, moving each pointer forward. When one pointer reaches the end of a list, it is redirected to the head of the other list. If there is an intersection, both pointers will eventually meet at the intersection node. If there is no intersection, both pointers will reach the end of the lists, i.e., null.
In the main method, two linked lists are created with nodes node1, node2, node3, node4, and node5. headA and headB are assigned the respective heads of the lists. Node node3 is the intersection point of both lists. The getIntersectionNode method is called to find the intersection node, and the value of the intersection node is printed using System.out.println().
22. Write a program to count the occurrences of each element in an array.
package com.tech.eyes.world4u;
import java.util.HashMap;
import java.util.Map;
public class ElementOccurrences {
public static void countElementOccurrences(int[] arr) {
Map entry : occurrences.entrySet()) {
System.out.println("Element " + entry.getKey() + " occurs " + entry.getValue() + " times.");
}
}
public static void main(String[] args) {
int[] arr = {2, 5, 2, 7, 4, 5, 7, 2, 4, 4, 5};
countElementOccurrences(arr);
}
}
Output:
Element 2 occurs 3 times.
Element 4 occurs 3 times.
Element 5 occurs 3 times.
Element 7 occurs 2 times.
In this Java program, the countElementOccurrences method takes an array arr as input and counts the occurrences of each element in the array. It uses a HashMap to store the elements as keys and their respective occurrences as values. The program iterates through the array and checks if the element already exists in the occurrences map. If it exists, the occurrence count is incremented. If it doesn't exist, a new entry is added with an occurrence count of 1. Finally, the program iterates through the occurrences map and prints each element along with its occurrence count.
In the main method, an array arr is initialized with some numbers. The countElementOccurrences method is called with this array, and it counts the occurrences of each element in the array. The occurrences are then printed using System.out.println().
23. Write a program to reverse a sentence word by word.
package com.tech.eyes.world4u;
public class ReverseSentence {
public static String reverseSentence(String sentence) {
String[] words = sentence.split(" ");
StringBuilder reversedSentence = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
reversedSentence.append(words[i]);
if (i > 0) {
reversedSentence.append(" ");
}
}
return reversedSentence.toString();
}
public static void main(String[] args) {
String sentence = "Hello world! How are you?";
String reversedSentence = reverseSentence(sentence);
System.out.println("Original sentence: " + sentence);
System.out.println("Reversed sentence: " + reversedSentence);
}
}
Output:
Original sentence: Hello world! How are you?
Reversed sentence: you? are How world! Hello
In this Java program, the reverseSentence method takes a sentence as input and reverses it word by word. The sentence is split into individual words using the split method, with the delimiter as a space (" "). The program then iterates over the words array from the last index to the first index. Each word is appended to a StringBuilder named reversedSentence, with a space added between words. Finally, the reversedSentence is converted back to a string using the toString method and returned.
In the main method, a sentence "Hello world! How are you?" is given as input. The reverseSentence method is called with this sentence, and the reversed sentence is stored in the reversedSentence variable. The original sentence and the reversed sentence are then printed using System.out.println().
24. Write a program to implement a binary tree and perform an in order traversal.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class BinaryTree {
public static void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.print(root.val + " ");
inOrderTraversal(root.right);
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.print("In-order traversal: ");
inOrderTraversal(root);
}
}
Output:
In-order traversal: 4 2 5 1 3
In this Java program, there is a TreeNode class representing a node in a binary tree. Each node has an integer value, and it has references to its left and right child nodes.
The inOrderTraversal method takes a TreeNoderoot as input and performs an in-order traversal of the binary tree. The method uses recursion to traverse the tree in the order: left subtree, current node, right subtree. It first checks if the root is null, and if so, it returns. Then, it recursively calls the inOrderTraversal method on the left subtree, prints the value of the current node, and recursively calls the method on the right subtree.
In the main method, a binary tree is created with nodes and connections. The inOrderTraversal method is called with the root of the tree, and it performs the in-order traversal. The values of the nodes are printed during the traversal using System.out.print().
25. Write a program to find the maximum sum subarray in an array.
package com.tech.eyes.world4u;
public class MaximumSubarraySum {
public static int findMaximumSubarraySum(int[] nums) {
int maxSum = Integer.MIN_VALUE;
int currentSum = 0;
for (int num : nums) {
currentSum = Math.max(num, currentSum + num);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int maxSum = findMaximumSubarraySum(nums);
System.out.println("Maximum sum of a subarray: " + maxSum);
}
}
Output:
Maximum sum of a subarray: 6
In this Java program, the findMaximumSubarraySum method takes an integer array nums as input and finds the maximum sum of a subarray using Kadane's algorithm. The algorithm initializes two variables: maxSum to track the maximum sum found so far (initialized with the minimum possible value) and currentSum to track the sum of the current subarray (initialized with 0). It then iterates through each element in the array, updating currentSum by taking the maximum of the current element or the sum of the current element and the previous currentSum. It also updates maxSum by taking the maximum of the current maxSum and the updated currentSum. Finally, it returns maxSum.
In the main method, an array nums is initialized with values. The findMaximumSubarraySum method is called with this array, and the maximum sum of a subarray is stored in the maxSum variable. The maximum sum is then printed using System.out.println().
26. Write a program to check if a string is a valid parentheses expression.
package com.tech.eyes.world4u;
import java.util.Stack;
public class ValidParentheses {
public static boolean isValid(String s) {
Stack
In this Java program, the isValid method takes a string s as input and checks if it is a valid parentheses expression. It uses a stack to keep track of opening parentheses. It iterates through each character in the string. If the character is an opening parentheses ((, [, or {), it is pushed onto the stack. If the character is a closing parentheses (), ], or }), it is checked if the stack is not empty and the top of the stack corresponds to the matching opening parentheses. If they match, the opening parentheses is popped from the stack. If any other character is encountered or there is a mismatch between the closing and opening parentheses, the expression is considered invalid, and false is returned. After iterating through all characters, it is checked if the stack is empty. If it is empty, the expression is valid; otherwise, it is invalid.
In the main method, several test cases are given as input strings (s1, s2, s3, s4, s5). The isValid method is called with each string, and the result of validity is printed using System.out.println().
The program checks if each input string is a valid parentheses expression and prints the validity result. In this example, s1, s2, and s5 are valid expressions, while s3 and s4 are invalid expressions.
27. Write a program to implement a circular linked list.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedList {
private Node head;
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
head.next = head;
} else {
Node current = head;
while (current.next != head) {
current = current.next;
}
current.next = newNode;
newNode.next = head;
}
}
public void display() {
if (head == null) {
System.out.println("Circular Linked List is empty.");
return;
}
Node current = head;
do {
System.out.print(current.data + " ");
current = current.next;
} while (current != head);
System.out.println();
}
public static void main(String[] args) {
CircularLinkedList circularLinkedList = new CircularLinkedList();
circularLinkedList.insert(1);
circularLinkedList.insert(2);
circularLinkedList.insert(3);
circularLinkedList.insert(4);
System.out.println("Circular Linked List:");
circularLinkedList.display();
}
}
Output:
Circular Linked List:
1 2 3 4
In this Java program, a circular linked list is implemented using the Node class to represent each node in the list. The CircularLinkedList class has methods for insertion and display of the circular linked list.
The insert method is used to insert a new node at the end of the circular linked list. If the list is empty, the new node becomes the head and points to itself. Otherwise, it iterates through the list until it reaches the last node (whose next points to the head), and then inserts the new node.
The display method is used to print the elements of the circular linked list. It starts from the head and traverses the list until it reaches the head again, printing the data of each node.
In the main method, a CircularLinkedList object is created, and some elements (1, 2, 3, and 4) are inserted into the list using the insert method. Finally, the elements of the circular linked list are displayed using the display method.
28. Write a program to find the largest prime factor of a number.
package com.tech.eyes.world4u;
public class LargestPrimeFactor {
public static long findLargestPrimeFactor(long number) {
long largestPrimeFactor = 1;
while (number % 2 == 0) {
largestPrimeFactor = 2;
number /= 2;
}
for (int i = 3; i <= Math.sqrt(number); i += 2) {
while (number % i == 0) {
largestPrimeFactor = i;
number /= i;
}
}
if (number > 2) {
largestPrimeFactor = number;
}
return largestPrimeFactor;
}
public static void main(String[] args) {
long number = 13195;
long largestPrimeFactor = findLargestPrimeFactor(number);
System.out.println("Largest prime factor of " + number + " is: " + largestPrimeFactor);
}
}
Output:
Largest prime factor of 13195 is: 29
In this Java program, the findLargestPrimeFactor method takes a long number as input and finds the largest prime factor of that number. It uses a loop to divide the number by 2 until it is no longer divisible by 2, updating the largestPrimeFactor to 2 each time. Then, it iterates from 3 to the square root of the number, checking if the number is divisible by each odd number.
If it is divisible, it updates the largestPrimeFactor to that divisor and divides the number by that divisor. Finally, if the remaining number is greater than 2, it updates the largestPrimeFactor to that remaining number. The method returns the largestPrimeFactor.
In the main method, a test number (number) is given as input. The findLargestPrimeFactor method is called with this number, and the largest prime factor is stored in the largestPrimeFactor variable. The largest prime factor is then printed using System.out.println().
29. Write a program to check if a binary tree is balanced.
package com.tech.eyes.world4u;
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class BalancedBinaryTree {
public static boolean isBalanced(Node root) {
if (root == null) {
return true;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
return true;
}
return false;
}
public static int getHeight(Node node) {
if (node == null) {
return 0;
}
int leftHeight = getHeight(node.left);
int rightHeight = getHeight(node.right);
return Math.max(leftHeight, rightHeight) + 1;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
boolean isBalanced = isBalanced(root);
System.out.println("Is the binary tree balanced? " + isBalanced);
}
}
Output:
Is the binary tree balanced? false
In this Java program, a binary tree is represented using the Node class, which has an int data value, and references to the left and right child nodes. The BalancedBinaryTree class has methods to check if a binary tree is balanced and to calculate the height of a node.
The isBalanced method takes a Node root as input and recursively checks if the tree is balanced by comparing the heights of the left and right subtrees. It calls the getHeight method to calculate the height of each node. If the absolute difference between the heights is less than or equal to 1, and both the left and right subtrees are balanced, it returns true. Otherwise, it returns false.
The getHeight method calculates the height of a node by recursively calculating the height of its left and right subtrees. It returns the maximum height between the left and right subtrees plus 1.
In the main method, a binary tree is created with some sample nodes. The isBalanced method is called with the root of the tree, and the result of whether the binary tree is balanced or not is stored in the isBalanced variable. The result is then printed using System.out.println().
30. Write a program to find the intersection of two sorted arrays.
package com.tech.eyes.world4u;
import java.util.ArrayList;
import java.util.List;
public class IntersectionOfArrays {
public static List findIntersection(int[] arr1, int[] arr2) {
List intersection = findIntersection(arr1, arr2);
System.out.println("Intersection of the two arrays: " + intersection);
}
}
Output:
Intersection of the two arrays: [2, 4]
In this Java program, the findIntersection method takes two sorted arrays (arr1 and arr2) as input and finds their intersection. It uses two pointers, i and j, to iterate through the arrays. The method compares the elements at the current positions of the pointers. If the element in arr1 is less than the element in arr2, i is incremented.
If the element in arr1 is greater than the element in arr2, j is incremented. If the elements are equal, the element is added to the intersection list, and both i and j are incremented. This process continues until either array reaches its end.
In the main method, two sorted arrays (arr1 and arr2) are given as input. The findIntersection method is called with these arrays, and the intersection is stored in the intersection list. The intersection of the two arrays is then printed using System.out.println().
31. Write a program to find the minimum element in a rotated sorted array.
package com.tech.eyes.world4u;
public class MinimumInRotatedArray {
public static int findMinimum(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
}
}
return nums[left];
}
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
int minimum = findMinimum(nums);
System.out.println("Minimum element in the rotated sorted array: " + minimum);
}
}
Output:
Minimum element in the rotated sorted array: 0
In this Java program, the findMinimum method takes a rotated sorted array (nums) as input and finds the minimum element in it. It uses a modified version of the binary search algorithm to perform the search. The method initializes the left pointer to the beginning of the array and the right pointer to the end of the array.
The method repeatedly divides the array into two halves and checks if the mid element is greater than the rightmost element. If it is, it means the minimum element lies in the right half of the array, so the left pointer is moved to mid + 1. If the mid element is less than the rightmost element, it means the minimum element lies in the left half of the array, so the right pointer is moved to mid. This process continues until the left and right pointers converge, indicating that the minimum element has been found.
In the main method, a rotated sorted array (nums) is given as input. The findMinimum method is called with this array, and the minimum element is stored in the minimum variable. The minimum element in the rotated sorted array is then printed using System.out.println().
32. Write a program to check if a string is a valid palindrome ignoring non-alphanumeric characters.
package com.tech.eyes.world4u;
public class ValidPalindrome {
public static boolean isPalindrome(String str) {
// Remove non-alphanumeric characters and convert to lowercase
String processedStr = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
// Check if the processed string is a palindrome
int left = 0;
int right = processedStr.length() - 1;
while (left < right) {
if (processedStr.charAt(left) != processedStr.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
String str = "A man, a plan, a canal: Panama";
boolean isPalindrome = isPalindrome(str);
System.out.println("Is the string a valid palindrome? " + isPalindrome);
}
}
Output:
Is the string a valid palindrome? true
In this Java program, the isPalindrome method takes a string (str) as input and checks if it is a valid palindrome while ignoring non-alphanumeric characters. First, it removes all non-alphanumeric characters from the string using the replaceAll method and regular expression [^a-zA-Z0-9]. Then, it converts the processed string to lowercase.
The method uses two pointers, left and right, to compare characters from the start and end of the processed string. It iterates until the left pointer is less than the right pointer. If the characters at the left and right pointers are not equal, it means the string is not a palindrome and returns false. If all characters are equal, it returns true.
In the main method, a string (str) is given as input. The isPalindrome method is called with this string, and the result of whether the string is a valid palindrome or not is stored in the isPalindrome variable. The result is then printed using System.out.println().
33. Write a program to implement a queue using a linked list.
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class Queue {
private Node front;
private Node rear;
public Queue() {
this.front = null;
this.rear = null;
}
public boolean isEmpty() {
return front == null;
}
public void enqueue(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
rear.next = newNode;
rear = newNode;
}
System.out.println("Enqueued: " + data);
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty");
return -1;
}
int data = front.data;
front = front.next;
if (front == null) {
rear = null;
}
System.out.println("Dequeued: " + data);
return data;
}
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty");
return;
}
Node temp = front;
System.out.print("Queue: ");
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
}
public class QueueUsingLinkedList {
public static void main(String[] args) {
Queue queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.display();
queue.dequeue();
queue.dequeue();
queue.display();
queue.enqueue(40);
queue.display();
}
}
Output:
Enqueued: 10
Enqueued: 20
Enqueued: 30
Queue: 10 20 30
Dequeued: 10
Dequeued: 20
Queue: 30
Enqueued: 40
Queue: 30 40
In this Java program, a linked list is used to implement a queue. The Node class represents each node in the linked list, containing an int data value and a reference to the next node. The Queue class represents the queue and contains methods to enqueue, dequeue, check if the queue is empty, and display the elements of the queue.
The enqueue method adds an element to the rear of the queue by creating a new node and updating the rear pointer accordingly.
The dequeue method removes the element from the front of the queue and updates the front pointer accordingly.
The display method prints the elements of the queue.
In the main method, a Queue object is created, and various operations are performed on the queue, such as enqueueing elements (10, 20, 30), dequeuing elements, and displaying the queue after each operation.
34. Write a program to reverse a number.
package com.tech.eyes.world4u;
public class ReverseNumber {
public static int reverse(int number) {
int reversed = 0;
while (number != 0) {
int digit = number % 10;
reversed = reversed * 10 + digit;
number /= 10;
}
return reversed;
}
public static void main(String[] args) {
int number = 12345;
int reversedNumber = reverse(number);
System.out.println("Original number: " + number);
System.out.println("Reversed number: " + reversedNumber);
}
}
Output:
Original number: 12345
Reversed number: 54321
In this Java program, the reverse method takes an integer (number) as input and reverses the digits of the number. It initializes a variable reversed to 0. It then iteratively extracts the last digit of the number using the modulus operator % and appends it to the reversed variable by multiplying it by 10 and adding the digit. Finally, it divides the number by 10 to discard the last digit. This process continues until the number becomes 0.
In the main method, an integer (number) is given as input. The reverse method is called with this number, and the reversed number is stored in the reversedNumber variable. The original number and the reversed number are then printed using System.out.println().
35. Write a program to find the power of a number using recursion.
package com.tech.eyes.world4u;
public class PowerOfNumber {
public static double power(double base, int exponent) {
if (exponent == 0) {
return 1;
} else if (exponent > 0) {
return base * power(base, exponent - 1);
} else {
return 1 / (base * power(base, -exponent - 1));
}
}
public static void main(String[] args) {
double base = 2.5;
int exponent = 3;
double result = power(base, exponent);
System.out.println(base + " raised to the power of " + exponent + " is: " + result);
}
}
Output:
2.5 raised to the power of 3 is: 15.625
In this Java program, the power method calculates the power of a number using recursion. The method takes a base number (base) and an exponent (exponent) as input.
If the exponent is 0, the method returns 1 (any number raised to the power of 0 is 1). If the exponent is positive, the method recursively multiplies the base with the result of power(base, exponent - 1), reducing the exponent by 1 in each recursive call. If the exponent is negative, the method recursively calculates the reciprocal of the base multiplied by the result of power(base, -exponent - 1), reducing the absolute value of the exponent by 1 in each recursive call.
In the main method, a base number (base) of 2.5 and an exponent (exponent) of 3 are given as input. The power method is called with these values, and the result of the power operation is stored in the result variable. The base number, exponent, and the calculated result are then printed using System.out.println().
36. Write a program to implement a binary search tree and perform an in order traversal.
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
private Node root;
public BinarySearchTree() {
this.root = null;
}
public void insert(int data) {
root = insertRecursive(root, data);
}
private Node insertRecursive(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data) {
root.left = insertRecursive(root.left, data);
} else if (data > root.data) {
root.right = insertRecursive(root.right, data);
}
return root;
}
public void inOrderTraversal() {
inOrderTraversalRecursive(root);
}
private void inOrderTraversalRecursive(Node root) {
if (root != null) {
inOrderTraversalRecursive(root.left);
System.out.print(root.data + " ");
inOrderTraversalRecursive(root.right);
}
}
}
public class BinarySearchTreeExample {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.insert(50);
bst.insert(30);
bst.insert(20);
bst.insert(40);
bst.insert(70);
bst.insert(60);
bst.insert(80);
System.out.print("In-order traversal: ");
bst.inOrderTraversal();
}
}
Output:
In-order traversal: 20 30 40 50 60 70 80
In this Java program, a binary search tree (BST) is implemented using the BinarySearchTree class. Each node of the tree is represented by the Node class, which contains an int data value and references to its left and right child nodes.
The BinarySearchTree class has methods for inserting nodes (insert) and performing an in-order traversal (inOrderTraversal).
The insertRecursive method recursively inserts a new node with the given data into the BST. It compares the data value with the current node and decides whether to go left or right in the tree until it finds an appropriate position for insertion.
The inOrderTraversalRecursive method performs an in-order traversal of the BST recursively. It traverses the left subtree, visits the current node, and then traverses the right subtree.
In the main method, a BinarySearchTree object (bst) is created, and several nodes with different data values are inserted into the BST. The in-order traversal of the BST is then performed using the inOrderTraversal method, and the output is printed using System.out.print.
37. Write a program to find the maximum depth of a binary tree.
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
private Node root;
public BinaryTree() {
this.root = null;
}
public int maxDepth() {
return maxDepthRecursive(root);
}
private int maxDepthRecursive(Node root) {
if (root == null) {
return 0;
} else {
int leftDepth = maxDepthRecursive(root.left);
int rightDepth = maxDepthRecursive(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
}
public class MaxDepthBinaryTree {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
binaryTree.root = new Node(1);
binaryTree.root.left = new Node(2);
binaryTree.root.right = new Node(3);
binaryTree.root.left.left = new Node(4);
binaryTree.root.left.right = new Node(5);
int maxDepth = binaryTree.maxDepth();
System.out.println("Maximum Depth of the Binary Tree: " + maxDepth);
}
}
Output:
Maximum Depth of the Binary Tree: 3
In this Java program, a binary tree is implemented using the BinaryTree class. Each node of the tree is represented by the Node class, which contains an int data value and references to its left and right child nodes.
The BinaryTree class has a method maxDepth that calculates the maximum depth of the binary tree. The maxDepthRecursive method is a recursive helper function that traverses the tree and calculates the depth of each subtree. It returns the maximum depth of the left and right subtrees and adds 1 for the current node.
In the main method, a BinaryTree object (binaryTree) is created, and a binary tree is constructed with several nodes. The maxDepth method is called on the binary tree object to calculate the maximum depth of the tree. The result is then printed using System.out.println.
38. Write a program to find the first non-repeated character in a string.
package com.tech.eyes.world4u;
import java.util.HashMap;
import java.util.Map;
public class FirstNonRepeatedCharacter {
public static char findFirstNonRepeatedCharacter(String str) {
// Create a HashMap to store the frequency of each character
Map charFrequency = new HashMap<>();
// Iterate through the string and count the frequency of each character
for (char c : str.toCharArray()) {
charFrequency.put(c, charFrequency.getOrDefault(c, 0) + 1);
}
// Find the first non-repeated character
for (char c : str.toCharArray()) {
if (charFrequency.get(c) == 1) {
return c;
}
}
// If no non-repeated character found, return a default value
return '\0';
}
public static void main(String[] args) {
String str = "aabbcdeeffggh";
char firstNonRepeatedChar = findFirstNonRepeatedCharacter(str);
if (firstNonRepeatedChar != '\0') {
System.out.println("First non-repeated character: " + firstNonRepeatedChar);
} else {
System.out.println("No non-repeated character found.");
}
}
}
Output:
First non-repeated character: c
In this Java program, the findFirstNonRepeatedCharacter method takes a string (str) as input and finds the first non-repeated character in the string.
The method uses a HashMap to store the frequency of each character in the string. It iterates through the string and counts the frequency of each character by updating the corresponding entry in the charFrequency map.
Then, it iterates through the string again and checks the frequency of each character in the charFrequency map. It returns the first character with a frequency of 1, which is the first non-repeated character.
In the main method, a string (str) is given as input, and the findFirstNonRepeatedCharacter method is called with this string. If a non-repeated character is found, it is printed as output. Otherwise, a message is printed indicating that no non-repeated character is found.
39. Write a program to check if a number is a perfect number.
package com.tech.eyes.world4u;
public class PerfectNumber {
public static boolean isPerfectNumber(int number) {
if (number <= 1) {
return false;
}
int sum = 1; // Initialize sum as 1 (since 1 is a proper divisor of all numbers)
// Find all the proper divisors of the number and add them to the sum
for (int i = 2; i * i <= number; i++) {
if (number % i == 0) {
sum += i;
if (i != number / i) {
sum += number / i;
}
}
}
// Check if the sum of proper divisors is equal to the number
return sum == number;
}
public static void main(String[] args) {
int number = 28;
boolean isPerfect = isPerfectNumber(number);
if (isPerfect) {
System.out.println(number + " is a perfect number.");
} else {
System.out.println(number + " is not a perfect number.");
}
}
}
Output:
28 is a perfect number.
In this Java program, the isPerfectNumber method takes an integer (number) as input and checks if it is a perfect number.
A perfect number is a positive integer that is equal to the sum of its proper divisors (excluding the number itself). For example, 6 is a perfect number because the sum of its proper divisors (1, 2, and 3) is equal to 6.
The method checks if the input number is less than or equal to 1, in which case it returns false since 1 is not considered a perfect number.
Then, it initializes a variable sum to 1 since 1 is always a proper divisor of any number. It iterates through the numbers from 2 to the square root of the input number and checks if the number is divisible by the current iteration value (i). If it is divisible, it adds i to the sum and also adds the corresponding divisor (number / i) to the sum if it's different from i.
Finally, the method compares the sum of the proper divisors with the input number and returns true if they are equal, indicating that the number is a perfect number. Otherwise, it returns false.
In the main method, an integer (number) is given as input, and the isPerfectNumber method is called with this number. If the number is a perfect number, it is printed as output. Otherwise, a message is printed indicating that the number is not a perfect number.
40. Write a program to implement a priority queue using a heap.
package com.tech.eyes.world4u;
import java.util.Arrays;
class PriorityQueue {
private int[] heap;
private int size;
private int capacity;
public PriorityQueue(int capacity) {
this.heap = new int[capacity];
this.size = 0;
this.capacity = capacity;
}
public void insert(int value) {
if (size == capacity) {
System.out.println("Priority queue is full. Cannot insert value: " + value);
return;
}
heap[size] = value;
heapifyUp(size);
size++;
}
public int remove() {
if (isEmpty()) {
throw new IllegalStateException("Priority queue is empty. Cannot remove element.");
}
int removedValue = heap[0];
heap[0] = heap[size - 1];
size--;
heapifyDown(0);
return removedValue;
}
public boolean isEmpty() {
return size == 0;
}
private void heapifyUp(int index) {
int parent = (index - 1) / 2;
while (index > 0 && heap[parent] < heap[index]) {
swap(parent, index);
index = parent;
parent = (index - 1) / 2;
}
}
private void heapifyDown(int index) {
int maxChild;
while (index < size) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
if (leftChild < size && heap[leftChild] > heap[index]) {
maxChild = leftChild;
} else {
maxChild = index;
}
if (rightChild < size && heap[rightChild] > heap[maxChild]) {
maxChild = rightChild;
}
if (maxChild == index) {
break;
}
swap(index, maxChild);
index = maxChild;
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public void print() {
if (isEmpty()) {
System.out.println("Priority queue is empty.");
return;
}
System.out.print("Priority queue: ");
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
}
System.out.println();
}
}
package com.tech.eyes.world4u;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue priorityQueue = new PriorityQueue(10);
priorityQueue.insert(5);
priorityQueue.insert(3);
priorityQueue.insert(8);
priorityQueue.insert(1);
priorityQueue.insert(10);
priorityQueue.print();
int removedValue = priorityQueue.remove();
System.out.println("Removed value: " + removedValue);
priorityQueue.print();
}
}
Output:
Priority queue: 10 5 8 1 3
Removed value: 10
Priority queue: 8 5 3 1
In this Java program, a priority queue is implemented using a heap. The PriorityQueue class has methods to insert elements, remove elements, check if the priority queue is empty, and print the contents of the priority queue.
The insert method inserts an element into the priority queue. It first checks if the priority queue is full. If not, it adds the element to the end of the heap, performs a heapify-up operation to maintain the heap property, and increments the size.
The remove method removes and returns the highest priority element from the priority queue. It first checks if the priority queue is empty. If not, it replaces the root element with the last element in the heap, performs a heapify-down operation to maintain the heap property, decrements the size, and returns the removed value.
The isEmpty method checks if the priority queue is empty.
The heapifyUp method is used during insertion to move the inserted element up the heap until it reaches its correct position based on its priority.
The heapifyDown method is used during removal to move the new root element down the heap until it reaches its correct position based on its priority.
The swap method is a utility method to swap two elements in the heap.
The print method is used to print the contents of the priority queue.
In the main method, a PriorityQueue object is created with a capacity of 10. Several elements are inserted into the priority queue, and then the priority queue is printed. One element is removed from the priority queue, and the updated priority queue is printed again.
41. Write a program to find the longest common prefix in an array of strings.
package com.tech.eyes.world4u;
public class LongestCommonPrefix {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}
// Find the minimum length among all strings in the array
int minLength = Integer.MAX_VALUE;
for (String str : strs) {
minLength = Math.min(minLength, str.length());
}
StringBuilder prefix = new StringBuilder();
for (int i = 0; i < minLength; i++) {
char currentChar = strs[0].charAt(i);
// Check if all characters at the current index are equal across all strings
for (int j = 1; j < strs.length; j++) {
if (strs[j].charAt(i) != currentChar) {
return prefix.toString();
}
}
prefix.append(currentChar);
}
return prefix.toString();
}
public static void main(String[] args) {
String[] strings = { "flower", "flow", "flight" };
String longestPrefix = longestCommonPrefix(strings);
System.out.println("Longest common prefix: " + longestPrefix);
}
}
Output:
Longest common prefix: fl
In this Java program, the longestCommonPrefix method takes an array of strings (strs) as input and returns the longest common prefix among the strings.
The method first checks if the input array is null or empty. If so, it returns an empty string.
Then, it finds the minimum length among all the strings in the array. This is necessary because the longest common prefix cannot be longer than the shortest string in the array.
Next, it iterates over the characters at each index (from 0 to the minimum length) in the first string (strs[0]). For each character, it checks if all the other strings in the array have the same character at the corresponding index. If not, it returns the current prefix.
If all characters at the current index are equal across all strings, the current character is appended to the prefix StringBuilder.
Finally, the method returns the prefix StringBuilder converted to a string.
In the main method, an array of strings (strings) is given as input, and the longestCommonPrefix method is called with this array. The longest common prefix is then printed as output.
42. Write a program to implement a hash table.
package com.tech.eyes.world4u;
class Entry {
private final K key;
private V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
}
class HashTable {
private static final int DEFAULT_CAPACITY = 16;
private Entry[] table;
private int size;
public HashTable() {
table = new Entry[DEFAULT_CAPACITY];
size = 0;
}
public void put(K key, V value) {
int index = hash(key);
Entry entry = new Entry<>(key, value);
if (table[index] == null) {
table[index] = entry;
size++;
} else {
Entry current = table[index];
while (current != null) {
if (current.getKey().equals(key)) {
current.setValue(value);
return;
}
current = current.getNext();
}
entry.setNext(table[index]);
table[index] = entry;
size++;
}
}
public V get(K key) {
int index = hash(key);
Entry current = table[index];
while (current != null) {
if (current.getKey().equals(key)) {
return current.getValue();
}
current = current.getNext();
}
return null;
}
public void remove(K key) {
int index = hash(key);
Entry current = table[index];
Entry previous = null;
while (current != null) {
if (current.getKey().equals(key)) {
if (previous == null) {
table[index] = current.getNext();
} else {
previous.setNext(current.getNext());
}
size--;
return;
}
previous = current;
current = current.getNext();
}
}
public int size() {
return size;
}
private int hash(K key) {
return Math.abs(key.hashCode() % DEFAULT_CAPACITY);
}
}
public class Main {
public static void main(String[] args) {
HashTable hashTable = new HashTable<>();
// Insert elements into the hash table
hashTable.put("Apple", 5);
hashTable.put("Banana", 3);
hashTable.put("Cherry", 8);
hashTable.put("Mango", 10);
// Get the value for a specific key
System.out.println("Value for 'Banana': " + hashTable.get("Banana"));
// Remove an entry from the hash table
hashTable.remove("Cherry");
// Check the size of the hash table
System.out.println("Size of the hash table: " + hashTable.size());
}
}
Output:
Value for 'Banana': 3
Size of the hash table: 3
In this program, we first define the Entry class, representing an entry in the hash table. Each entry contains a key and a value.
Next, we define the HashTable class, which is the implementation of the hash table. It uses an array of Entry objects as the underlying data structure. The put method is used to insert key-value pairs into the hash table. The get method retrieves the value for a given key, and the remove method removes an entry from the hash table. The size method returns the number of entries in the hash table.
In the main method, we create an instance of the HashTable class and perform various operations on it. We insert elements with keys "Apple", "Banana", "Cherry", and "Mango" into the hash table, retrieve the value for the key "Banana", remove the entry with the key "Cherry", and finally check the size of the hash table.
43. Write a program to reverse a doubly linked list.
class Node {
int data;
Node prev;
Node next;
public Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
Node head;
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
newNode.prev = current;
}
}
public void reverse() {
if (head == null || head.next == null) {
return;
}
Node current = head;
Node temp = null;
// Swap the prev and next pointers of each node
while (current != null) {
temp = current.prev;
current.prev = current.next;
current.next = temp;
current = current.prev;
}
// Update the head pointer to the last node
if (temp != null) {
head = temp.prev;
}
}
public void display() {
Node current = head;
if (current == null) {
System.out.println("Doubly linked list is empty.");
return;
}
System.out.print("Doubly linked list: ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
}
package com.tech.eyes.world4u;
public class DoublyLinkedListExample {
public static void main(String[] args) {
DoublyLinkedList dll = new DoublyLinkedList();
dll.insert(1);
dll.insert(2);
dll.insert(3);
dll.insert(4);
dll.insert(5);
System.out.println("Before reversing:");
dll.display();
dll.reverse();
System.out.println("After reversing:");
dll.display();
}
}
Output:
Before reversing:
Doubly linked list: 1 2 3 4 5
After reversing:
Doubly linked list: 5 4 3 2 1
In this Java program, a Node class is defined to represent each node of the doubly linked list. It contains data, a reference to the previous node (prev), and a reference to the next node (next).
A DoublyLinkedList class is also defined, which contains the head pointer of the doubly linked list. It has methods to insert nodes, reverse the doubly linked list, and display the doubly linked list.
The insert method inserts a new node at the end of the doubly linked list.
The reverse method reverses the doubly linked list by swapping the prev and next pointers of each node. It starts from the head node and iterates through the list, swapping the pointers until it reaches the end. It also updates the head pointer to point to the last node after reversing.
The display method is used to print the elements of the doubly linked list.
In the main method, a DoublyLinkedList object (dll) is created, and several elements are inserted into the doubly linked list. The original doubly linked list is displayed. Then, the reverse method is called to reverse the doubly linked list. Finally, the reversed doubly linked list is displayed.
44. Write a program to find the maximum product subarray in an array.
package com.tech.eyes.world4u;
public class MaximumProductSubarray {
public static int maxProductSubarray(int[] nums) {
int n = nums.length;
// Variables to track the maximum and minimum product subarrays
int maxProduct = nums[0];
int minProduct = nums[0];
int maxResult = nums[0];
for (int i = 1; i < n; i++) {
// If the current element is negative, swap the maximum and minimum products
if (nums[i] < 0) {
int temp = maxProduct;
maxProduct = minProduct;
minProduct = temp;
}
// Update the maximum and minimum product subarrays
maxProduct = Math.max(nums[i], maxProduct * nums[i]);
minProduct = Math.min(nums[i], minProduct * nums[i]);
// Update the maximum result
maxResult = Math.max(maxResult, maxProduct);
}
return maxResult;
}
public static void main(String[] args) {
int[] nums = { 2, 3, -2, 4 };
int maxProduct = maxProductSubarray(nums);
System.out.println("Maximum product subarray: " + maxProduct);
}
}
Output:
Maximum product subarray: 6
In this Java program, the maxProductSubarray method takes an array of integers (nums) as input and returns the maximum product of a subarray within the array.
The method uses three variables to keep track of the maximum product (maxProduct), minimum product (minProduct), and the maximum result (maxResult) seen so far.
The method iterates over the array starting from the second element. For each element, it checks if the element is negative. If so, it swaps the maximum and minimum products because multiplying a negative number with the current maximum product can yield a larger product.
Then, it updates the maximum and minimum product subarrays based on the current element. It takes the maximum of the current element or the current element multiplied by the maximum product so far (maxProduct). Similarly, it takes the minimum of the current element or the current element multiplied by the minimum product so far (minProduct).
Finally, it updates the maximum result (maxResult) by taking the maximum of the maximum result and the current maximum product.
In the main method, an array of integers (nums) is given as input, and the maxProductSubarray method is called with this array. The maximum product subarray is then printed as output.
45. Write a program to check if a string is a valid palindrome using a stack.
package com.tech.eyes.world4u;
import java.util.Stack;
public class PalindromeCheck {
public static boolean isPalindrome(String str) {
// Remove non-alphanumeric characters and convert to lowercase
String cleanedStr = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
Stack stack = new Stack<>();
// Push characters onto the stack
for (char ch : cleanedStr.toCharArray()) {
stack.push(ch);
}
// Compare characters from the stack with the string
for (char ch : cleanedStr.toCharArray()) {
if (ch != stack.pop()) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String str = "A man, a plan, a canal: Panama";
boolean isPalindrome = isPalindrome(str);
System.out.println("Is the string a palindrome? " + isPalindrome);
}
}
Output:
Is the string a palindrome? true
In this Java program, the isPalindrome method takes a string (str) as input and returns true if the string is a valid palindrome and false otherwise.
The method first removes all non-alphanumeric characters from the string and converts it to lowercase using regular expressions.
It creates a stack (stack) to store the characters of the cleaned string.
It then iterates over the characters of the cleaned string and pushes each character onto the stack.
Next, it iterates over the characters of the cleaned string again and compares each character with the character popped from the stack. If there is a mismatch, it returns false as the string is not a palindrome.
If all characters match, it returns true as the string is a valid palindrome.
In the main method, a string (str) is given as input, and the isPalindrome method is called with this string. The program then prints whether the string is a palindrome or not.
46. Write a program to implement a breadth-first search (BFS) algorithm.
package com.tech.eyes.world4u;
import java.util.*;
class Graph {
private int V;
private LinkedList[] adjacencyList;
public Graph(int V) {
this.V = V;
adjacencyList = new LinkedList[V];
for (int i = 0; i < V; i++) {
adjacencyList[i] = new LinkedList<>();
}
}
public void addEdge(int v, int w) {
adjacencyList[v].add(w);
}
public void BFS(int startVertex) {
boolean[] visited = new boolean[V];
LinkedList queue = new LinkedList<>();
visited[startVertex] = true;
queue.add(startVertex);
while (queue.size() != 0) {
startVertex = queue.poll();
System.out.print(startVertex + " ");
Iterator iterator = adjacencyList[startVertex].listIterator();
while (iterator.hasNext()) {
int nextVertex = iterator.next();
if (!visited[nextVertex]) {
visited[nextVertex] = true;
queue.add(nextVertex);
}
}
}
}
}
public class BFSExample {
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
System.out.println("Breadth-First Traversal (starting from vertex 0):");
graph.BFS(0);
}
}
Output:
Breadth-First Traversal (starting from vertex 0):
0 1 2 3 4 5
In this Java program, a Graph class is defined to represent a graph data structure. It has a constructor that initializes the number of vertices (V) and an array of linked lists (adjacencyList) to store the adjacency list representation of the graph.
The addEdge method is used to add an edge between two vertices.
The BFS method implements the breadth-first search algorithm. It takes a starting vertex as input and performs the BFS traversal of the graph. It uses a boolean array (visited) to keep track of visited vertices and a queue (queue) to process the vertices in a FIFO manner.
The method starts by marking the starting vertex as visited and enqueueing it. It then enters a loop that dequeues a vertex from the queue, prints it, and enqueues all its unvisited neighbors. This process continues until the queue becomes empty.
In the main method, a Graph object (graph) is created, and several edges are added to the graph using the addEdge method. The breadth-first traversal is then performed starting from vertex 0 using the BFS method.
47. Write a program to find the kth smallest element in an array.
package com.tech.eyes.world4u;
import java.util.Arrays;
public class KthSmallestElement {
public static int findKthSmallest(int[] nums, int k) {
Arrays.sort(nums);
return nums[k - 1];
}
public static void main(String[] args) {
int[] nums = { 5, 8, 2, 9, 1 };
int k = 3;
int kthSmallest = findKthSmallest(nums, k);
System.out.println("The " + k + "th smallest element is: " + kthSmallest);
}
}
Output:
The 3rd smallest element is: 5
In this Java program, the findKthSmallest method takes an array of integers (nums) and an integer (k) as input and returns the kth smallest element in the array.
The method first sorts the array in ascending order using the Arrays.sort() method. Then, it retrieves the element at the k-1 index, as arrays are zero-indexed.
In the main method, an array of integers (nums) and an integer (k) are given as input. The findKthSmallest method is called with these inputs, and the kth smallest element is printed as output.
48. Write a program to convert a binary tree to its mirror image.
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
TreeNode root;
public BinaryTree() {
root = null;
}
public void mirror() {
mirrorHelper(root);
}
private void mirrorHelper(TreeNode node) {
if (node == null) {
return;
}
// Swap the left and right subtrees
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
// Recursively mirror the left and right subtrees
mirrorHelper(node.left);
mirrorHelper(node.right);
}
public void inorderTraversal(TreeNode node) {
if (node == null) {
return;
}
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}
}
package com.tech.eyes.world4u;
public class MirrorBinaryTree {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(1);
tree.root.left = new TreeNode(2);
tree.root.right = new TreeNode(3);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(5);
System.out.println("Original Binary Tree (Inorder Traversal):");
tree.inorderTraversal(tree.root);
tree.mirror();
System.out.println("\nMirror Binary Tree (Inorder Traversal):");
tree.inorderTraversal(tree.root);
}
}
Output:
Original Binary Tree (Inorder Traversal):
4 2 5 1 3
Mirror Binary Tree (Inorder Traversal):
3 1 5 2 4
In this Java program, we define a TreeNode class to represent each node in the binary tree. Each node has a data value, and references to its left and right child nodes.
The BinaryTree class represents the binary tree. It has a mirror method that serves as the entry point for converting the binary tree to its mirror image. The mirrorHelper method is a private helper method that recursively swaps the left and right subtrees of a given node.
The inorderTraversal method performs an inorder traversal of the binary tree to display its elements in order.
In the main method, a binary tree is created with some sample nodes. The original binary tree is displayed using inorder traversal, then the mirror method is called to convert the binary tree to its mirror image. Finally, the mirror binary tree is displayed using inorder traversal.
49. Write a program to implement a merge sort algorithm.
package com.tech.eyes.world4u;
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
int[] temp = new int[n];
mergeSortHelper(arr, temp, 0, n - 1);
}
private static void mergeSortHelper(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSortHelper(arr, temp, left, mid);
mergeSortHelper(arr, temp, mid + 1, right);
merge(arr, temp, left, mid, right);
}
}
private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k] = temp[i];
i++;
} else {
arr[k] = temp[j];
j++;
}
k++;
}
while (i <= mid) {
arr[k] = temp[i];
i++;
k++;
}
}
public static void main(String[] args) {
int[] arr = { 6, 3, 8, 5, 2 };
System.out.println("Original Array: " + Arrays.toString(arr));
mergeSort(arr);
System.out.println("Sorted Array: " + Arrays.toString(arr));
}
}
Output:
Original Array: [6, 3, 8, 5, 2]
Sorted Array: [2, 3, 5, 6, 8]
In this Java program, the mergeSort method is used to sort an array using the merge sort algorithm. It first checks if the array is null or has only one element, in which case it returns early. Otherwise, it initializes a temporary array temp and calls the mergeSortHelper method to perform the recursive merge sort on the array.
The mergeSortHelper method implements the divide-and-conquer approach of the merge sort algorithm. It recursively divides the array into smaller subarrays until each subarray has one element. Then it calls the merge method to merge and sort the subarrays.
The merge method merges two sorted subarrays into a single sorted array. It uses a temporary array temp to store the elements of the subarrays while merging them.
In the main method, an array of integers (arr) is given as input. The original array is displayed, then the mergeSort method is called to sort the array using merge sort. Finally, the sorted array is displayed.
50. Write a program to find the length of the longest increasing subarray in an array.
package com.tech.eyes.world4u;
public class LongestIncreasingSubarray {
public static int findLongestIncreasingSubarray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int maxLength = 1;
int currentLength = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
currentLength++;
} else {
maxLength = Math.max(maxLength, currentLength);
currentLength = 1;
}
}
return Math.max(maxLength, currentLength);
}
public static void main(String[] args) {
int[] nums = { 3, 1, 5, 2, 4, 7, 6, 8 };
int longestIncreasingSubarrayLength = findLongestIncreasingSubarray(nums);
System.out.println("Length of the Longest Increasing Subarray: " + longestIncreasingSubarrayLength);
}
}
Output:
Length of the Longest Increasing Subarray: 4
In this Java program, the findLongestIncreasingSubarray method takes an array of integers (nums) as input and returns the length of the longest increasing subarray.
The method iterates through the array and keeps track of the current length of the increasing subarray. If the next element is greater than the previous element, the current length is incremented. If the next element is not greater, the current length is compared with the maximum length so far (maxLength), and if it is greater, the maxLength is updated. The current length is then reset to 1, as the increasing subarray ends at that point.
In the main method, an array of integers (nums) is given as input. The findLongestIncreasingSubarray method is called with this input, and the length of the longest increasing subarray is printed as output.