1.Array rotation
- Problem: Rotate an array to the right by k steps.
- Solution: Use a temporary array to store elements and shift them to their new positions.
import java.util.Arrays;
public class ArrayRotation {
// Function to rotate array to the
right by k steps
public static void rotateArray(int[] nums, int k)
{
if (nums == null || nums.length == 0 || k == 0)
{
return;
}
int n = nums.length;
k = k % n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
// Function to reverse the array within the
given range
public static void reverse(int[] nums,
int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
// Main method to test the rotation function
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6, 7};
int k = 3;
System.out.println("Original Array: "
+ Arrays.toString(nums));
rotateArray(nums, k);
System.out.println("Array rotated by "
+ k + " steps: " + Arrays.toString(nums));
}
}
2.Find the missing number in a given integer array of 1 to 100
- Problem: Find the missing number in a sequence of integers from 1 to 100.
- Solution: Calculate the sum of the sequence and find the missing number by subtracting the sum of the given array from the sum of the sequence.
public class FindMissingNumber {
public static void main(String[] args) {
// Given array with one missing number
int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51, 52, 53, 54, 55, 56, 57, 58, 59, 60,
61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
71, 72, 73, 74, 75, 76, 77, 78, 79, 80,
81, 82, 83, 84, 85, 86, 87, 88, 89, 90,
91, 92, 93, 94, 95, 96, 97, 98, 99, 100};
int missingNumber = findMissingNumber(array);
System.out.println("The missing number is: "
+ missingNumber);
}
// Function to find the missing number in
the given array
public static int findMissingNumber(int[] array) {
int n = array.length + 1;
int totalSum = n * (n + 1) / 2;
int arraySum = 0;
for (int num : array) {
arraySum += num;
}
return totalSum - arraySum;
}
}
3.Sort an array of 0s, 1s, and 2s
- Problem: Sort an array containing only 0s, 1s, and 2s without using any sorting algorithm.
- Solution: Use the Dutch National Flag algorithm to partition the array into three sections.
public class SortArrayOfZeroOneTwo {
public static void sortArray(int[] nums) {
int low = 0;
int high = nums.length - 1;
int mid = 0, temp = 0;
while (mid <= high) {
switch (nums[mid]) {
case 0: {
temp = nums[low];
nums[low] = nums[mid];
nums[mid] = temp;
low++;
mid++;
break;
}
case 1:
mid++;
break;
case 2: {
temp = nums[mid];
nums[mid] = nums[high];
nums[high] = temp;
high--;
break;
}
}
}
}
public static void main(String[] args) {
int[] nums = {0, 1, 2, 1, 0, 2, 1, 0, 2, 0, 1};
System.out.println("Original Array: "
+ java.util.Arrays.toString(nums));
sortArray(nums);
System.out.println("Sorted Array: "
+ java.util.Arrays.toString(nums));
}
}
4.Reverse an array
- Problem: Reverse an array of integers.
- Solution: Use two pointers to swap elements from the beginning and end of the array.
import java.util.Arrays;
public class ReverseArray {
public static void reverseArray(int[] arr) {
int start = 0;
int end = arr.length - 1;
int temp;
while (start < end) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5};
System.out.println("Original Array: "
+ Arrays.toString(array));
reverseArray(array);
System.out.println("Reversed Array: "
+ Arrays.toString(array));
}
}
5.Implement a stack using an array
- Problem: Implement a stack data structure using an array.
- Solution: Use an array and keep track of the top element.
public class Stack {
private int maxSize;
private int[] stackArray;
private int top;
public Stack(int size) {
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}
public void push(int value) {
if (top < maxSize - 1) {
stackArray[++top] = value;
System.out.println("Pushed element:
" + value);
} else {
System.out.println
("Stack is full. Cannot push " + value);
}
}
public int pop() {
if (top >= 0) {
int value = stackArray[top--];
System.out.println
("Popped element: " + value);
return value;
} else {
System.out.println
("Stack is empty. Cannot pop");
return -1;
}
}
public int peek() {
if (top >= 0) {
return stackArray[top];
} else {
System.out.println
("Stack is empty. No element to peek");
return -1;
}
}
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(1);
stack.push(2);
stack.push(3);
stack.pop();
System.out.println("Top element: "
+ stack.peek());
System.out.println("Is the stack empty? "
+ stack.isEmpty());
System.out.println("Is the stack full? "
+ stack.isFull());
}
}
6.Implement a queue using an array
- Problem: Implement a queue data structure using an array.
- Solution: Use an array and maintain pointers for the front and rear elements.
public class Queue {
private int maxSize;
private int[] queueArray;
private int front;
private int rear;
private int currentSize;
public Queue(int size) {
maxSize = size;
queueArray = new int[maxSize];
front = 0;
rear = -1;
currentSize = 0;
}
public void enqueue(int value) {
if (!isFull()) {
rear = (rear + 1) % maxSize;
queueArray[rear] = value;
currentSize++;
System.out.println("Enqueued element:
" + value);
} else {
System.out.println
("Queue is full. Cannot enqueue " + value);
}
}
public int dequeue() {
if (!isEmpty()) {
int temp = queueArray[front];
front = (front + 1) % maxSize;
currentSize--;
System.out.println
("Dequeued element: " + temp);
return temp;
} else {
System.out.println
("Queue is empty. Cannot dequeue");
return -1;
}
}
public int peek() {
if (!isEmpty()) {
return queueArray[front];
} else {
System.out.println
("Queue is empty. No element to peek");
return -1;
}
}
public boolean isEmpty() {
return (currentSize == 0);
}
public boolean isFull() {
return (currentSize == maxSize);
}
public static void main(String[] args) {
Queue queue = new Queue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue();
System.out.println
("Front element: " + queue.peek());
System.out.println
("Is the queue empty? " + queue.isEmpty());
System.out.println
("Is the queue full? " + queue.isFull());
}
}
7.Find the intersection point of two linked lists
- Problem: Find the node at which two linked lists intersect.
- Solution: Find the lengths of the two lists, align the starting points, and then iterate to find the intersection.
// Node class for the linked list
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class IntersectionLinkedLists {
// Function to find the
intersection point of two linked lists
public static Node getIntersectionNode
(Node headA, Node headB) {
if (headA == null || headB == null) {
return null;
}
Node a = headA;
Node b = headB;
while (a != b) {
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
public static void main(String[] args) {
// Creating the first linked list
Node node1 = new Node(3);
Node node2 = new Node(6);
Node node3 = new Node(9);
Node node4 = new Node(15);
Node node5 = new Node(30);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
// Creating the second linked list
Node node6 = new Node(10);
node6.next = node4;
Node intersectionNode = getIntersectionNode
(node1, node6);
if
(intersectionNode != null) {
System.out.println
("Intersection point of the two
linked lists is: " + intersectionNode.data);
} else {
System.out.println
("No intersection point found.");
}
}
}
8.Reverse a linked list
- Problem: Reverse a singly linked list.
- Solution: Traverse the list, reversing the links between nodes.
// Node class for the linked list
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class ReverseLinkedList {
// Function to reverse the linked list
public static Node reverseList(Node head) {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// Function to print the linked list
public static void printList(Node head) {
Node current = head;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
// Creating a sample linked list
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:");
printList(head);
Node reversedHead = reverseList(head);
System.out.println("Reversed linked list:");
printList(reversedHead);
}
}
9.Detect a cycle in a linked list
- Problem: Determine if a linked list has a cycle.
- Solution: Use the slow and fast pointer approach to detect a cycle in the linked list.
// Node class for the linked list
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class DetectCycleLinkedList {
// Function to detect a cycle in a linked list
public static boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
public static void main(String[] args) {
ListNode head = new ListNode(3);
ListNode node1 = new ListNode(2);
ListNode node2 = new ListNode(0);
ListNode node3 = new ListNode(-4);
head.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node1; // creating a cycle
boolean hasCycle = hasCycle(head);
if (hasCycle) {
System.out.println
("The linked list has a cycle.");
} else {
System.out.println
("The linked list does not have a cycle.");
}
}
}
10.Find the nth node from the end in a linked list
- Problem: Find the nth node from the end of a singly linked list.
- Solution: Use two pointers with a distance of n between them.
// Node class for the linked list
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class NthNodeFromEndLinkedList {
// Function to find the nth node from the end
of a linked list
public static ListNode findNthFromEnd
(ListNode head, int n) {
if (head == null || n <= 0) {
return null;
}
ListNode fast = head;
ListNode slow = head;
for (int i = 0; i < n; i++) {
if (fast == null) {
return null;
}
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
public static void main(String[] args) {
ListNode head = new ListNode(1);
ListNode node1 = new ListNode(2);
ListNode node2 = new ListNode(3);
ListNode node3 = new ListNode(4);
ListNode node4 = new ListNode(5);
head.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
int n = 2; // Find the 2nd node from the end
ListNode nthNode = findNthFromEnd(head, n);
if (nthNode != null) {
System.out.println("The " + n
+ "th node from the end is: " + nthNode.val);
} else {
System.out.println("The list is too
short or n is not valid.");
}
}
}
