This page serves as a comprehensive resource for job seekers looking to excel in Java programming interviews. Building upon the success of our previous guide, Part 2 delves deeper into the realm of Java by focusing on essential programs related to string manipulation and sorting algorithms.

Make sure to visit Part 1 of this series if you haven’t already. It offers a collection of interesting programs and algorithms that I highly recommend you explore first. So, if you’re ready to embark on a comprehensive journey through the top Java programs and their solutions, let’s dive into Part 2 and build upon the knowledge you gained in Part 1.

## String Anagram

### Task

In this task, you need to write a Java program to check whether two strings are anagrams or not. An anagram is a word or phrase formed by rearranging the letters of another word or phrase.

### Task Instructions

- Ask the user to enter two strings.
- Check and display whether the entered strings are anagrams or not.

### Example

If the user enters “listen” and “silent” as the strings, the program should display the message: “The entered strings are anagrams.”

### Solution 1

To solve this task, we will compare the characters in both strings and check if they contain the same set of characters.

- Read the two strings, let’s call them
`str1`

and`str2`

, from the user. - Remove any whitespace and convert both strings to lowercase for case-insensitive comparison.
- If the lengths of the two strings are not equal, they cannot be anagrams. Display the appropriate message.
- Convert each string into a character array.
- Sort both character arrays.
- Compare the sorted arrays. If they are equal, the strings are anagrams.
- Display the result to the user.

import java.util.Arrays; import java.util.Scanner; public class StringAnagram { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print("Enter the first string: "); String str1 = input.nextLine().replaceAll("\\s", "").toLowerCase(); System.out.print("Enter the second string: "); String str2 = input.nextLine().replaceAll("\\s", "").toLowerCase(); char[] charArray1 = str1.toCharArray(); char[] charArray2 = str2.toCharArray(); Arrays.sort(charArray1); Arrays.sort(charArray2); boolean isAnagram = Arrays.equals(charArray1, charArray2); if (isAnagram) { System.out.println("The entered strings are anagrams."); } else { System.out.println("The entered strings are not anagrams."); } input.close(); } }

### Solution 2

We can also solve this task by comparing the frequency of characters in both strings to check if they contain the same set of characters.

- Read the two strings, let’s call them
`str1`

and`str2`

, from the user. - Remove any whitespace and convert both strings to lowercase for case-insensitive comparison.
- If the lengths of the two strings are not equal, they cannot be anagrams. Display the appropriate message.
- Initialize two integer arrays,
`count1`

and`count2`

, of size 26 to represent the frequencies of characters (assuming only lowercase letters are present). - Iterate through each character in
`str1`

and increment the count in`count1`

for the corresponding character. - Iterate through each character in
`str2`

and increment the count in`count2`

for the corresponding character. - Compare the values in
`count1`

and`count2`

for each index. If they are not equal, the strings are not anagrams. - Display the result to the user.

import java.util.Scanner; public class StringAnagram { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print("Enter the first string: "); String str1 = input.nextLine().replaceAll("\\s", "").toLowerCase(); System.out.print("Enter the second string: "); String str2 = input.nextLine().replaceAll("\\s", "").toLowerCase(); if (str1.length() != str2.length()) { System.out.println("The entered strings are not anagrams."); input.close(); return; } int[] count1 = new int[26]; int[] count2 = new int[26]; for (int i = 0; i < str1.length(); i++) { count1[str1.charAt(i) - 'a']++; count2[str2.charAt(i) - 'a']++; } boolean isAnagram = true; for (int i = 0; i < 26; i++) { if (count1[i] != count2[i]) { isAnagram = false; break; } } if (isAnagram) { System.out.println("The entered strings are anagrams."); } else { System.out.println("The entered strings are not anagrams."); } input.close(); } }

## The First Non-repeated Character of String

### Task

In this task, you need to write a Java program that finds the first non-repeated character in a given string. The first non-repeated character is the character that appears only once in the string.

### Task Instructions

- Ask the user to enter a string.
- Find and display the first non-repeated character in the string.

### Example

If the user enters “hello”, the program should display the message: “The first non-repeated character is ‘h’.”

### Solution 1

To solve this task, we will iterate through the characters of the string and maintain a count of each character. Then, we will identify the first character with a count of 1, indicating it is the first non-repeated character.

- Read the string from the user and store it in a variable, let’s call it
`inputString`

