Introduction to Mid-Level Java Coding Interview Problems
Mid-level Java coding interview problems sit between the foundational "easy" challenges and the more demanding "hard" algorithm puzzles. These problems typically require a solid grasp of data structures, the ability to apply common algorithmic patterns, and the skill to articulate trade-offs clearly. You won't be asked to implement a red-black tree from scratch, but you will need to demonstrate that you can manipulate linked lists, traverse trees iteratively and recursively, apply dynamic programming to optimize naive solutions, and use hash-based structures to achieve O(n) time complexity where brute force would be O(nĀ²).
These problems are the sweet spot interviewers use to gauge whether a candidate has moved beyond textbook knowledge into practical problem-solving. They test not just whether you can write code that compiles, but whether you can recognize patterns, choose appropriate data structures, handle edge cases, and communicate your thought process under pressure.
Why Mid-Level Preparation Matters
š Deploy your AI agent in 10 minutes
Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.
Try it free →Mid-level problems form the backbone of technical interviews at most companies. Here's why focused preparation at this level is critical:
- They are the most common filter: Easy problems are often used only for phone screens. Hard problems may appear only in specialized roles or final rounds. Mid-level problems dominate the onsite and technical video interviews that determine hiring decisions.
- They reveal pattern recognition: Interviewers watch for whether you immediately spot that a problem reduces to two-sum, sliding window, topological sort, or BFS on a grid. Mid-level problems are designed to test exactly this skill.
- They expose code quality habits: At this level, interviewers scrutinize variable naming, modularization, boundary checks, null handling, and whether you write clean loops versus tangled nested logic.
- They bridge theory and practice: You need to know when a LinkedList is better than an ArrayList, when to use a TreeMap versus a HashMap, and how to articulate these choices with confidence.
Investing time in mid-level problems builds the muscle memory that makes hard problems approachable. Every hard problem is essentially a mid-level core with an additional layer of complexity.
Core Problem Categories with Complete Examples
1. Arrays and Two-Pointer Techniques
The two-pointer technique is one of the most powerful patterns for solving array problems in O(n) time with O(1) extra space. It's used for problems like removing duplicates in-place, finding pairs that satisfy a condition, or reversing segments of an array.
Problem: Remove duplicates from a sorted array in-place and return the new length.
public class ArrayProblems {
/**
* Removes duplicates in-place from a sorted array.
* Returns the length of the array containing unique elements.
* Elements beyond the returned length are ignored.
*
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
public int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// The insertIndex tracks where the next unique element should go
int insertIndex = 1;
for (int i = 1; i < nums.length; i++) {
// When we find a new unique element
if (nums[i] != nums[i - 1]) {
nums[insertIndex] = nums[i];
insertIndex++;
}
}
return insertIndex;
}
/**
* Two-pointer approach: find if there exist two elements
* in a sorted array that sum to a target value.
* Returns the indices (1-based) of the two numbers.
*/
public int[] twoSumSorted(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int currentSum = numbers[left] + numbers[right];
if (currentSum == target) {
return new int[]{left + 1, right + 1}; // 1-based indexing
} else if (currentSum < target) {
left++; // Need a larger sum, move left pointer rightward
} else {
right--; // Need a smaller sum, move right pointer leftward
}
}
// No solution found
return new int[]{-1, -1};
}
// Example usage
public static void main(String[] args) {
ArrayProblems ap = new ArrayProblems();
int[] nums = {1, 1, 2, 3, 3, 4, 5, 5};
int newLength = ap.removeDuplicates(nums);
System.out.print("After removing duplicates: ");
for (int i = 0; i < newLength; i++) {
System.out.print(nums[i] + " ");
}
// Output: 1 2 3 4 5
System.out.println();
int[] sortedNumbers = {2, 7, 11, 15};
int[] result = ap.twoSumSorted(sortedNumbers, 9);
System.out.println("Two sum indices: [" + result[0] + ", " + result[1] + "]");
// Output: [1, 2]
}
}
2. Strings and Character Manipulation
String problems at the mid-level often involve palindromes, anagrams, substring searches, or character frequency analysis. The key is choosing between StringBuilder for mutable operations, using character arrays for in-place manipulation, or leveraging hash maps for frequency counts.
Problem: Find the longest palindromic substring using the expand-around-center technique.
public class StringProblems {
/**
* Finds the longest palindromic substring in a given string.
* Uses the expand-around-center approach for O(nĀ²) time and O(1) space.
* This is more intuitive than Manacher's algorithm and sufficient for interviews.
*
* Time Complexity: O(nĀ²)
* Space Complexity: O(1) excluding the returned substring
*/
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
// Check for odd-length palindromes (single character center)
int len1 = expandFromCenter(s, i, i);
// Check for even-length palindromes (pair center)
int len2 = expandFromCenter(s, i, i + 1);
int maxLen = Math.max(len1, len2);
if (maxLen > (end - start)) {
// Calculate new start and end based on the center and length
start = i - (maxLen - 1) / 2;
end = i + maxLen / 2;
}
}
return s.substring(start, end + 1);
}
private int expandFromCenter(String s, int left, int right) {
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// Return the length of the palindrome
// Note: left and right have moved one step beyond the valid range
return right - left - 1;
}
/**
* Checks if two strings are anagrams using character frequency counting.
* Time Complexity: O(n)
* Space Complexity: O(1) ā fixed 26-character alphabet assumption
*/
public boolean areAnagrams(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] charCounts = new int[26]; // Assuming lowercase a-z only
for (int i = 0; i < s.length(); i++) {
charCounts[s.charAt(i) - 'a']++;
charCounts[t.charAt(i) - 'a']--;
}
for (int count : charCounts) {
if (count != 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
StringProblems sp = new StringProblems();
String test1 = "babad";
System.out.println("Longest palindrome in '" + test1 + "': "
+ sp.longestPalindrome(test1));
// Could output "bab" or "aba" ā both are valid
String test2 = "cbbd";
System.out.println("Longest palindrome in '" + test2 + "': "
+ sp.longestPalindrome(test2));
// Output: "bb"
System.out.println("Are 'listen' and 'silent' anagrams? "
+ sp.areAnagrams("listen", "silent"));
// Output: true
System.out.println("Are 'hello' and 'world' anagrams? "
+ sp.areAnagrams("hello", "world"));
// Output: false
}
}
3. Hash Maps and Frequency Counting
Hash maps are the go-to structure for transforming O(nĀ²) pairwise comparisons into O(n) single-pass solutions. They excel at problems involving grouping, counting, finding duplicates, or caching previously seen values.
Problem: Given an array of integers, return indices of the two numbers that add up to a target (classic Two Sum).
import java.util.*;
public class HashMapProblems {
/**
* Classic Two Sum: Find two indices whose values sum to target.
* Uses a HashMap to store value-to-index mappings for O(n) time.
*
* Time Complexity: O(n)
* Space Complexity: O(n)
*/
public int[] twoSum(int[] nums, int target) {
// Map stores: value we've seen -> its index in the array
Map seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement), i};
}
seen.put(nums[i], i);
}
throw new IllegalArgumentException("No two elements sum to the target");
}
/**
* Group anagrams from an array of strings.
* Uses a HashMap where the key is a canonical representation
* of each word (sorted characters).
*
* Time Complexity: O(n * k log k) where n is number of strings
* and k is the maximum length of a string
*/
public List> groupAnagrams(String[] strs) {
Map> groups = new HashMap<>();
for (String s : strs) {
// Create canonical key by sorting characters
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}
/**
* Find the first non-repeating character in a string
* using LinkedHashMap to preserve insertion order.
*/
public char firstNonRepeatingChar(String s) {
// Use LinkedHashMap to maintain insertion order
Map freqMap = new LinkedHashMap<>();
for (char c : s.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
for (Map.Entry entry : freqMap.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
return '_'; // Sentinel value meaning no unique character
}
public static void main(String[] args) {
HashMapProblems hp = new HashMapProblems();
int[] nums = {2, 7, 11, 15};
int[] indices = hp.twoSum(nums, 9);
System.out.println("Two Sum indices: [" + indices[0] + ", " + indices[1] + "]");
String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
List> grouped = hp.groupAnagrams(words);
System.out.println("Grouped anagrams: " + grouped);
// Output: [[eat, tea, ate], [bat], [tan, nat]]
String test = "stress";
System.out.println("First non-repeating in '" + test + "': "
+ hp.firstNonRepeatingChar(test));
// Output: 't' (s and r repeat, t appears once first)
}
}
4. Linked Lists
Linked list problems test your comfort with pointer manipulation, edge cases (empty lists, single nodes), and the critical skill of drawing out the node connections before writing code. Common patterns include the dummy head technique, fast/slow pointers, and recursive reversal.
Problem: Detect a cycle in a linked list and find the node where the cycle begins.
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class LinkedListProblems {
/**
* Detects if a linked list has a cycle using Floyd's Tortoise and Hare.
* Returns true if a cycle exists, false otherwise.
*
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // Move one step
fast = fast.next.next; // Move two steps
if (slow == fast) {
return true; // They met, so cycle exists
}
}
return false; // Fast reached null, no cycle
}
/**
* Finds the starting node of the cycle in a linked list.
* Uses Floyd's algorithm: after first meeting, reset one pointer
* to head and move both at same speed until they meet again.
*
* Time Complexity: O(n)
* Space Complexity: O(1)
*/
public ListNode detectCycleStart(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
boolean hasCycle = false;
// Phase 1: Detect cycle
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}
if (!hasCycle) {
return null;
}
// Phase 2: Find cycle start
// Reset slow to head, keep fast at meeting point
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // This is the cycle start node
}
/**
* Reverses a linked list iteratively.
* Classic interview question that tests pointer manipulation.
*/
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode nextTemp = current.next; // Save next node
current.next = prev; // Reverse the link
prev = current; // Move prev forward
current = nextTemp; // Move current forward
}
return prev; // New head of the reversed list
}
// Helper method to print a linked list (for debugging)
public void printList(ListNode head, int limit) {
ListNode current = head;
int count = 0;
while (current != null && count < limit) {
System.out.print(current.val + " -> ");
current = current.next;
count++;
}
System.out.println(count >= limit ? "..." : "null");
}
public static void main(String[] args) {
LinkedListProblems llp = new LinkedListProblems();
// Create a list: 1 -> 2 -> 3 -> 4 -> 5
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);
System.out.println("Has cycle? " + llp.hasCycle(head));
// Create a cycle: point 5's next back to 3
head.next.next.next.next.next = head.next.next; // 5 -> 3
System.out.println("Has cycle after creating loop? " + llp.hasCycle(head));
ListNode cycleStart = llp.detectCycleStart(head);
if (cycleStart != null) {
System.out.println("Cycle starts at node with value: " + cycleStart.val);
}
// Test reversal on a fresh list without cycle
ListNode freshHead = new ListNode(10);
freshHead.next = new ListNode(20);
freshHead.next.next = new ListNode(30);
System.out.println("Original list:");
llp.printList(freshHead, 10);
ListNode reversed = llp.reverseList(freshHead);
System.out.println("Reversed list:");
llp.printList(reversed, 10);
// Output: 30 -> 20 -> 10 -> null
}
}
5. Trees and Binary Search Trees
Tree problems demand comfort with recursion and iteration using stacks. You'll encounter traversal variations (inorder, preorder, postorder, level-order), tree property validation, and BST operations. The key insight for many tree problems is recognizing that recursive solutions often mirror the tree's recursive structure.
Problem: Validate if a binary tree is a valid BST and find the lowest common ancestor.
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class TreeProblems {
/**
* Validates whether a binary tree is a valid Binary Search Tree.
* Uses recursive bounds checking with null sentinels for infinity.
*
* Time Complexity: O(n) ā visits each node once
* Space Complexity: O(h) ā recursion stack height
*/
public boolean isValidBST(TreeNode root) {
return validateBST(root, null, null);
}
private boolean validateBST(TreeNode node, Integer lowerBound, Integer upperBound) {
if (node == null) {
return true; // An empty subtree is valid
}
// Check if current node's value violates bounds
if ((lowerBound != null && node.val <= lowerBound) ||
(upperBound != null && node.val >= upperBound)) {
return false;
}
// Recursively validate subtrees with updated bounds
// Left subtree: all values must be less than current node's value
// Right subtree: all values must be greater than current node's value
return validateBST(node.left, lowerBound, node.val) &&
validateBST(node.right, node.val, upperBound);
}
/**
* Finds the Lowest Common Ancestor (LCA) of two nodes in a BST.
* Leverages BST property: if both nodes are on the left, go left;
* if both are on the right, go right; otherwise, current node is LCA.
*
* Time Complexity: O(h) where h is tree height
* Space Complexity: O(1) iterative, O(h) recursive
*/
public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
TreeNode current = root;
while (current != null) {
// If both p and q are smaller, LCA must be in left subtree
if (p.val < current.val && q.val < current.val) {
current = current.left;
}
// If both p and q are larger, LCA must be in right subtree
else if (p.val > current.val && q.val > current.val) {
current = current.right;
}
// Split occurs here: one on each side, or current equals one of them
else {
return current;
}
}
return null; // Should not reach here if p and q are in the tree
}
/**
* Finds LCA in a general binary tree (not necessarily BST).
* Uses recursive post-order traversal approach.
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// If both sides returned non-null, current node is LCA
if (left != null && right != null) {
return root;
}
// Otherwise, propagate the non-null result upward
return left != null ? left : right;
}
/**
* Performs level-order (BFS) traversal of a binary tree.
* Returns a list of lists, each inner list representing one level.
*/
public List> levelOrderTraversal(TreeNode root) {
List> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(currentLevel);
}
return result;
}
public static void main(String[] args) {
TreeProblems tp = new TreeProblems();
// Build a valid BST:
// 5
// / \
// 3 7
// / \ / \
// 2 4 6 8
TreeNode root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(7);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(8);
System.out.println("Is valid BST? " + tp.isValidBST(root));
// Output: true
TreeNode lcaBST = tp.lowestCommonAncestorBST(root, root.left.left, root.left.right);
System.out.println("LCA of 2 and 4 in BST: " + lcaBST.val);
// Output: 3
TreeNode lca = tp.lowestCommonAncestor(root, root.left.left, root.right.right);
System.out.println("LCA of 2 and 8: " + lca.val);
// Output: 5
List> levels = tp.levelOrderTraversal(root);
System.out.println("Level order: " + levels);
// Output: [[5], [3, 7], [2, 4, 6, 8]]
}
}
6. Dynamic Programming (Basic to Mid-Level)
Dynamic programming (DP) transforms exponential recursive solutions into polynomial time by storing and reusing intermediate results. At the mid-level, you'll encounter classic problems like coin change, knapsack variations, longest increasing subsequence, and edit distance. The two approaches are top-down (memoization) and bottom-up (tabulation).
Problem: Coin Change ā minimum coins to make a target amount, and Longest Increasing Subsequence.
import java.util.Arrays;
public class DynamicProgrammingProblems {
/**
* Coin Change: Find the minimum number of coins needed to make
* the target amount. Returns -1 if impossible.
* Uses bottom-up DP with an array where dp[i] = min coins for amount i.
*
* Time Complexity: O(amount * coins.length)
* Space Complexity: O(amount)
*/
public int coinChange(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
// dp[i] stores the minimum coins needed to make amount i
int[] dp = new int[amount + 1];
// Fill with a value larger than any possible answer
Arrays.fill(dp, amount + 1);
dp[0] = 0; // Zero coins needed to make amount 0
// Build dp array from bottom up
for (int currentAmount = 1; currentAmount <= amount; currentAmount++) {
for (int coin : coins) {
if (coin <= currentAmount) {
// We can use this coin, then we need dp[remaining] more coins
int remaining = currentAmount - coin;
dp[currentAmount] = Math.min(dp[currentAmount], dp[remaining] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
/**
* Longest Increasing Subsequence (LIS) using DP with O(nĀ²) time.
* For each position i, we look back at all previous positions j
* and extend the LIS ending at j if nums[j] < nums[i].
*/
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// dp[i] = length of LIS ending at index i
int[] dp = new int[nums.length];
// Each element alone forms a subsequence of length 1
Arrays.fill(dp, 1);
int globalMax = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
// We can extend the subsequence ending at j
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
globalMax = Math.max(globalMax, dp[i]);
}
return globalMax;
}
/**
* 0/1 Knapsack: Given weights and values of items, and a capacity,
* find the maximum total value achievable without exceeding capacity.
* Each item can be used at most once.
*
* Time Complexity: O(n * capacity)
* Space Complexity: O(capacity) with 1D optimization
*/
public int knapsack01(int[] weights, int[] values, int capacity) {
int n = weights.length;
// dp[w] = max value achievable with capacity w
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
int itemWeight = weights[i];
int itemValue = values[i];
// Traverse backwards to avoid using the same item multiple times
for (int w = capacity; w >= itemWeight; w--) {
dp[w] = Math.max(dp[w], dp[w - itemWeight] + itemValue);
}
}
return dp[capacity];
}
public static void main(String[] args) {
DynamicProgrammingProblems dp = new DynamicProgrammingProblems();
int[] coins = {1, 2, 5};
int amount = 11;
System.out.println("Min coins for amount " + amount + ": "
+ dp.coinChange(coins, amount));
// Output: 3 (5 + 5 + 1 or 5 + 2 + 2 + 2)
int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
System.out.println("LIS length: " + dp.lengthOfLIS(nums));
// Output: 4 (subsequence: 2, 5, 7, 101 or 2, 3, 7, 101)
int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 5;
System.out.println("Max knapsack value: "
+ dp.knapsack01(weights, values, capacity));
// Output: 7 (items with weights 2 and 3, values 3+4=7)
}
}
7. Stacks and Queues
Stacks and queues are essential for problems involving parsing (valid parentheses), evaluation of expressions, monotonic sequences, and breadth-first traversals. The monotonic stack pattern, in particular, solves problems like "next greater element" in O(n) time elegantly.
Problem: Valid parentheses and implementing a stack-based queue.
import java.util.*;
public class StackQueueProblems {
/**
* Validates parentheses, brackets, and braces in a string.
* Uses a stack to match opening and closing characters.
*
* Time Complexity: O(n)
* Space Complexity: O(n) worst case (all opening brackets)
*/
public boolean isValidParentheses(String s) {
Stack stack = new Stack<>();
Map matchingPairs = new HashMap<>();
matchingPairs.put(')', '(');
matchingPairs.put('}', '{');
matchingPairs.put(']', '[');
for (char c : s.toCharArray()) {
if (matchingPairs.containsValue(c)) {
// It's an opening bracket ā push onto stack
stack.push(c);
} else if (matchingPairs.containsKey(c)) {
// It's a closing bracket ā must match top of stack
if (stack.isEmpty() || stack.pop() != matchingPairs.get(c)) {
return false;
}
}
// Ignore other characters if any
}
return stack.isEmpty(); // All brackets must be matched
}
/**
* Next Greater Element: For each element in an array, find the first
* greater element to its right. Uses a monotonic decreasing stack.
*
* Time Complexity: O(n) ā each element is pushed and popped at most once
* Space Complexity: O(n) for the result and stack
*/
public int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
// Initialize with -1 (sentinel for "no greater element")
Arrays.fill(result, -1);
// Stack stores indices of elements waiting for their next greater
Stack stack = new Stack<>();
for (int i = 0; i < n; i++) {
// While current element is greater than elements at stack indices
while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
int idx = stack.pop();
result[idx] = nums[i]; // Current element is the next greater
}
stack.push(i); // Current element waits for its next greater
}
return result;
}
/**
* Implement a Queue using two Stacks.
* Push is O(1), amortized pop/peek is O(1).
*/
static class QueueUsingStacks {
private Stack inbox; // For pushing new elements
private Stack outbox; // For popping/peeking
public QueueUsingStacks() {
inbox = new Stack<>();
outbox = new Stack<>();
}
public void push(int x) {
inbox.push(x);
}
public int pop() {
ensureOutboxHasElements();
return outbox.pop();
}
public int peek() {
ensureOutboxHasElements();
return outbox.peek();
}
public boolean empty() {
return inbox.isEmpty() && outbox.isEmpty();
}
private void ensureOutboxHasElements() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
}
}
public static void main(String[] args) {
StackQueueProblems sqp = new StackQueueProblems();
String test1 = "({[]})";
System.out.println("'" + test1 + "' valid? " + sqp.isValidParentheses(test1));
// Output: true
String test2 = "({[})]";
System.out.println("'" + test2 + "' valid? " + sqp.isValidParentheses(test2));
// Output: false
int[] nums = {4, 5, 2, 10, 8};
int[] nge = sqp.nextGreaterElement(nums);
System.out.println("Next greater elements: " + Arrays.toString(nge));
// Output: [5, 10, 10, -1, -1]
QueueUsingStacks queue = new QueueUsingStacks();
queue.push(1);
queue.push(2);
queue.push(3);
System.out.println("Queue peek: " + queue.peek()); // 1
System.out.println("Queue pop: " + queue.pop()); // 1
System.out.println("Queue pop: " + queue.pop()); // 2
queue.push(4);
System.out.println("Queue pop: " + queue.pop()); // 3
System.out.println("Queue pop: " + queue.pop()); // 4
}
}
8. Graphs ā BFS and DFS
Graph problems at the mid-level involve traversals (BFS for shortest paths in unweighted graphs, DFS for connectivity and topological sorting), cycle detection, and simple path finding. You'll represent graphs using adjacency lists or matrices and need to handle both directed and undirected cases.
Problem: Course Schedule ā detect cycles in a directed graph (topological sort via DFS).
import java.util.*;
public class GraphProblems {
/**
* Course Schedule: Determine if it's possible to complete all courses
* given prerequisites. This reduces to cycle detection in a directed graph.
* Uses DFS with three-state coloring:
* 0 = unvisited,