Java Progressive Coding Master Bank (25 Algorithmic Questions)
25 practical Java coding interview challenges complete with optimal solutions, algorithmic explanations, space/time complexity analysis, and interactive knowledge check quizzes.
Q1: How do you reverse a String in-place without built-in reverse functions?
Strings in Java are immutable, so to reverse a String in-place, convert it to a char[] array and use the Two-Pointer Technique. Initialize pointers at both ends of the array, swap characters, and move the pointers toward the center until they meet.
public class StringReversal {
public static String reverse(String input) {
if (input == null || input.length() <= 1) return input;
char[] chars = input.toCharArray();
int left = 0, right = chars.length - 1;
while (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
return new String(chars);
}
}- Strings are immutable in Java; convert to
char[]for swapping. - Two-pointer technique yields $O(n)$ time and $O(n)$ space complexity.
What is the time complexity of reversing a string of length N using the two-pointer approach on a char array?
Q2: How do you check if a String is a Palindrome (ignoring non-alphanumeric characters)?
Use two pointers (left at index 0, right at index len - 1). Increment left and decrement right past non-alphanumeric characters (Character.isLetterOrDigit), and compare lowercased characters.
public class ValidPalindrome {
public static boolean isPalindrome(String s) {
if (s == null) return false;
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
}- Filter non-alphanumeric characters dynamically using
Character.isLetterOrDigit(). - Runs in $O(n)$ time with $O(1)$ auxiliary space.
Why is scanning inward with Character.isLetterOrDigit preferred over s.replaceAll("[^a-zA-Z0-9]", "")?
Q3: How do you verify if two Strings are Anagrams?
Two strings are anagrams if they contain the exact same character frequencies. Check if lengths are equal first. Count character occurrences using a fixed-size integer frequency array (int[26] for lowercase English letters) or a HashMap for general Unicode.
public class ValidAnagram {
public static boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] counts = new int[26];
for (int i = 0; i < s.length(); i++) {
counts[s.charAt(i) - 'a']++;
counts[t.charAt(i) - 'a']--;
}
for (int count : counts) {
if (count != 0) return false;
}
return true;
}
}- Use
int[26]array as a fast frequency map for ASCII alphabets. - Increment count for string 1, decrement for string 2; verify all entries equal 0.
What is the space complexity of checking anagrams of lower-case ASCII strings using a fixed int[26] array?
Q4: How do you solve the Two Sum problem in O(n) time?
Given an array of integers and a target sum, return the indices of two numbers that add up to target. Use a HashMap<Integer, Integer> storing (value -> index). Iterate through the array once, computing complement = target - nums[i]. If complement exists in map, return current index and stored complement index.
import java.util.HashMap;
import java.util.Map;
public class TwoSum {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}- HashMap provides $O(1)$ lookup time for target complements.
- Achieves $O(n)$ time complexity in a single pass.
What is the time complexity of finding a Two Sum pair using a Hash Table?
Q5: How do you find the first non-repeating character in a String?
Perform two passes over the string. Pass 1: Build a character frequency map (int[256] or LinkedHashMap). Pass 2: Iterate through the string from left to right; return the index of the first character whose frequency count equals 1.
public class FirstUniqueChar {
public static int firstUniqChar(String s) {
int[] freq = new int[256];
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i)]++;
}
for (int i = 0; i < s.length(); i++) {
if (freq[s.charAt(i)] == 1) return i;
}
return -1;
}
}- Pass 1 counts character frequencies.
- Pass 2 preserves input ordering to identify the first unique character index.
Why does a second iteration over the string s (rather than iterating over the frequency array) guarantee finding the FIRST non-repeating character?
Q6: How do you find the single missing number in an array containing numbers 0 to n?
Use Gauss's Sum Formula: expected sum $S = frac{n(n + 1)}{2}$. Calculate the actual sum of array elements and subtract it from $S$. Alternatively, use XOR: $x oplus x = 0$, XORing indices and values leaves the missing number.
public class MissingNumber {
public static int findMissing(int[] nums) {
int xor = nums.length;
for (int i = 0; i < nums.length; i++) {
xor ^= i ^ nums[i];
}
return xor;
}
}- Mathematical approach: $ ext{Expected Sum} - ext{Actual Sum} = ext{Missing Number}$.
- XOR approach avoids potential integer overflow errors.
What primary advantage does the Bitwise XOR method have over Gauss's sum formula when n is very large?
Q7: How do you move all zeroes to the end of an array in-place while maintaining relative order?
Maintain a lastNonZeroFoundAt pointer initialized to 0. Iterate through the array; whenever a non-zero element is encountered, swap it with the element at lastNonZeroFoundAt and increment the pointer.
public class MoveZeroes {
public static void moveZeroes(int[] nums) {
int insertPos = 0;
for (int num : nums) {
if (num != 0) {
nums[insertPos++] = num;
}
}
while (insertPos < nums.length) {
nums[insertPos++] = 0;
}
}
}- Two-pointer partitioning scheme.
- Executes in $O(n)$ time with $O(1)$ auxiliary memory.
What is the total number of array writes required in the worst-case for the two-pass insertPos approach?
Q8: How do you reverse a Singly LinkedList iteratively in O(n) time and O(1) space?
Maintain three pointers: prev (initialized to null), curr (initialized to head), and next. Traverse the list: store curr.next in next, reverse curr.next to point to prev, advance prev to curr, and advance curr to next. Return prev as the new head.
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class ReverseLinkedList {
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
}- Use
prev,curr, andnextpointers to reverse node pointers in place. - $O(n)$ time complexity, $O(1)$ space complexity.
What does the prev pointer point to at the conclusion of the iterative reversal loop?
Q9: How do you detect a cycle in a LinkedList using Floyd's Cycle-Finding Algorithm?
Use Floyd's Tortoise and Hare Algorithm. Initialize two pointers: slow and fast at head. Move slow by 1 step and fast by 2 steps. If a cycle exists, fast and slow will eventually meet at the same node. If fast reaches null, no cycle exists.
public class LinkedListCycle {
public static boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
}- Two pointers moving at different speeds ($1 imes$ vs $2 imes$).
- Detects cycles in $O(n)$ time using $O(1)$ memory.
Why is Floyd's Cycle detection algorithm preferred over storing visited nodes in a HashSet?
Q10: How do you validate balanced brackets and parentheses using a Stack?
Traverse the string character by character. When encountering an opening bracket ((, {, [), push its corresponding matching closing bracket onto a Deque<Character> stack. When encountering a closing bracket, check if the stack is empty or if the popped element matches. Return stack.isEmpty() at the end.
import java.util.ArrayDeque;
import java.util.Deque;
public class ValidParentheses {
public static boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') stack.push(')');
else if (c == '{') stack.push('}');
else if (c == '[') stack.push(']');
else if (stack.isEmpty() || stack.pop() != c) return false;
}
return stack.isEmpty();
}
}- Push expected closing characters to simplify validation logic.
- Return
stack.isEmpty()to handle unclosed opening brackets.
What is the stack state when processing an invalid input string with unmatched opening brackets like "((("?