. - Initialize an integer array,
`charCount`

, of size 256 to represent the count of each character in the string. Set all elements to 0. - Iterate through each character in
`inputString`

using a for loop. - For each character, increment the count in
`charCount`

for the corresponding ASCII value. - Iterate through
`inputString`

again and check the count in`charCount`

for each character. - As soon as you find a character with a count of 1, that is the first non-repeated character.
- Display the first non-repeated character to the user.

import java.util.Scanner; public class FirstNonRepeatedCharacter { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print("Enter a string: "); String inputString = input.nextLine(); int[] charCount = new int[256]; for (int i = 0; i < inputString.length(); i++) { charCount[inputString.charAt(i)]++; } char firstNonRepeatedChar = '\0'; for (int i = 0; i < inputString.length(); i++) { if (charCount[inputString.charAt(i)] == 1) { firstNonRepeatedChar = inputString.charAt(i); break; } } if (firstNonRepeatedChar != '\0') { System.out.println("The first non-repeated character is '" + firstNonRepeatedChar + "'."); } else { System.out.println("There is no non-repeated character in the string."); } input.close(); } }

### Solution 2

We can also iterate through the characters of the string and check if a character repeats or not. By using a LinkedHashMap to maintain the order of character occurrences and find the first non-repeated character.

- Read the string from the user and store it in a variable, let’s call it
`inputString`

. - Initialize a LinkedHashMap,
`charCount`

, to maintain the order of character occurrences. - Iterate through each character in
`inputString`

. - For each character, check if it exists in
`charCount`

.- If it exists, increment its count by 1.
- If it doesn’t exist, add it to
`charCount`

with a count of 1.

- Iterate through the entries of
`charCount`

using a for-each loop. - Find the first entry with a value of 1, indicating it is the first non-repeated character.
- Display the first non-repeated character to the user.

import java.util.LinkedHashMap; import java.util.Map; import java.util.Scanner; public class FirstNonRepeatedCharacter { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print("Enter a string: "); String inputString = input.nextLine(); Map<Character, Integer> charCount = new LinkedHashMap<>(); for (char c : inputString.toCharArray()) { charCount.put(c, charCount.getOrDefault(c, 0) + 1); } char firstNonRepeatedChar = '\0'; for (Map.Entry<Character, Integer> entry : charCount.entrySet()) { if (entry.getValue() == 1) { firstNonRepeatedChar = entry.getKey(); break; } } if (firstNonRepeatedChar != '\0') { System.out.println("The first non-repeated character is '" + firstNonRepeatedChar + "'."); } else { System.out.println("There is no non-repeated character in the string."); } input.close(); } }

## Finding Middle Element of Linked List in One Pass

### Task

In this task, you need to write a Java program that finds the middle element of a linked list in a single pass. The middle element is the element that is located at the middle position of the linked list.

### Task Instructions

- Define a linked list data structure or use an existing implementation in Java.
- Add elements to the linked list.
- Find and display the middle element of the linked list.

### Example

If the linked list contains the elements [1, 2, 3, 4, 5], the program should display the message: “The middle element is 3.”

### Solution

To solve this task, we will use the concept of two pointers, a slow pointer and a fast pointer, moving through the linked list. The fast pointer will move at twice the speed of the slow pointer. When the fast pointer reaches the end of the list, the slow pointer will be at the middle element.

- Create a linked list data structure or use an existing implementation in Java.
- Add elements to the linked list.
- Initialize two pointers,
`slow`

and`fast`

, and set them both to the head of the linked list. - Traverse the linked list using the two pointers, with
`fast`

moving two steps at a time and`slow`

moving one step at a time. - Keep moving the pointers until the fast pointer reaches the end of the list.
- At each step, move the slow pointer to the next node and the fast pointer to the next two nodes.
- When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle element.
- Display the middle element to the user.

public class LinkedList { private static class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; } } private Node head; public void add(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node currentNode = head; while (currentNode.next != null) { currentNode = currentNode.next; } currentNode.next = newNode; } } public int findMiddleElement() { if (head == null) { throw new IllegalStateException("Linked list is empty."); } Node slow = head; Node fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow.data; } public static void main(String[] args) { LinkedList list = new LinkedList(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); int middleElement = list.findMiddleElement(); System.out.println("The middle element is " + middleElement + "."); } }

## Pre-order Traversal

### Task

