| Array index access | O(1) time — direct memory offset calculation |
| Linear search (unsorted) | O(n) time, O(1) space |
| Binary search (sorted) | O(log n) time, requires sorted input |
| Two-pointer technique | O(n) time, O(1) space — sorted arrays, pairs, palindromes |
| Sliding window | O(n) time — contiguous subarray/substring problems |
| Prefix sum array | O(n) build, O(1) range-sum query |
| ArrayList append | O(1) amortized (doubling growth strategy) |
| Arrays.sort() | O(n log n) — dual-pivot quicksort (primitives), TimSort (objects) |
Arrays & Strings Coding Interview Questions & Answers
Q1. What is the time complexity of accessing an element in an array by index, and why?
A: Accessing arr[i] is O(1) because arrays store elements in contiguous memory. The runtime computes the address as baseAddress + i * elementSize directly, with no traversal needed. This is the key advantage of arrays over linked structures, where you must walk node-by-node to reach an index.
Q2. What is the difference between a Java array and an ArrayList?
A: A plain array (int[]) has a fixed size set at creation and can hold primitives directly. ArrayList is a resizable wrapper backed internally by an array; it grows automatically (typically 1.5x capacity) and only stores objects (autoboxing primitives). Arrays are slightly faster and more memory-efficient for fixed-size primitive data; ArrayList offers convenience methods and dynamic sizing.
int[] fixed = new int[5]; // fixed size, primitives allowed
List<Integer> dynamic = new ArrayList<>(); // resizable, boxed Integer objects
dynamic.add(10);
dynamic.add(20);Q3. How do you find the maximum and minimum element in an array?
A: Scan the array once, tracking the running max and min while comparing each element. This is O(n) time and O(1) extra space — no sorting is needed, since sorting would cost O(n log n) for a task that only requires a single linear pass.
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) max = arr[i];
if (arr[i] < min) min = arr[i];
}Q4. Why is inserting an element at the beginning of an array an O(n) operation?
A: Arrays are contiguous blocks of memory, so inserting at index 0 requires shifting every existing element one position to the right to make room, which touches all n elements. Inserting at the end (when capacity allows) is O(1); inserting at the beginning or middle is always O(n) because of the shift.
Q5. How do you reverse an array in place?
A: Use two pointers starting at both ends and swap elements while moving them toward the center, stopping when they meet or cross. This runs in O(n) time and O(1) extra space since no auxiliary array is needed.
void reverse(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}Q6. What is the two-pointer technique and when is it applicable?
A: The two-pointer technique uses two index variables that traverse a data structure — often from opposite ends inward, or both moving forward at different speeds — instead of nested loops. It applies well to sorted arrays for pair-sum problems, palindrome checks, merging, and partitioning, typically reducing an O(n²) brute force to O(n).
Q7. How do you remove duplicates from a sorted array in place?
A: Use a slow pointer marking the last unique position and a fast pointer scanning ahead. Whenever the fast pointer finds a value different from the one at the slow pointer, increment the slow pointer and copy the value there. This is O(n) time, O(1) space, and works only because the array is sorted (duplicates are adjacent).
int removeDuplicates(int[] arr) {
if (arr.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < arr.length; fast++) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1; // new length
}Q8. What is the sliding window technique?
A: Sliding window maintains a contiguous range (window) over an array or string and adjusts its boundaries incrementally rather than recomputing from scratch. A fixed-size window slides one step at a time (add new element, remove the one leaving); a variable-size window expands/shrinks based on a condition. It converts many O(n²) brute-force substring/subarray scans into O(n).
Q9. How do you find the maximum sum subarray of a fixed size k?
A: Compute the sum of the first k elements, then slide the window: subtract the element leaving the window and add the new element entering it, updating the max each step. This is O(n) time versus the O(n×k) brute force of recomputing every window's sum.
int maxSumSubarray(int[] arr, int k) {
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += arr[i];
int maxSum = windowSum;
for (int i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}Q10. What is Kadane's algorithm and what problem does it solve?
A: Kadane's algorithm finds the maximum sum of any contiguous subarray in O(n) time and O(1) space. It keeps a running "current max ending here" — if adding the current element makes the running sum negative-leaning worse than starting fresh, it resets to the current element; otherwise it extends. The global max is tracked across all positions.
int maxSubArray(int[] nums) {
int maxEndingHere = nums[0], maxSoFar = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}Q11. How do you rotate an array to the right by k positions efficiently?
A: The reversal algorithm does this in O(n) time and O(1) space: reverse the whole array, then reverse the first k elements, then reverse the remaining n-k elements. An alternative is copying into a temp array at shifted indices, which is O(n) time but O(n) space.
void rotate(int[] arr, int k) {
int n = arr.length;
k %= n;
reverse(arr, 0, n - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, n - 1);
}
void reverse(int[] arr, int start, int end) {
while (start < end) {
int t = arr[start]; arr[start] = arr[end]; arr[end] = t;
start++; end--;
}
}Q12. What is the Dutch National Flag problem?
A: It asks you to sort an array containing only three distinct values (classically 0, 1, 2) in a single O(n) pass using O(1) space. The solution uses three pointers — low, mid, high — partitioning the array into three regions in place without a general-purpose sort.
void sortColors(int[] arr) {
int low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
if (arr[mid] == 0) { swap(arr, low++, mid++); }
else if (arr[mid] == 1) { mid++; }
else { swap(arr, mid, high--); }
}
}Q13. How do you find the missing number in an array containing 1 to n with one number missing?
A: Use the formula for the sum of 1..n, which is n*(n+1)/2, and subtract the actual sum of the array elements — the difference is the missing number. This is O(n) time, O(1) space. Alternatively, XOR all numbers 1..n with all array elements; the result is the missing number, which avoids overflow risk for very large n.
int findMissing(int[] arr, int n) {
long expectedSum = (long) n * (n + 1) / 2;
long actualSum = 0;
for (int x : arr) actualSum += x;
return (int) (expectedSum - actualSum);
}Q14. How do you find a duplicate number in an array without using extra space?
A: If values are in range [0, n-1] and stored in an array of size n, treat the array as an implicit linked list where arr[i] points to index arr[i]; a duplicate creates a cycle, detectable with Floyd's cycle-detection (tortoise and hare) in O(n) time, O(1) space. A simpler alternative when values can be negated: mark visited indices by negating arr[abs(v)] and check if it's already negative.
Q15. What is a prefix sum array and how does it speed up range-sum queries?
A: A prefix sum array prefix[i] stores the cumulative sum of all elements from index 0 to i. Building it takes O(n). After that, the sum of any range [l, r] is computed in O(1) as prefix[r] - prefix[l-1], instead of re-summing the range in O(n) each query — critical when there are many range-sum queries.
int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) prefix[i + 1] = prefix[i] + arr[i];
// sum of range [l, r] inclusive:
int rangeSum = prefix[r + 1] - prefix[l];Q16. How do you solve the classic Two Sum problem efficiently?
A: Use a HashMap to store each visited value's index. For each element, check if target - current already exists in the map; if so, return the pair. This is O(n) time and O(n) space, versus O(n²) for the brute-force nested-loop approach. If the array is sorted, a two-pointer approach can solve it in O(n) time and O(1) space instead.
int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (seen.containsKey(need)) return new int[]{seen.get(need), i};
seen.put(nums[i], i);
}
throw new IllegalArgumentException("No solution");
}Q17. How do you solve the Three Sum problem (find all triplets summing to zero)?
A: Sort the array first (O(n log n)). Then for each index i, fix nums[i] and use two pointers on the remaining subarray to find pairs summing to -nums[i], skipping duplicate values to avoid duplicate triplets. This gives O(n²) overall, better than the O(n³) brute force.
List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++; right--;
} else if (sum < 0) left++;
else right--;
}
}
return result;
}Q18. How do you find a contiguous subarray with a given sum in an unsorted array (including negative numbers)?
A: Use prefix sums with a HashMap: as you scan and accumulate the running sum, check whether runningSum - target has been seen before — if so, the subarray between those points sums to target. This handles negative numbers correctly and runs in O(n) time, O(n) space, unlike a sliding window which only works cleanly with non-negative values.
Q19. How do you merge two sorted arrays into one sorted array?
A: Use two pointers, one per array, comparing the current elements and appending the smaller one to the result, advancing that pointer. Once one array is exhausted, append the remainder of the other. This runs in O(m+n) time and O(m+n) space for the output array — the same idea powers the merge step of merge sort.
int[] merge(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
result[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
while (i < a.length) result[k++] = a[i++];
while (j < b.length) result[k++] = b[j++];
return result;
}Q20. How do you merge overlapping intervals?
A: Sort intervals by start time (O(n log n)). Then scan left to right, keeping a "current merged interval"; if the next interval's start is <= the current merged interval's end, extend the end to the max of the two; otherwise, close the current merged interval and start a new one. This is O(n log n) total, dominated by the sort.
int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
for (int[] iv : intervals) {
if (!merged.isEmpty() && iv[0] <= merged.get(merged.size() - 1)[1]) {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], iv[1]);
} else {
merged.add(iv);
}
}
return merged.toArray(new int[0][]);
}Q21. How do you find the intersection of two arrays?
A: Put one array's elements into a HashSet, then iterate the second array and collect elements present in the set (removing them after a match if duplicates in the result should be avoided). This is O(m+n) time, O(min(m,n)) space. If both arrays are sorted, a two-pointer merge-style scan achieves the same in O(m+n) time and O(1) extra space (besides the result).
Q22. How do you move all zeroes in an array to the end while preserving the relative order of non-zero elements?
A: Use a single pointer marking the next position to place a non-zero element. Scan the array; whenever a non-zero element is found, swap it into that position and advance the pointer. This is O(n) time, O(1) space, and preserves relative order in one pass.
void moveZeroes(int[] nums) {
int insertPos = 0;
for (int num : nums) {
if (num != 0) nums[insertPos++] = num;
}
while (insertPos < nums.length) nums[insertPos++] = 0;
}Q23. How does the Boyer-Moore voting algorithm find the majority element?
A: The majority element (appearing more than n/2 times) can be found in O(n) time and O(1) space by keeping a candidate and a count: increment count when the current element matches the candidate, decrement otherwise, and swap to a new candidate when count hits zero. Because the majority element outnumbers all others combined, it survives this cancellation process.
int majorityElement(int[] nums) {
int candidate = nums[0], count = 0;
for (int num : nums) {
if (num == candidate) count++;
else count--;
if (count == 0) { candidate = num; count = 1; }
}
return candidate;
}Q24. How do you solve the "trapping rain water" problem?
A: For each bar, the water it can trap equals min(maxLeft, maxRight) - height[i], where maxLeft/maxRight are the tallest bars to its left and right. The efficient two-pointer solution tracks running maxLeft and maxRight from both ends inward, always processing the side with the smaller max, achieving O(n) time and O(1) space (versus O(n) space for precomputed left/right max arrays).
int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right--;
}
}
return water;
}Q25. How do you compute "product of array except self" without using division?
A: Build a prefix-product array (product of all elements to the left of i) and a suffix-product array (product of all elements to the right of i), then multiply them elementwise. This runs in O(n) time and can be done in O(1) extra space by computing prefix products in the output array first, then folding in suffix products in a second pass with a single running variable.
int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] result = new int[n];
result[0] = 1;
for (int i = 1; i < n; i++) result[i] = result[i - 1] * nums[i - 1];
int suffix = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= suffix;
suffix *= nums[i];
}
return result;
}Q26. What is the "next permutation" algorithm?
A: To get the next lexicographic permutation in place: scan from the right to find the first index i where arr[i] < arr[i+1] (the pivot). Then find the smallest element to the right of i that is greater than arr[i], swap them, and reverse the suffix after i. This runs in O(n) time and O(1) space.
Q27. How do you find a peak element in an array (an element greater than its neighbors)?
A: A modified binary search works even without full sorting: compare the middle element to its right neighbor. If arr[mid] < arr[mid+1], a peak must exist to the right, so search the right half; otherwise search the left half (including mid). This achieves O(log n) time instead of O(n) linear scanning.
Q28. How do you search for a target in a rotated sorted array?
A: Use a modified binary search: at each step, determine which half (left or right of mid) is properly sorted by comparing arr[low], arr[mid], and arr[high]. If the target falls within the sorted half's range, search there; otherwise search the other half. This preserves O(log n) time despite the rotation.
int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (nums[mid] == target) return mid;
if (nums[low] <= nums[mid]) { // left half sorted
if (nums[low] <= target && target < nums[mid]) high = mid - 1;
else low = mid + 1;
} else { // right half sorted
if (nums[mid] < target && target <= nums[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}Q29. What is an equilibrium index and how do you find one efficiently?
A: An equilibrium index is a position where the sum of elements to its left equals the sum of elements to its right. Compute the total sum once, then scan left to right tracking a running left-sum; at each index, the right-sum is total - leftSum - arr[i]. This finds an equilibrium index in O(n) time and O(1) space, avoiding recomputation for every candidate index.
Q30. How do you traverse a matrix in spiral order?
A: Maintain four boundaries — top, bottom, left, right. Traverse the top row left-to-right, the right column top-to-bottom, the bottom row right-to-left, and the left column bottom-to-top, shrinking each boundary inward after its pass, and repeat until the boundaries cross. This visits all m×n cells in O(m×n) time.
List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
for (int j = left; j <= right; j++) result.add(matrix[top][j]);
top++;
for (int i = top; i <= bottom; i++) result.add(matrix[i][right]);
right--;
if (top <= bottom) {
for (int j = right; j >= left; j--) result.add(matrix[bottom][j]);
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) result.add(matrix[i][left]);
left++;
}
}
return result;
}Q31. How do you rotate an N×N matrix by 90 degrees in place?
A: Transpose the matrix (swap matrix[i][j] with matrix[j][i] for i < j), then reverse each row. This achieves a clockwise 90-degree rotation in O(n²) time and O(1) extra space, without allocating a second matrix.
void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int t = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = t;
}
for (int[] row : matrix) {
for (int l = 0, r = n - 1; l < r; l++, r--) {
int t = row[l]; row[l] = row[r]; row[r] = t;
}
}
}Q32. How do you efficiently search for a value in a row-wise and column-wise sorted matrix?
A: Start at the top-right corner. If the current value equals the target, return found. If it's greater than the target, move left (eliminate the column); if smaller, move down (eliminate the row). This eliminates one row or column per step, giving O(m+n) time versus O(m×n) brute force, and O(1) space.
Q33. How do you set an entire row and column to zero if a matrix cell is zero, in place?
A: First pass: scan the matrix and record which rows and columns contain a zero (using the matrix's own first row/column as markers, or small boolean arrays for O(1) extra space beyond that). Second pass: zero out any cell whose row or column was marked. This is O(m×n) time, avoiding the bug of zeroing cells during the scan itself (which would cascade incorrectly).
Q34. How do you find the longest consecutive sequence in an unsorted array?
A: Insert all elements into a HashSet for O(1) lookups. For each number that is the start of a sequence (i.e., num - 1 is not in the set), count consecutive numbers upward (num, num+1, num+2, ...) until the chain breaks. Because each number is only counted as part of one sequence-start expansion, total work is O(n), beating the O(n log n) sort-based approach.
int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);
int longest = 0;
for (int n : set) {
if (!set.contains(n - 1)) {
int length = 1;
while (set.contains(n + length)) length++;
longest = Math.max(longest, length);
}
}
return longest;
}Q35. How do you find the kth largest element in an array?
A: Three common approaches: (1) sort descending and index k-1, O(n log n); (2) use a min-heap of size k, pushing elements and popping the smallest when size exceeds k, O(n log k); (3) use Quickselect (partition-based, like quicksort but recursing only into the needed side), average O(n) but O(n²) worst case. Quickselect is the optimal interview answer for average-case performance.
int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
minHeap.offer(n);
if (minHeap.size() > k) minHeap.poll();
}
return minHeap.peek();
}Q36. What is an in-place algorithm and why does it matter in interviews?
A: An in-place algorithm transforms input using only O(1) (or O(log n)) extra space, modifying the original structure rather than allocating a new one proportional to input size. Interviewers ask for it to test whether you understand space complexity trade-offs — e.g., reversing an array in place versus copying into a new reversed array uses the same time but very different space.
Q37. What is the amortized time complexity of appending to a Java ArrayList, and why?
A: Appending is O(1) amortized. Internally, ArrayList doubles its backing array capacity (roughly) when full, which is an O(n) operation, but this happens rarely enough (geometrically less often as size grows) that the total cost of n appends is O(n), averaging to O(1) per append. A single append can occasionally spike to O(n) when a resize is triggered.
Q38. How do you check if two sorted arrays can be merged without using extra space (in one of them, if it has enough capacity)?
A: Merge from the back: compare the last valid elements of both arrays and place the larger one at the end of the combined capacity, working backward. This avoids overwriting unprocessed elements in the array with spare capacity and runs in O(m+n) time, O(1) extra space.
void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
}Q39. How do you find all "leaders" in an array (elements greater than every element to their right)?
A: Scan from right to left, keeping a running maximum. An element is a leader if it is greater than the running max seen so far (to its right); update the max after each check. This is O(n) time and O(1) extra space, versus O(n²) for checking each element against all elements to its right individually.
Q40. How do you find the maximum sum of a circular subarray?
A: The answer is the max of two cases: (1) the standard Kadane's max subarray sum (non-wrapping), and (2) total sum minus the minimum subarray sum (using an inverted Kadane's to find minimum), which represents the best wrapping subarray. Special case: if all elements are negative, case 2 would incorrectly yield an empty array, so you must fall back to case 1's result. Overall O(n) time.
Q41. How do you check if a string is a palindrome?
A: Use two pointers starting at both ends of the string, comparing characters and moving inward; if any pair mismatches, it is not a palindrome. This runs in O(n) time and O(1) extra space. An alternative is reversing the string and comparing to the original, which is also O(n) time but uses O(n) extra space for the reversed copy.
Q42. How do you reverse a string in Java given that String is immutable?
A: Since String cannot be mutated, convert it to a char array (or use StringBuilder), reverse in place with a two-pointer swap, then build a new String from the result. StringBuilder.reverse() does this internally and is the idiomatic one-liner in production code.
String reverse(String s) {
char[] chars = s.toCharArray();
int left = 0, right = chars.length - 1;
while (left < right) {
char t = chars[left]; chars[left] = chars[right]; chars[right] = t;
left++; right--;
}
return new String(chars);
}
// Idiomatic: new StringBuilder(s).reverse().toString();Q43. How do you check if two strings are anagrams of each other?
A: If lengths differ, they cannot be anagrams. Otherwise, build a frequency count of each character (a fixed-size int array of 26 for lowercase letters, or a HashMap for Unicode) for one string, then decrement counts while scanning the second string. If all counts return to zero, they are anagrams. This is O(n) time, O(1) space (for a bounded alphabet) — faster than sorting both strings and comparing, which is O(n log n).
Q44. How do you find the first non-repeating character in a string?
A: Build a frequency map of all characters in one pass (O(n)), then scan the string again in order and return the first character whose count is 1. Two passes are needed because you must know the full frequency before you can trust that a character never repeats. Overall O(n) time, O(1) space for a bounded character set.
char firstNonRepeating(String s) {
int[] freq = new int[256];
for (char c : s.toCharArray()) freq[c]++;
for (char c : s.toCharArray()) if (freq[c] == 1) return c;
return '\0';
}Q45. How do you count the occurrences of each character in a string?
A: For ASCII text, use a fixed int array of size 128/256 indexed by the character's numeric code — O(1) increment per character, O(n) total, O(1) space. For full Unicode text, use a HashMap<Character, Integer> (or better, count code points via codePoints() to handle characters outside the Basic Multilingual Plane correctly).
Q46. Why does Java's String immutability matter for string algorithm design?
A: Because every "modification" (concatenation, substring, replace) creates a brand-new String object rather than mutating the original, naively building or editing strings in a loop with + can degrade to O(n²) total time due to repeated copying. Algorithm design should convert to a char[] or use StringBuilder for any in-place-style manipulation, only converting back to String once at the end.
Q47. Why is StringBuilder preferred over String concatenation inside a loop?
A: Each + concatenation on immutable Strings allocates a new String object and copies both operands' characters, so n concatenations in a loop cost O(n²) total. StringBuilder maintains a resizable internal char buffer and appends in amortized O(1) per call (like ArrayList), making the loop O(n) total. Always prefer StringBuilder.append() when building strings incrementally.
Q48. How do you find the length of the longest substring without repeating characters?
A: Use a variable-size sliding window with a HashSet or HashMap tracking characters currently in the window. Expand the right edge; if the new character is already in the window, shrink from the left until the duplicate is removed. Track the max window size seen. This runs in O(n) time since each character is visited at most twice (once by each pointer), and O(min(n, alphabet size)) space.
int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
left = lastSeen.get(c) + 1;
}
lastSeen.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Q49. How do you find the longest palindromic substring in a string?
A: The "expand around center" technique checks every possible center (2n-1 centers, accounting for both odd- and even-length palindromes) and expands outward while characters match, tracking the longest found. This is O(n²) time, O(1) space — simpler to implement correctly than Manacher's algorithm, which achieves O(n) but is rarely expected in an interview unless explicitly requested.
String longestPalindrome(String s) {
int start = 0, maxLen = 0;
for (int center = 0; center < s.length(); center++) {
int len1 = expand(s, center, center); // odd length
int len2 = expand(s, center, center + 1); // even length
int len = Math.max(len1, len2);
if (len > maxLen) { maxLen = len; start = center - (len - 1) / 2; }
}
return s.substring(start, start + maxLen);
}
int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return r - l - 1;
}Q50. How do you check if one string is a rotation of another?
A: If two strings have equal length, string B is a rotation of string A if and only if B is a substring of A concatenated with itself (A+A). For example, "waterbottle" rotated is "erbottlewat", which appears inside "waterbottlewaterbottle". This trick reduces the rotation check to a single substring search, O(n) with an efficient search algorithm.
Q51. How do you check if a string of brackets is balanced/valid?
A: Use a stack: push opening brackets as encountered; on a closing bracket, pop the stack and verify it matches the corresponding opening type — if the stack is empty or the types mismatch, the string is invalid. At the end, the string is valid only if the stack is empty. This is O(n) time, O(n) worst-case space.
boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) stack.push(c);
else if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
}
return stack.isEmpty();
}Q52. How does the naive (brute-force) substring search algorithm work, and what is its complexity?
A: For each starting position in the text, compare characters one by one against the pattern until a mismatch or a full match. In the worst case (e.g., text "aaaa...a" and pattern "aaab"), this is O(n×m) where n is text length and m is pattern length, because every position can require nearly a full pattern-length comparison before failing.
Q53. How does the KMP (Knuth-Morris-Pratt) algorithm improve substring search?
A: KMP precomputes a "failure function" (longest proper prefix of the pattern that is also a suffix, for every prefix length) in O(m) time. During the search, on a mismatch it uses this table to avoid re-comparing characters already known to match, skipping the text pointer back only as far as necessary rather than restarting from scratch. This guarantees O(n+m) worst-case time overall, a major improvement over the naive O(n×m).
Q54. How does the Rabin-Karp algorithm perform substring search?
A: Rabin-Karp computes a rolling hash of the pattern and of each window of the text of the same length, comparing hashes instead of raw characters. Because the rolling hash can be updated in O(1) as the window slides (subtract the outgoing character's contribution, multiply, add the incoming character), average-case time is O(n+m). On a hash collision, it falls back to a direct character comparison to confirm a true match, so worst case remains O(n×m) but is rare with a good hash function.
Q55. How do you group an array of strings into anagram groups?
A: Use a HashMap keyed by a canonical form of each string — either the sorted character sequence, or a fixed-length frequency-count signature (e.g., a 26-length count array turned into a string/key). All strings mapping to the same key are anagrams of each other and go into the same group. Sorting-based keys cost O(n×k log k) total (k = average string length); frequency-count keys cost O(n×k).
List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
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());
}Q56. How does string compression using run-length encoding work?
A: Scan the string once, counting consecutive repeats of each character; append the character and its count (if greater than 1) to a result buffer. For example, "aaabbc" compresses to "a3b2c". This is O(n) time, O(n) space for the output in the worst case (no repeats, though a well-designed version returns the original if compression doesn't save space).
String compress(String s) {
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < s.length()) {
char current = s.charAt(i);
int count = 0;
while (i < s.length() && s.charAt(i) == current) { i++; count++; }
sb.append(current);
if (count > 1) sb.append(count);
}
return sb.toString();
}Q57. How do you check if any permutation of a short string exists as a substring of a longer one?
A: Use a fixed-size sliding window of length equal to the shorter string, maintaining a running character-frequency count for the window and comparing it to the target string's frequency count. Slide the window one character at a time, updating counts in O(1) per step instead of recomputing from scratch. This runs in O(n) time overall instead of generating all permutations (O(k!)).
Q58. How do you reverse the order of words in a sentence while keeping the words themselves intact?
A: Split the string on whitespace (handling multiple/leading/trailing spaces), then either reverse the resulting list of words and join with a single space, or use a two-pass in-place technique on a char array: reverse the entire character array first, then reverse each individual word within it back to normal order. The two-pass technique is O(n) time and O(1) extra space (beyond the output) and is a favorite in-place variant.
String reverseWords(String s) {
String[] words = s.trim().split("\\s+");
StringBuilder sb = new StringBuilder();
for (int i = words.length - 1; i >= 0; i--) {
sb.append(words[i]);
if (i > 0) sb.append(' ');
}
return sb.toString();
}Q59. How do you remove all adjacent duplicate characters from a string (repeatedly)?
A: Use a stack: for each character, if it equals the character on top of the stack, pop the stack (they cancel); otherwise push the current character. After processing the whole string, the stack (bottom to top) holds the result. This is O(n) time and O(n) space, correctly handling cascading removals (e.g., "abba" fully collapses to an empty string).
String removeDuplicates(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek() == c) stack.pop();
else stack.push(c);
}
StringBuilder sb = new StringBuilder();
for (char c : stack) sb.append(c);
return sb.reverse().toString();
}Q60. How do you find the longest common prefix among an array of strings?
A: Take the first string as an initial candidate prefix; for each subsequent string, shrink the candidate until it is actually a prefix of that string (comparing character by character or using indexOf tricks). Stop early if the candidate becomes empty. Worst case is O(n×m) where m is the length of the shortest string, but it typically terminates much earlier.
Q61. Comparing sorting-based and frequency-count-based anagram checks, which is better and why?
A: Sorting both strings and comparing them is O(n log n) time, O(n) space (for the sorted copies). A frequency-count comparison using a fixed-size array (for a bounded alphabet like lowercase English letters) is O(n) time, O(1) space, which is strictly better. Prefer frequency counting whenever the character set is bounded and known in advance.
Q62. How do you check if a string is a valid palindrome, ignoring non-alphanumeric characters and case?
A: Use two pointers from both ends; at each step, skip over any character that is not a letter or digit (using Character.isLetterOrDigit()), then compare the remaining characters case-insensitively (Character.toLowerCase()). Continue until the pointers meet or a mismatch is found. This is O(n) time, O(1) space, avoiding the need to build a cleaned copy of the string first.
Q63. How do you solve the "minimum window substring" problem?
A: Use a variable-size sliding window with a frequency map of the target characters still needed. Expand the right edge, decrementing the needed count for each character; once all required characters are covered, try shrinking from the left to minimize the window while it remains valid, recording the smallest valid window seen. This runs in O(n + m) time (n = text length, m = target length) since each pointer moves forward monotonically.
String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
int required = need.size(), formed = 0;
Map<Character, Integer> window = new HashMap<>();
int left = 0, bestLen = Integer.MAX_VALUE, bestStart = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.merge(c, 1, Integer::sum);
if (need.containsKey(c) && window.get(c).intValue() == need.get(c).intValue()) formed++;
while (formed == required) {
if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
char lc = s.charAt(left);
window.put(lc, window.get(lc) - 1);
if (need.containsKey(lc) && window.get(lc) < need.get(lc)) formed--;
left++;
}
}
return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
}Q64. How do you compute the longest common subsequence (LCS) of two strings?
A: Use dynamic programming with a 2D table dp[i][j] representing the LCS length of the first i characters of string A and first j of string B. If the characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). This runs in O(n×m) time and space (reducible to O(min(n,m)) space with a rolling array).
int longestCommonSubsequence(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = (a.charAt(i - 1) == b.charAt(j - 1))
? dp[i - 1][j - 1] + 1
: Math.max(dp[i - 1][j], dp[i][j - 1]);
return dp[n][m];
}Q65. What is the difference between longest common subsequence and longest common substring?
A: A subsequence preserves relative order but need not be contiguous (characters can be skipped); a substring must be contiguous. Both use similar O(n×m) DP tables, but the substring recurrence resets to 0 on a mismatch (dp[i][j] = 0 if characters differ) rather than taking the max of neighboring cells, and the answer is the maximum value anywhere in the table rather than the bottom-right corner.
Q66. How do you compute the edit distance (Levenshtein distance) between two strings?
A: Use DP where dp[i][j] is the minimum number of insertions, deletions, and substitutions to convert the first i characters of A into the first j characters of B. If characters match, dp[i][j] = dp[i-1][j-1]; otherwise dp[i][j] = 1 + min(insert, delete, substitute) = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]). This is O(n×m) time and space.
int editDistance(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) dp[i][0] = i;
for (int j = 0; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = (a.charAt(i - 1) == b.charAt(j - 1))
? dp[i - 1][j - 1]
: 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
return dp[n][m];
}Q67. How do you solve the "word break" problem (can a string be segmented into dictionary words)?
A: Use DP where dp[i] means the prefix of length i can be segmented into valid dictionary words. dp[0] = true (empty prefix); for each i, check every j < i where dp[j] is true and the substring from j to i is in the dictionary (using a HashSet for O(1) lookup) — if found, dp[i] = true. This is O(n²) time (n² substring checks, each O(1) with a hash set and precomputed substring, or O(n) if using substring slicing naively) and O(n) space.
Q68. How do you count all palindromic substrings in a string?
A: Use the expand-around-center technique for every possible center (2n-1 centers for odd and even lengths); each successful expansion step counts one palindromic substring. This is O(n²) time, O(1) space. A DP table approach (dp[i][j] = true if substring i..j is a palindrome) also works in O(n²) time and space, useful when the DP table is needed for a follow-up like palindrome partitioning.
Q69. How do you count the number of subarrays whose sum equals exactly k?
A: Use a running prefix sum and a HashMap counting how many times each prefix-sum value has occurred so far. For each new prefix sum, the number of valid subarrays ending here equals the count of (prefixSum - k) seen previously — add that to the answer, then record the current prefix sum. This is O(n) time, O(n) space, and correctly handles negative numbers, unlike a sliding window.
Q70. How do you find the maximum product of a contiguous subarray?
A: Unlike max-sum, negative numbers can flip a very negative running product into the new maximum when multiplied by another negative, so you must track both a running max product and a running min product ending at each position, updating both at every step (since a negative current element can turn the min into the new max). This is O(n) time, O(1) space.
int maxProduct(int[] nums) {
int maxProd = nums[0], minProd = nums[0], result = nums[0];
for (int i = 1; i < nums.length; i++) {
int n = nums[i];
int candMax = Math.max(n, Math.max(maxProd * n, minProd * n));
int candMin = Math.min(n, Math.min(maxProd * n, minProd * n));
maxProd = candMax; minProd = candMin;
result = Math.max(result, maxProd);
}
return result;
}Q71. How do you find the maximum in every fixed-size sliding window across an array?
A: Use a monotonic deque holding indices, keeping it decreasing in value from front to back. For each new element, pop indices from the back whose values are smaller than the current one (they can never be the max while the current element is in the window), then push the current index; pop from the front if it has slid out of the window. The front of the deque is always the current window's max. This is O(n) total time since each index is pushed and popped at most once.
Q72. How do you find the length of the smallest contiguous subarray with a sum ≥ a given target (positive numbers only)?
A: Use a variable-size sliding window: expand the right edge, adding to a running sum; whenever the running sum meets or exceeds the target, try shrinking from the left (subtracting from the sum) to find the minimal valid window length, recording the best length seen. Because both pointers only move forward, this is O(n) time and O(1) space, versus O(n²) for checking all subarrays.
int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}Q73. How do you find a pair of elements in an array with a given difference?
A: Sort the array (O(n log n)), then use two pointers: for a target difference d, advance the right pointer if the current difference is smaller than d, and the left pointer if it's larger, since sorted order makes the difference change monotonically as pointers move. Alternatively, use a HashSet for O(n) time: for each element x, check if x + d (or x - d) exists in the set.
Q74. How do you count the number of pairs in an array that sum to a given value?
A: Use a HashMap to count frequency of each value seen so far. For each element x, add the current count of (target - x) in the map to the running total, then increment x's own count in the map. This correctly counts all pairs (including duplicate values) in O(n) time and O(n) space, versus O(n²) for the nested-loop brute force.
Q75. How do you find the smallest missing positive integer in an unsorted array?
A: The answer must be between 1 and n+1 (n = array length), so use the array itself as a hash table: for each value v in range [1, n], place it at index v-1 by swapping (cyclic sort), ignoring out-of-range and duplicate values. After this O(n) partitioning pass, scan the array — the first index i where arr[i] != i + 1 gives the answer i+1; if none, the answer is n+1. This achieves O(n) time, O(1) extra space.
Q76. How do you implement a String-to-Integer (atoi) parser?
A: Skip leading whitespace, then an optional '+' or '-' sign, then consume consecutive digit characters, building up the numeric value while clamping to Integer.MIN_VALUE/MAX_VALUE if it would overflow (check before multiplying/adding to avoid actual overflow). Stop parsing at the first non-digit character; return 0 if no valid number was found at all. This is O(n) time.
int myAtoi(String s) {
int i = 0, n = s.length();
while (i < n && s.charAt(i) == ' ') i++;
int sign = 1;
if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
sign = (s.charAt(i) == '-') ? -1 : 1;
i++;
}
long result = 0;
while (i < n && Character.isDigit(s.charAt(i))) {
result = result * 10 + (s.charAt(i) - '0');
if (sign * result > Integer.MAX_VALUE) return Integer.MAX_VALUE;
if (sign * result < Integer.MIN_VALUE) return Integer.MIN_VALUE;
i++;
}
return (int) (sign * result);
}Q77. How do you add two very large non-negative integers represented as strings?
A: Process both strings from the rightmost digit toward the left (like manual column addition), maintaining a carry. At each step, sum the corresponding digits (treating a missing digit as 0 once one string is exhausted) plus the carry, append sum % 10 to the result, and update the carry to sum / 10. Reverse the accumulated digits at the end. This is O(max(n, m)) time and avoids the range limits of primitive long/int for arbitrarily large numbers.
String addStrings(String num1, String num2) {
StringBuilder sb = new StringBuilder();
int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int d1 = i >= 0 ? num1.charAt(i--) - '0' : 0;
int d2 = j >= 0 ? num2.charAt(j--) - '0' : 0;
int sum = d1 + d2 + carry;
sb.append(sum % 10);
carry = sum / 10;
}
return sb.reverse().toString();
}Q78. How do you multiply two non-negative integers represented as strings?
A: Use the grade-school multiplication approach: multiply each digit of one number by each digit of the other, placing the partial product at the correct offset in a result array of size len1 + len2, accumulating and carrying as needed, then trim leading zeros. This avoids overflow for arbitrarily large numbers and runs in O(n×m) time, which is optimal for a straightforward interview solution (Karatsuba's O(n^1.585) is a follow-up optimization rarely required).
Q79. How do you find the next greater element for every element in an array?
A: Use a monotonic decreasing stack of indices. Scan the array; while the stack's top index has a value smaller than the current element, pop it and record the current element as its "next greater element," then push the current index. Any indices remaining on the stack at the end have no next greater element. This is O(n) time since each index is pushed and popped once.
int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
Deque<Integer> stack = new ArrayDeque<>(); // indices
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
result[stack.pop()] = nums[i];
}
stack.push(i);
}
return result;
}Q80. What is the zigzag conversion problem and how do you solve it?
A: Given a string and a number of rows, the characters are conceptually written in a zigzag (diagonal) pattern across that many rows, then read back row by row. Simulate this by maintaining a "current row" index that increments while moving down and decrements while moving up (bouncing between 0 and numRows-1), appending each character to a StringBuilder for its row, then concatenating all row buffers. This is O(n) time, O(n) space.
Q81. What are the key trade-offs between arrays and linked lists?
A: Arrays offer O(1) random access and better cache locality (contiguous memory improves CPU cache hit rates), but insertion/deletion in the middle is O(n) due to shifting, and resizing beyond fixed capacity requires a full copy. Linked lists offer O(1) insertion/deletion at a known node (no shifting) but O(n) access to an arbitrary index and worse cache locality due to scattered memory and pointer-chasing overhead. Choose arrays when random access dominates; linked lists when frequent insertions/deletions at arbitrary positions dominate and indexed access is rare.
Q82. What is the difference between a substring and a subsequence?
A: A substring is a contiguous run of characters from the original string (e.g., "ell" from "hello"). A subsequence preserves relative order but characters need not be contiguous — they can skip positions (e.g., "hlo" is a subsequence of "hello" but not a substring). A string of length n has O(n²) substrings but O(2ⁿ) possible subsequences, which is why subsequence problems (like LCS) typically require DP rather than simple enumeration.
Q83. How do you find the length of the longest increasing subsequence (LIS)?
A: The O(n²) DP approach defines dp[i] as the LIS length ending at index i, computed as 1 + max(dp[j]) for all j < i where nums[j] < nums[i]. The optimal O(n log n) approach maintains a list of the smallest possible tail values for increasing subsequences of each length, using binary search to find where each new element fits (replacing the first tail ≥ it, or appending if it's the largest so far); the final list length is the LIS length.
int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int lo = 0, hi = size;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] < x) lo = mid + 1; else hi = mid;
}
tails[lo] = x;
if (lo == size) size++;
}
return size;
}Q84. How do you count subarrays whose sum is divisible by k?
A: Compute the running prefix sum modulo k, and use a HashMap counting how many times each remainder has occurred. Because two prefix sums with the same remainder mod k mean the subarray between them has a sum divisible by k, add the current remainder's prior count to the answer at each step, then increment that remainder's count. Careful: in Java, the % of a negative number can be negative, so normalize with ((sum % k) + k) % k. This is O(n) time, O(k) space.
Q85. How do you shuffle an array uniformly at random?
A: Use the Fisher-Yates (Knuth) shuffle: iterate from the last index down to the first, swapping the current element with a randomly chosen element from index 0 up to and including the current index. This guarantees every permutation is equally likely and runs in O(n) time, O(1) extra space. A common bug is picking the random index from the full array range instead of only the unshuffled prefix, which produces a biased (non-uniform) shuffle.
void shuffle(int[] arr) {
Random rand = new Random();
for (int i = arr.length - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}Q86. How do you generate all subsets (the power set) of an array?
A: Two common approaches: (1) backtracking — at each element, recursively branch into "include it" and "exclude it," building 2ⁿ subsets total; (2) bitmasking — iterate all integers from 0 to 2ⁿ-1, and for each, include element i if bit i is set. Both are O(2ⁿ × n) time (n to build/copy each subset) and are standard interview answers depending on whether recursion or iteration is preferred.
List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
result.add(new ArrayList<>(current));
for (int i = start; i < nums.length; i++) {
current.add(nums[i]);
backtrack(nums, i + 1, current, result);
current.remove(current.size() - 1);
}
}Q87. How do you generate all permutations of an array?
A: Use backtracking: maintain a "used" marker for each element; at each recursive step, try every unused element as the next position, recurse, then backtrack (unmark it) to try the next option. This explores all n! permutations, each built in O(n), for O(n! × n) total time. Swap-based in-place backtracking avoids a separate "used" array by swapping candidates into the current position and swapping back after recursing.
List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
permuteHelper(nums, 0, result);
return result;
}
void permuteHelper(int[] nums, int start, List<List<Integer>> result) {
if (start == nums.length) {
List<Integer> perm = new ArrayList<>();
for (int n : nums) perm.add(n);
result.add(perm);
return;
}
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
permuteHelper(nums, start + 1, result);
swap(nums, start, i);
}
}Q88. How do you efficiently check if an array is sorted in ascending order?
A: Scan once, comparing each element to the next; return false as soon as any arr[i] > arr[i+1] is found. This is O(n) time worst case but can exit early (best case O(1)) if the array is unsorted near the start. There is no need to actually sort and compare — that would waste O(n log n) for a simple yes/no check.
Q89. Why must binary search's input be sorted, and how do you avoid integer overflow when computing the midpoint?
A: Binary search relies on being able to discard half the search space based on a single comparison, which is only valid if the elements are ordered — on unsorted data the target could be anywhere, so no half can be safely eliminated. For the midpoint, computing (low + high) / 2 can overflow if both are large ints; use low + (high - low) / 2 or the unsigned right shift (low + high) >>> 1 to avoid it.
Q90. How do you find the second largest element in an array in a single pass?
A: Track two variables, largest and secondLargest, both initialized to negative infinity (or the first two elements). For each element: if it's greater than largest, shift largest down into secondLargest and update largest; else if it's greater than secondLargest (and not equal to largest, to handle duplicates correctly), update secondLargest. This is O(n) time, O(1) space, avoiding the O(n log n) cost of sorting.
int secondLargest(int[] arr) {
long largest = Long.MIN_VALUE, second = Long.MIN_VALUE;
for (int x : arr) {
if (x > largest) { second = largest; largest = x; }
else if (x > second && x != largest) { second = x; }
}
return (int) second;
}Q91. How do you find the single number that appears once while every other number appears exactly twice?
A: XOR every element together. Since x ^ x = 0 for any value x, all the paired numbers cancel each other out, leaving only the number that appears once. This is O(n) time, O(1) space, and is far more efficient than a HashMap frequency count (O(n) space) or sorting (O(n log n) time).
int singleNumber(int[] nums) {
int result = 0;
for (int n : nums) result ^= n;
return result;
}Q92. How do you find the common elements present in three sorted arrays?
A: Use three pointers, one per array. Compare the three current elements; if all are equal, record the value and advance all three pointers. Otherwise, advance the pointer(s) pointing at the smallest value(s), since a smaller value can never match the others in a sorted array. This runs in O(n1 + n2 + n3) time and O(1) extra space (besides the output).
Q93. What is "wiggle sort" and how do you achieve it in one pass?
A: Wiggle sort rearranges an array so that arr[0] ≤ arr[1] ≥ arr[2] ≤ arr[3] ... (alternating peaks and valleys). A single greedy pass works: at each index i, check the required relation with arr[i+1] — if it's violated, swap them. Because fixing a violation at position i only depends on its immediate neighbor, one O(n) left-to-right pass with O(1) space is sufficient; no sorting is required.
Q94. How do you count the number of islands in a 2D grid of 0s and 1s?
A: An island is a maximal group of connected '1' cells (usually 4-directionally connected). Scan every cell; whenever an unvisited '1' is found, increment the island count and run a DFS or BFS from it, marking every reachable connected '1' as visited so it isn't counted again. This is O(rows × cols) time and space (for the visited marking / recursion stack).
int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1') { count++; dfs(grid, r, c); }
return count;
}
void dfs(char[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] != '1') return;
grid[r][c] = '0'; // mark visited
dfs(grid, r + 1, c); dfs(grid, r - 1, c);
dfs(grid, r, c + 1); dfs(grid, r, c - 1);
}Q95. How do you validate a Sudoku board (partially filled, checking only the given rules)?
A: For each of the 9 rows, 9 columns, and 9 3×3 sub-boxes, use a HashSet (or boolean[9] array) to check that no digit 1-9 repeats, skipping empty cells. A single pass over all 81 cells can update all three sets (row, column, box index computed as (r/3)*3 + c/3) simultaneously, giving O(1) time relative to board size (81 cells is constant) — described as O(1) or O(n²) depending on whether board size is treated as fixed or variable n×n.
Q96. How do you remove all occurrences of a given value from an array in place and return the new length?
A: Use a single write pointer: scan the array, and whenever the current element does not equal the value to remove, copy it to the write pointer's position and advance the pointer. Elements beyond the final write pointer are irrelevant. This is O(n) time, O(1) space, and preserves the relative order of the remaining elements.
int removeElement(int[] nums, int val) {
int writePos = 0;
for (int readPos = 0; readPos < nums.length; readPos++) {
if (nums[readPos] != val) {
nums[writePos++] = nums[readPos];
}
}
return writePos;
}Q97. Why is inserting at the end of an ArrayList typically fast, but System.arraycopy still gets invoked internally?
A: When there's spare capacity, appending just writes to the next free slot — O(1), no copy needed. But when capacity is exceeded, ArrayList allocates a new, larger backing array (typically 1.5x the old size) and uses System.arraycopy (a highly optimized, often JIT-intrinsic, bulk memory copy) to move all existing elements over — an O(n) operation. Because resizes become exponentially rarer as the list grows, the amortized cost per append across n operations is still O(1).
Q98. How do you find the count of subarrays whose XOR equals a given value?
A: Similar to the subarray-sum-equals-k pattern: maintain a running prefix XOR and a HashMap counting how many times each prefix XOR value has occurred. For each new prefix XOR value, add the count of (prefixXor ^ target) seen so far to the answer, because XOR-ing a range is equivalent to XOR-ing two prefix values (XOR is its own inverse, unlike subtraction for sums). This is O(n) time, O(n) space.
Q99. How do you determine if an array can be partitioned into two subsets with equal sum?
A: If the total sum is odd, it's immediately impossible. Otherwise, this reduces to a subset-sum DP: can any subset sum to totalSum / 2? Use a boolean DP array of size (target+1) where dp[s] means sum s is achievable; process elements one at a time, updating from high to low to avoid reusing the same element twice in one iteration. This is O(n × target) time and O(target) space, a pseudo-polynomial solution typical of 0/1 knapsack-style problems.
Q100. How do you find the first and last occurrence of a target value in a sorted array with duplicates?
A: Run two separate binary searches: one biased to keep searching left even after finding a match (to find the first occurrence, moving high = mid - 1 on a match instead of stopping), and one biased to keep searching right (moving low = mid + 1 on a match) for the last occurrence. Each search is O(log n), so the combined answer is O(log n) total, versus O(n) for a linear scan.
int findFirst(int[] arr, int target) {
int low = 0, high = arr.length - 1, result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target) { result = mid; high = mid - 1; }
else if (arr[mid] < target) low = mid + 1;
else high = mid - 1;
}
return result;
}Q101. What sorting algorithm does Java's Arrays.sort() use, and does it differ for primitives vs objects?
A: For primitive arrays (int[], double[], etc.), Arrays.sort() uses a dual-pivot Quicksort variant — fast in practice, O(n log n) average, but not stable (relative order of equal elements isn't guaranteed, which doesn't matter for primitives anyway). For object arrays (String[], Integer[], or any Comparable), it uses TimSort — a stable, adaptive merge sort/insertion-sort hybrid, O(n log n) worst case, chosen because stability matters when objects carry additional state beyond the compared key.
Q102. How do you check if an array contains a duplicate within k indices of each other?
A: Use a sliding window of size k with a HashSet: for each element, check if it's already in the set (meaning a duplicate exists within the last k elements); if the window exceeds size k, remove the element that just fell out of the window from the set. This is O(n) time, O(k) space, and avoids the O(n²) cost of checking every pair within range.
Q103. How do you find the maximum length of a contiguous subarray with an equal number of 0s and 1s?
A: Convert 0s to -1 conceptually, then this becomes "find the longest subarray summing to zero." Track a running sum and store the first index where each running-sum value was seen in a HashMap; whenever the same running sum recurs, the subarray between the two occurrences has a net sum of zero (equal 0s and 1s), so update the max length using the distance between indices. This is O(n) time, O(n) space.
Q104. How do you efficiently merge k sorted arrays into one sorted array?
A: Use a min-heap (PriorityQueue) seeded with the first element of each array along with its array/index metadata. Repeatedly pop the smallest element, add it to the result, and push the next element from that same array if one remains. This runs in O(N log k) time, where N is the total number of elements across all arrays — much better than concatenating and sorting everything, which would be O(N log N).
int[] mergeKSorted(int[][] arrays) {
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int total = 0;
for (int i = 0; i < arrays.length; i++) {
if (arrays[i].length > 0) heap.offer(new int[]{arrays[i][0], i, 0});
total += arrays[i].length;
}
int[] result = new int[total];
int idx = 0;
while (!heap.isEmpty()) {
int[] top = heap.poll();
result[idx++] = top[0];
int arr = top[1], pos = top[2] + 1;
if (pos < arrays[arr].length) heap.offer(new int[]{arrays[arr][pos], arr, pos});
}
return result;
}Q105. How do you check if a string can become a palindrome by removing at most one character?
A: Use two pointers from both ends; while characters match, move both inward. On the first mismatch, try skipping either the left character or the right character (two branches) and check if the remaining substring is a palindrome using the standard two-pointer palindrome check. If either branch succeeds, the answer is true. This is O(n) time since each branch check is a linear palindrome scan performed at most once.
Q106. How do you implement wildcard string matching with '?' and '*' patterns?
A: Use 2D DP where dp[i][j] means the first i characters of the string match the first j characters of the pattern. '?' matches any single character (dp[i][j] = dp[i-1][j-1] if characters "match"); '*' matches any sequence including empty (dp[i][j] = dp[i-1][j] || dp[i][j-1], representing "use * to consume one more text char" or "treat * as matching nothing"). This is O(n×m) time and space, reducible to O(m) space with a rolling row.
Q107. How do you find the majority element that appears more than n/3 times (there can be up to two such elements)?
A: Generalize Boyer-Moore voting to track two candidates and two counters simultaneously. Scan the array: update matching candidate's count, or assign an empty candidate slot, or decrement both counts if neither matches. After the pass, verify both candidates actually appear more than n/3 times with a final counting pass (the algorithm can produce false positives that must be confirmed). This is O(n) time, O(1) space, versus O(n) space for a full frequency map.
Q108. Why is System.arraycopy() generally faster than a manual for-loop copy in Java?
A: System.arraycopy() is a native method that the JVM can implement using highly optimized, often hardware-accelerated bulk memory-move instructions (like memmove), and it correctly handles overlapping source/destination ranges. A manual for-loop copy is bytecode-interpreted or JIT-compiled per-element, incurring per-iteration overhead (bounds checks, loop control) that the JIT may or may not fully eliminate. Both are O(n) asymptotically, but arraycopy has a significantly lower constant factor in practice.
Q109. How do you check if a string has all unique characters?
A: Use a boolean array or bitset sized to the character set (e.g., 128 for ASCII) to mark each character as seen; if a character is encountered that's already marked, return false immediately. This is O(n) time, O(1) space for a bounded alphabet. If the input is restricted to lowercase letters, a single 32-bit integer used as a bitmask can track "seen" status with O(1) space and no array allocation at all.
boolean isUnique(String s) {
boolean[] seen = new boolean[128];
for (char c : s.toCharArray()) {
if (seen[c]) return false;
seen[c] = true;
}
return true;
}Q110. How do you rearrange an array so that positive and negative numbers alternate, preserving relative order as much as possible?
A: A simple O(n) time, O(n) space approach separates elements into two lists (positives, negatives) in one pass, then merges them back alternately. An in-place O(n²) approach rotates a subarray to bring the next needed-sign element to the correct position without extra space, trading space for time. Interviewers usually accept the two-list approach unless O(1) extra space is explicitly required.
Q111. How do you find the length of the longest substring with at most k distinct characters?
A: Use a variable-size sliding window with a frequency map of characters currently in the window. Expand the right edge, adding characters; whenever the number of distinct characters (map size) exceeds k, shrink from the left, decrementing counts and removing entries that hit zero, until the distinct count is back to ≤ k. Track the max window length throughout. This is O(n) time since both pointers only move forward.
Q112. How do you count the number of distinct substrings of a string?
A: A brute-force approach generates all O(n²) substrings and inserts them into a HashSet, costing O(n³) time overall due to substring hashing/comparison costs. The efficient approach builds a suffix trie or suffix array with an LCP (longest common prefix) array: the total number of distinct substrings equals n*(n+1)/2 minus the sum of LCP values between adjacent sorted suffixes, computable in O(n log n) with a suffix array or O(n) with a suffix automaton.
Q113. What is the time complexity of StringBuilder.insert() compared to StringBuilder.append()?
A: append() adds to the end and is O(1) amortized, same as ArrayList's add, because the internal char array only needs occasional resizing. insert() at an arbitrary position is O(n) because all characters after the insertion point must be shifted right to make room, similar to inserting into the middle of an array. Prefer building strings by appending in the natural order rather than repeatedly inserting at the front.
Q114. How do you convert between a 1D array index and 2D matrix (row, column) coordinates?
A: For a matrix with cols columns, a 1D index idx maps to row = idx / cols and col = idx % cols. Conversely, given (row, col), the 1D index is row * cols + col. This mapping is commonly used to binary-search a 2D matrix as if it were a flattened sorted 1D array, avoiding the need for nested loops.
int rows = matrix.length, cols = matrix[0].length;
int low = 0, high = rows * cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int value = matrix[mid / cols][mid % cols];
if (value == target) { /* found */ break; }
else if (value < target) low = mid + 1;
else high = mid - 1;
}Q115. Why could heavy use of String.substring() cause memory issues in old Java versions, and how was it fixed?
A: Before Java 7u6, substring() shared the original character array internally, only storing a new offset and length — this made substring O(1) but meant even a tiny substring kept the entire original (potentially huge) char array alive in memory, preventing it from being garbage collected. Since Java 7u6, substring() always copies the relevant characters into a new array, making it O(n) but eliminating that memory-retention hazard, at the cost of losing the old O(1) fast path.
Post a Comment
Add