Array Problems
Now that you understand arrays, let's solve classic problems that frequently appear in interviews. Mastering these patterns will boost your confidence.
1. Reverse an array
Swap elements from both ends until the middle.
public static 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--;
}
}
2. Rotate array by k positions
Right rotate by k: reverse entire, then reverse first k, then reverse rest.
public static void rotate(int[] arr, int k) {
k = k % arr.length;
reverse(arr, 0, arr.length - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, arr.length - 1);
}
private static void reverse(int[] arr, int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++; end--;
}
}
3. Merge two sorted arrays
Merge into a new array, picking smaller each time.
public static 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) {
if (a[i] < b[j]) result[k++] = a[i++];
else result[k++] = b[j++];
}
while (i < a.length) result[k++] = a[i++];
while (j < b.length) result[k++] = b[j++];
return result;
}
Two Minute Drill
- Reverse: O(n) time, O(1) space.
- Rotate using three reverses: O(n) time, O(1) space.
- Merge two sorted arrays: O(n+m) time, O(n+m) space.
- These are building blocks for more complex problems.
Need more clarification?
Drop us an email at career@quipoinfotech.com