In this task, you need to write a Java program that performs a pre-order traversal on a binary tree. Pre-order traversal visits the nodes of the tree in the order: root, left subtree, right subtree.

### Task Instructions

- Define a binary tree data structure or use an existing implementation in Java.
- Create a binary tree by adding nodes and establishing the relationships between them.
- Perform a pre-order traversal on the binary tree.
- Display the visited nodes in the pre-order traversal order.

### Example

Consider the binary tree:

1 / \ 2 3 / \ 4 5

The pre-order traversal will visit the nodes in the order: 1, 2, 4, 5, 3.

### Solution

To solve this task, we will use recursive programming to implement the pre-order traversal algorithm for a binary tree.

- Define a binary tree data structure or use an existing implementation in Java.
- Create a binary tree by adding nodes and establishing the relationships between them.
- Implement a recursive function, let’s call it
`preorderTraversal`

, that takes a node as a parameter and performs the pre-order traversal on the binary tree. - In the
`preorderTraversal`

function:- Check if the current node is null. If so, return.
- Display the data of the current node.
- Recursively call
`preorderTraversal`

on the left subtree of the current node. - Recursively call
`preorderTraversal`

on the right subtree of the current node.

- Invoke the
`preorderTraversal`

function on the root of the binary tree to initiate the pre-order traversal.

class Node { int data; Node left; Node right; Node(int data) { this.data = data; this.left = null; this.right = null; } } public class BinaryTree { Node root; public void preorderTraversal(Node node) { if (node == null) { return; } System.out.print(node.data + " "); preorderTraversal(node.left); preorderTraversal(node.right); } public static void main(String[] args) { BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); System.out.print("Pre-order traversal: "); tree.preorderTraversal(tree.root); } }

## Sort Array Using Quicksort

### Task

In this task, you need to write a Java program that sorts an array using the QuickSort algorithm. QuickSort is a popular sorting algorithm that follows the divide-and-conquer approach.

### Task Instructions

- Define an array of integers or take input from the user.
- Implement the QuickSort algorithm to sort the array.
- Display the sorted array as output.

### Example

Consider an array: [9, 5, 2, 7, 3] The program should display the sorted array: [2, 3, 5, 7, 9]

### Solution

To solve this task, we will implement the QuickSort algorithm recursively.

- Implement a recursive function, let’s call it
`quickSort`

, that takes an array and the indices of the first and last elements as parameters. - Choose a pivot element from the array (e.g., the last element).
- Partition the array into two parts:
- All elements smaller than the pivot element will be on the left side.
- All elements greater than the pivot element will be on the right side.

- Recursively call
`quickSort`

on the left and right partitions separately. - Combine the sorted left partition, pivot element, and sorted right partition to get the final sorted array.

public class QuickSort { public void quickSort(int[] arr, int low, int high) { if (low < high) { int partitionIndex = partition(arr, low, high); quickSort(arr, low, partitionIndex - 1); quickSort(arr, partitionIndex + 1, high); } } private int partition(int[] arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, high); return i + 1; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = {9, 5, 2, 7, 3}; QuickSort quickSort = new QuickSort(); quickSort.quickSort(arr, 0, arr.length - 1); System.out.print("Sorted array: "); for (int num : arr) { System.out.print(num + " "); } } }

## Insertion Sort

### Task

In this task, you need to write a Java program that sorts an array using the Insertion Sort algorithm. Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time.

### Task Instructions

- Define an array of integers or take input from the user.
- Implement the Insertion Sort algorithm to sort the array.
- Display the sorted array as output.

### Example

Consider an array: [9, 5, 2, 7, 3] The program should display the sorted array: [2, 3, 5, 7, 9]

### Solution

To solve this task, we will implement the Insertion Sort algorithm.

- Start with the second element of the array.
- Iterate through the array, starting from the second element.
- Compare the current element with the elements on its left side.
- Move the elements greater than the current element to the right by one position.
- Insert the current element into the correct position in the sorted subarray on the left side.
- Repeat steps 2-5 until all elements are in their correct positions.

public class InsertionSort { public void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } public static void main(String[] args) { int[] arr = {9, 5, 2, 7, 3}; InsertionSort insertionSort = new InsertionSort(); insertionSort.insertionSort(arr); System.out.print("Sorted array: "); for (int num : arr) { System.out.print(num + " "); } } }

## Bubble Sort

### Task

