Yesterdays Coding Questions

Question 1: Glass Balls Collision Problem

You are given an array of integers representing glass balls:

Positive numbers ( + ) → ball moving right

Negative numbers () → ball moving left

Collision rules:

1. When two balls moving in opposite directions collide:

The smaller ball breaks.

If equal, both break.

2. Balls moving in the same direction never collide.

Return the state of the balls after all collisions.

import java.util.*;
public class StackSimulation {
public static void main(String[] args) {
int[] arr = {5, 10, -5, -10, 8}; // Example input
int n = arr.length;

Stack<Integer> st = new Stack<>();

for (int i : arr) {

if (i > 0) {
st.push(i);
} else {
int num = Math.abs(i);
while (!st.isEmpty() && num > st.peek()) {
st.pop();
}
if (!st.isEmpty() && num == st.peek()) {
st.pop();
} else if (st.isEmpty() || num < st.peek()) {
st.push(num);
}

Yesterdays Coding Questions 1

 }
}

System.out.println("Stack size: " + st.size());

}
}

Question 2a: Rearrange Linked List (1st Version)

Problem:
Given a singly linked list:

1 → 2 → 3 → 4 → 5 → 6 → null

Rearrange it so that nodes are in this order:

1 → 6 → 2 → 5 → 3 → 4 → null

Approach:

1. Find the middle of the list.

2. Reverse the second half.

3. Merge the two halves alternately.

Java Solution (Version 1)

class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}

public class RearrangeLinkedList {

public static void reorderList1(ListNode head) {

Yesterdays Coding Questions 2

 if (head == null || head.next == null) return;

// Step 1: Find middle

ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

// Step 2: Reverse second half

ListNode prev = null, curr = slow.next;
slow.next = null;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}

// Step 3: Merge halves

ListNode first = head, second = prev;
while (second != null) {
ListNode tmp1 = first.next;
ListNode tmp2 = second.next;

first.next = second;
second.next = tmp1;

first = tmp1;
second = tmp2;
}
}

// Helper to print list

public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;

Yesterdays Coding Questions 3

 }
System.out.println("null");
}

public static void main(String[] args) {

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = new ListNode(6);

reorderList1(head);
printList(head); // Output: 1 6 2 5 3 4 null
}
}

Question 2b: Rearrange Linked List (2nd Version)

Problem:

Same input list:

1 → 2 → 3 → 4 → 5 → 6 → null

Rearrange it so that nodes are in this order:

3 → 4 → 2 → 5 → 1 → 6 → null

Approach:

Use two pointers: start and end.

Take nodes from middle outwards alternately.

This version is a bit custom and can be solved using a deque to pick nodes
from both ends.

Yesterdays Coding Questions 4

 Java Solution (Version 2)

import java.util.*;

public class RearrangeLinkedList2 {

public static void reorderList2(ListNode head) {
if (head == null) return;

// Step 1: Push all nodes into a deque

Deque<ListNode> deque = new LinkedList<>();
ListNode curr = head;
while (curr != null) {
deque.addLast(curr);
curr = curr.next;
}

// Step 2: Rebuild list from middle outwards

ListNode dummy = new ListNode(0);
ListNode node = dummy;

while (!deque.isEmpty()) {
if (!deque.isEmpty()) node.next = deque.pollFirst();
node = node.next;
if (!deque.isEmpty()) node.next = deque.pollLast();
node = node.next;
}
node.next = null; // end list

// Update original head

head.val = dummy.next.val;
head.next = dummy.next.next;
}

public static void main(String[] args) {

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);

Yesterdays Coding Questions 5

 head.next.next.next.next = new ListNode(5);
head.next.next.next.next.next = new ListNode(6);

reorderList2(head);
RearrangeLinkedList.printList(head); // Output: 3 4 2 5 1 6 null
}
}

Question 3: Beautify String

Problem:

Given a string s consisting of uppercase and lowercase letters, a string is

