In part-8 of our series on challenging Java programs and succeeding in coding interviews, we will be tackling a variety of programming problems with detailed descriptions of the solutions.
By mastering these types of problems, you can improve your chances of success in technical interviews and develop your Java programming skills further. Join us as we explore some of the most challenging Java programs and work towards finding effective solutions.
Write a program to reverse a singly linked list in Java
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
void add(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
return;
}
Node currNode = head;
while (currNode.next != null) {
currNode = currNode.next;
}
currNode.next = newNode;
}
void printList() {
Node currNode = head;
while (currNode != null) {
System.out.print(currNode.data + " ");
currNode = currNode.next;
}
System.out.println();
}
void reverse() {
Node prevNode = null;
Node currNode = head;
Node nextNode = null;
while (currNode != null) {
nextNode = currNode.next;
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
}
head = prevNode;
}
}
class JavaTechypid {
public static void main(String[] args) {
LinkedList list = new LinkedList();
for (int i = 1; i <= 10; i++) {
list.add(i);
}
System.out.println("Original List:");
list.printList();
list.reverse();
System.out.println("Reversed List:");
list.printList();
}
}
Output:
Original List:
1 2 3 4 5 6 7 8 9 10
Reversed List:
10 9 8 7 6 5 4 3 2 1
Explanation Of Above Java Code:
In this program, we first define a Node class to represent the nodes of the linked list. Each node has an integer value and a reference to the next node in the list.
We then define a LinkedList class that has a head reference to the first node in the list.
This class has methods to add a new node to the end of the list (add()), print the contents of the list (printList()), and reverse the list (reverse()).
To reverse the list, we start with three references: prevNode, currNode, and nextNode.
We initialize prevNode to null, currNode to the first node (head), and nextNode to null.
We then iterate through the list, updating the next reference of the current node to point to the previous node (prevNode).
We then update prevNode to be the current node, currNode to be the next node (nextNode), and nextNode to be the node after currNode.
We continue this process until currNode is null, at which point we set head to prevNode to make it the new first node in the reversed list.
Finally, we print the reversed list using the printList() method.
Write a program to implement a binary search in Java
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;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // target not found
}
Explanation Of Above Java Code:
This implementation takes an array of integers arr and a target value target.
It initializes two pointers, left and right, to the first and last indices of the array, respectively.
The while loop runs as long as the left pointer is less than or equal to the right pointer.
In each iteration of the loop, the mid index is computed as the average of the left and right indices.
If the value at the mid index equals the target value, we’ve found the element we’re looking for and return its index.
If the value at the mid index is less than the target value, we adjust the left pointer to be one index higher than mid.
If the value at the mid index is greater than the target value, we adjust the right pointer to be one index lower than mid.
If the loop exits without finding the target value, we return -1 to indicate that the value was not found in the array.
Write a Java program that illustrates merge sort in java.
public class JavaTechypid {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
mergeSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void mergeSort(int[] arr, int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
}
public static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp[k] = arr[i];
i++;
} else {
temp[k] = arr[j];
j++;
}
k++;
}
while (i <= mid) {
temp[k] = arr[i];
i++;
k++;
}
while (j <= high) {
temp[k] = arr[j];
j++;
k++;
}
for (k = 0; k < temp.length; k++) {
arr[low + k] = temp[k];
}
}
}
Output:
1 2 3 4 5 6 7 8
Explanation Of Above Java Code:
The mergeSort method takes an array of integers as input and recursively splits it into two halves until there is only one element in each half.
Then, it calls the merge method to merge the two halves in sorted order.
The merge method creates a temporary array and compares the elements of the two halves to merge them into the temporary array in sorted order.
Finally, the temporary array is copied back into the original array.
In the main method, an array of integers is created and filled with random numbers.
The unsorted array is printed to the console, and then the mergeSort method is called to sort the array.
The sorted array is then printed to the console.
Write a Java program that sorts HashMap by value
import java.util.*;
public class JavaTechypid {
public static void main(String[] args) {
// Create a HashMap
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 2);
map.put("cherry", 8);
map.put("date", 3);
// Convert HashMap to List
List<Map.Entry<String, Integer>> list = new ArrayList<>(map.entrySet());
// Sort list by value
Collections.sort(list, new Comparator<Map.Entry<String, Integer>>() {
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
return o1.getValue().compareTo(o2.getValue());
}
});
// Create a LinkedHashMap to maintain insertion order
Map<String, Integer> sortedMap = new LinkedHashMap<>();
// Put sorted entries into sortedMap
for (Map.Entry<String, Integer> entry : list) {
sortedMap.put(entry.getKey(), entry.getValue());
}
// Print sortedMap
System.out.println("Sorted HashMap by value: " + sortedMap);
}
}
Output:
Sorted HashMap by value: {banana=2, date=3, apple=5, cherry=8}
Explanation Of Above Java Code:
Here, the HashMap is sorted by the values of its entries in ascending order.
In this program, we first create a HashMap and add some key-value pairs to it.
Then, we convert the HashMap to a List using ArrayList constructor, which takes a Collection as an argument.
We pass the entrySet() method of the HashMap to the constructor to get a Set of Map.Entry objects, each representing a key-value pair in the HashMap.
Next, we use the Collections.sort() method to sort the List by value. To do this, we pass a Comparator object that compares Map.Entry objects by their values.
The compare() method of the Comparator object returns a negative integer, zero, or a positive integer, depending on whether the first argument is less than, equal to, or greater than the second argument.
After sorting the List, we create a LinkedHashMap to maintain the insertion order of the sorted entries.
We iterate over the sorted entries and put them into the LinkedHashMap.