In this task, you need to write a Java program that sorts an array using the Bubble Sort algorithm. Bubble Sort is a simple sorting algorithm that repeatedly steps through the array, compares adjacent elements, and swaps them if they are in the wrong order.

### Task Instructions

- Define an array of integers or take input from the user.
- Implement the Bubble Sort algorithm to sort the array.
- Display the sorted array as output.

### Example

Consider an array: [9, 5, 2, 7, 3] The program should display the sorted array: [2, 3, 5, 7, 9]

### Solution

To solve this task, we will implement the Bubble Sort algorithm.

- Start with the first element of the array.
- Iterate through the array, comparing adjacent elements.
- If the elements are in the wrong order, swap them.
- Repeat steps 2-3 until the array is fully sorted (no more swaps are needed).

public class BubbleSort { public void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { 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; } } } } public static void main(String[] args) { int[] arr = {9, 5, 2, 7, 3}; BubbleSort bubbleSort = new BubbleSort(); bubbleSort.bubbleSort(arr); System.out.print("Sorted array: "); for (int num : arr) { System.out.print(num + " "); } } }

## Print All Permutations of String

### Task

In this task, you need to write a Java program that prints all permutations of a given string. A permutation is an arrangement of characters in a specific order.

### Task Instructions

- Take a string as input from the user or define a string.
- Implement a function to print all permutations of the string.
- Display the permutations as output.

### Example

Consider the string: “abc” The program should display the permutations: “abc”, “acb”, “bac”, “bca”, “cab”, “cba”

### Solution

To solve this task, we will implement a recursive algorithm to generate all permutations of the given string.

- Implement a recursive function, let’s call it
`permute`

, that takes the string, a starting index, and an ending index as parameters. - If the starting index is equal to the ending index, print the string as a permutation.
- Iterate from the starting index to the ending index:
- Swap the characters at the starting index and the current index.
- Recursively call the
`permute`

function with the starting index incremented by 1. - Swap the characters back to their original positions for backtracking.

- In the main method, call the
`permute`

function with the string, the starting index set to 0, and the ending index set to the length of the string minus 1.

public class Permutations { public void permute(String str, int start, int end) { if (start == end) { System.out.println(str); } else { for (int i = start; i <= end; i++) { str = swap(str, start, i); permute(str, start + 1, end); str = swap(str, start, i); } } } private String swap(String str, int i, int j) { char[] charArray = str.toCharArray(); char temp = charArray[i]; charArray[i] = charArray[j]; charArray[j] = temp; return String.valueOf(charArray); } public static void main(String[] args) { String str = "abc"; Permutations permutations = new Permutations(); permutations.permute(str, 0, str.length() - 1); } }

## Reverse a Linked List

### Task

In this task, you need to write a Java program that reverses a given linked list. A linked list is a data structure consisting of a sequence of nodes, where each node contains a value and a reference to the next node.

### Task Instructions

- Define a linked list by creating a Node class with a value and next pointer/reference.
- Implement a function to reverse the linked list.
- Display the reversed linked list as output.

### Example

Consider a linked list: 1 -> 2 -> 3 -> 4 The program should display the reversed linked list: 4 -> 3 -> 2 -> 1

### Solution

To solve this task, we will implement an iterative algorithm to reverse the linked list.

- Define a Node class with a value and next pointer/reference.
- Implement a function, let’s call it
`reverseLinkedList`

, that takes the head node of the linked list as a parameter. - Initialize three pointers,
`current`

pointing to the head,`previous`

pointing to null, and`next`

pointing to null. - Iterate through the linked list:
- Set
`next`

to the next node of the current node. - Update the next reference of the current node to point to the previous node.
- Move the previous and current pointers one step forward.
- Move the current pointer to the next node.

- Set
- Set the head pointer to the previous node, which will be the new head of the reversed linked list.

public class LinkedList { static class Node { int value; Node next; Node(int value) { this.value = value; } } public Node reverseLinkedList(Node head) { Node previous = null; Node current = head; Node next; while (current != null) { next = current.next; current.next = previous; previous = current; current = next; } return previous; } public static void main(String[] args) { LinkedList linkedList = new LinkedList(); Node head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); head.next = second; second.next = third; third.next = fourth; System.out.println("Original linked list:"); linkedList.printLinkedList(head); Node reversedHead = linkedList.reverseLinkedList(head); System.out.println("Reversed linked list:"); linkedList.printLinkedList(reversedHead); } public void printLinkedList(Node head) { Node current = head; while (current != null) { System.out.print(current.value + " "); current = current.next; } System.out.println(); } }