beautiful if:

All uppercase letters appear before any lowercase letters.

You can change the case of any character (upper → lower or lower → upper) at
a cost of 1 step per change.

Return the minimum number of steps to make the string beautiful.

Example
Input: "aAaaBB"

Output: 2

Explanation:

Convert the first 'a' to 'A' → 1 step

Convert the last 'B' to 'b' → 1 step

Total = 2 steps

Approach
1. Count the minimum operations to make each prefix all uppercase and
suffix all lowercase.

2. Iterate through string, keeping track of:

Number of lowercase letters seen so far

Yesterdays Coding Questions 6

 Number of uppercase letters remaining

3. Minimum steps = min(lowercase seen + uppercase remaining) at each split.

Java Solution

public class BeautifyString {

public static int minSteps(String s) {
int n = s.length();
int[] upperCount = new int[n + 1]; // upper letters from i to end

// Step 1: Count uppercase letters from end

for (int i = n - 1; i >= 0; i--) {
upperCount[i] = upperCount[i + 1] + (Character.isUpperCase(s.char
At(i)) ? 1 : 0);
}

int lowerSeen = 0;
int minSteps = Integer.MAX_VALUE;

// Step 2: Check every split point

for (int i = 0; i <= n; i++) {
int steps = lowerSeen + upperCount[i];
minSteps = Math.min(minSteps, steps);
if (i < n && Character.isLowerCase(s.charAt(i))) lowerSeen++;
}

return minSteps;
}

public static void main(String[] args) {

String s = "aAaaBB";
System.out.println(minSteps(s)); // Output: 2

String s2 = "AAaa";
System.out.println(minSteps(s2)); // Output: 0
}

Yesterdays Coding Questions 7

 }

✅ Explanation:
lowerSeen= number of lowercase letters in the prefix (convert to uppercase
if needed)

= number of uppercase letters in the suffix (convert to

upperCount[i]

lowercase if needed)

Sum gives total operations at that split; take minimum across all splits.

Q3.
public class MinMaxDifference {
public static int minDifference(int[] arr) {
if (arr == null || arr.length == 0) return 0;

int minVal = Integer.MAX_VALUE;

int maxVal = Integer.MIN_VALUE;

for (int num : arr) {

minVal = Math.min(minVal, num);
maxVal = Math.max(maxVal, num);
}

return maxVal - minVal;

}

4.

Problem Interpretation:

You are given an array of integers.

Each subarray (or contiguous segment) must contain at least one unique
number (i.e., not all identical).

You can change any element to any value.

Return the minimum number of changes required.

Example:

Yesterdays Coding Questions 8

 Input: [4, 4, 4, 4]
Output: 2
Explanation:
- You need at least 1 unique element in each subarray of size >1.
- Minimum 2 changes to break consecutive identical numbers: [4, x, 4, y]
→ 2 changes.

This is essentially a “make no two adjacent elements identical” problem. For

an array where all elements are the same, the minimum changes = floor(n/2).

Java Solution

public class MinChangesUniqueSubarray {

public static int minChanges(int[] arr) {
int n = arr.length;
int changes = 0;

for (int i = 1; i < n; i++) {

if (arr[i] == arr[i - 1]) {
changes++;
arr[i] = arr[i] + 1; // change to any different value
}
}
return changes;
}

public static void main(String[] args) {

int[] arr1 = {4, 4, 4, 4};
System.out.println(minChanges(arr1)); // Output: 2

int[] arr2 = {1, 2, 2, 3, 3};

System.out.println(minChanges(arr2)); // Output: 2
}
}

Yesterdays Coding Questions 9

 ✅ Explanation:
Traverse the array from left to right.

If the current element equals the previous, increment changes and modify
the current element.

This guarantees no two identical numbers are adjacent, satisfying the “at
least 1 unique per subarray” requirement.

Yesterdays Coding Questions 10