## Find The Length of The Linked List

### Task

In this task, you need to write a Java program that finds the length of a given linked list. The length of a linked list is the number of nodes it contains.

### Task Instructions

- Define a linked list by creating a Node class with a value and next pointer/reference.
- Implement a function to find the length of the linked list.
- Display the length of the linked list as output.

### Example

Consider a linked list: 1 -> 2 -> 3 -> 4 The program should display the length of the linked list: 4

### Solution

To solve this task, we will implement an iterative algorithm to find the length of the linked list.

- Define a Node class with a value and next pointer/reference.
- Implement a function, let’s call it
`findLinkedListLength`

, that takes the head node of the linked list as a parameter. - Initialize a counter variable,
`length`

, to 0. - Iterate through the linked list:
- Increment the
`length`

by 1 for each node visited. - Move to the next node.

- Increment the
- Return the
`length`

as the length of the linked list.

public class LinkedList { static class Node { int value; Node next; Node(int value) { this.value = value; } } public int findLinkedListLength(Node head) { int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length; } public static void main(String[] args) { LinkedList linkedList = new LinkedList(); Node head = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); head.next = second; second.next = third; third.next = fourth; int length = linkedList.findLinkedListLength(head); System.out.println("Length of the linked list: " + length); } }

## Bucket Sort

### Task

In this task, you need to write a Java program that sorts an array using the Bucket Sort algorithm. Bucket Sort is a sorting algorithm that divides the input into separate buckets and then sorts each bucket individually, either using a different sorting algorithm or recursively applying the bucket sort algorithm.

### Task Instructions

- Take an array of integers as input from the user or define an array.
- Implement a function to sort the array using the Bucket Sort algorithm.
- Display the sorted array as output.

### Example

Consider an array: [29, 25, 10, 8, 14, 9] The program should display the sorted array: [8, 9, 10, 14, 25, 29]

### Solution

To solve this task, we will implement the Bucket Sort algorithm for sorting the array of integers.

- Implement a function, let’s call it
`bucketSort`

, that takes the array of integers as a parameter. - Find the minimum and maximum values in the array to determine the range of values.
- Create an array of buckets, where each bucket represents a specific range of values.
- Iterate through the input array and distribute the elements into the respective buckets based on their value range.
- Sort each individual bucket using a sorting algorithm (e.g., Insertion Sort).
- Concatenate the sorted buckets to obtain the final sorted array.
- Return the sorted array.

import java.util.ArrayList; import java.util.Collections; public class BucketSort { public void bucketSort(int[] array) { int minVal = array[0]; int maxVal = array[0]; int n = array.length; for (int i = 1; i < n; i++) { if (array[i] < minVal) { minVal = array[i]; } else if (array[i] > maxVal) { maxVal = array[i]; } } int numBuckets = (maxVal - minVal) / n + 1; ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(numBuckets); for (int i = 0; i < numBuckets; i++) { buckets.add(new ArrayList<>()); } for (int i = 0; i < n; i++) { int bucketIndex = (array[i] - minVal) / n; buckets.get(bucketIndex).add(array[i]); } int currentIndex = 0; for (int i = 0; i < numBuckets; i++) { Collections.sort(buckets.get(i)); for (int j = 0; j < buckets.get(i).size(); j++) { array[currentIndex++] = buckets.get(i).get(j); } } } public static void main(String[] args) { BucketSort bucketSort = new BucketSort(); int[] array = {29, 25, 10, 8, 14, 9}; System.out.println("Original Array:"); bucketSort.printArray(array); bucketSort.bucketSort(array); System.out.println("Sorted Array:"); bucketSort.printArray(array); } public void printArray(int[] array) { for (int i : array) { System.out.print(i + " "); } System.out.println(); } }

## Conclusion

In conclusion, this page has provided an insightful guide to the top Java programs commonly encountered in job interviews, focusing on string manipulation and sorting algorithms, these algorithms not only demonstrate your proficiency in Java but also showcase your problem-solving skills.

By mastering these programs, you will be well-equipped to tackle job interviews with confidence. Do not forget to check out the Java Interview Questions page for more similar content. Good luck on your Java coding journey!