How to Succeed in Algorithms Interview Series
Merge Sort
- divide and conquer: left, right, count values while merging left and right
- merge procedure with auxiliary array
Merge sort code
private int merge(int[] A, int start, int mid, int end) {
int[] temp = new int[A.length];
int leftIndex = start;
int rightIndex = mid + 1;
int index = start;
int sum = 0;
while (leftIndex <= mid && rightIndex <= end) {
if (A[leftIndex] <= A[rightIndex]) {
temp[index++] = A[leftIndex++];
} else {
temp[index++] = A[rightIndex++];
sum += mid - leftIndex + 1;
}
}
while (leftIndex <= mid) {
temp[index++] = A[leftIndex++];
}
while (rightIndex <= end) {
temp[index++] = A[rightIndex++];
}
for (int i = start; i <= end; i++) {
A[i] = temp[i];
}
return sum;
}public Iterable<Integer> mergeKSortedIterators(Iterator<Integer>[] iters){
Queue<IntIter> minHeap = new PriorityQueue<IntIter>(iters.length, new iteratorComp());
List<Integer> result = new ArrayList<Integer>();
for(Iterator<Integer> iter : iters){
if(iter.hasNext()){
minHeap.add(new IntIter(iter));
}
}
while(!minHeap.isEmpty()){
IntIter curr = minHeap.poll();
result.add(curr.next);
if(curr.iter.hasNext()){
minHeap.add(new IntIter(curr.iter));
}. visit 1point3acres.com for more.
}
return result;
}
public class iteratorComp implements Comparator<IntIter>{
public int compare(IntIter a, IntIter b){
return a.next - b.next;
}
}
public class IntIter {
int next;
Iterator<Integer> iter;
public IntIter(Iterator<Integer> iter) {
this.next = iter.next();
this.iter = iter;
}
}Merge two sorted arrays
- Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. We can switch from one array to another array only at common elements
- LeetCode 632 - Smallest Range (shortest range in k-sorted lists)
- Find the smallest range that includes at least one number from each of the klists.
Divide and conquer + merge sort
- Count pairs in an array that hold iarr[i] > jarr[j]
- LeetCode 493 - Reverse Pairs: count inversions in an array
- Number of swaps to sort when only adjacent swapping allowed
- build the Binary Search Tree from right to left and search the partially built tree with nums[i]/2.0
public int reversePairs(int[] nums) { if (nums == null || nums.length == 0) return 0; return mergeSort(nums, 0, nums.length - 1); } private int mergeSort(int[] nums, int l, int r) { if (l >= r) return 0; int mid = l + (r - l)/2; int count = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r); int[] cache = new int[r - l + 1]; int i = l, t = l, c = 0; for (int j = mid + 1; j <= r; j++, c++) { while (i <= mid && nums[i] <= 2 * (long)nums[j]) i++; while (t <= mid && nums[t] < nums[j]) cache[c++] = nums[t++]; cache[c] = nums[j]; count += mid - i + 1; } while (t <= mid) cache[c++] = nums[t++]; System.arraycopy(cache, 0, nums, l, r - l + 1); return count; } - Positive-Negative partitioning preserving order
- merge in such a way that negative part of left and right sub-array is copied first followed by positive part of left and right sub-array
- LeetCode 315 - Count of Smaller Numbers After Self
- Augmented BST: dupCnt, smallerCnt
- merge sort
- count[i] = count of nums[j] - nums[i] < 0 with j > i
private Pair[] mergeSort(Pair[] arr, Integer[] smaller) { if (arr.length <= 1) { return arr; } int mid = arr.length / 2; Pair[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid), smaller); Pair[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length), smaller); for (int i = 0, j = 0; i < left.length || j < right.length;) { if (j == right.length || i < left.length && left[i].val <= right[j].val) { arr[i + j] = left[i]; smaller[left[i].index] += j; i++; } else { arr[i + j] = right[j]; j++; } } return arr; }
- LeetCode 327 - Count of Range Sum: return the number of range sums that lie in (lower, upper)
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.- Augmented BST: dupCnt, leftSize, rightSize
- merge sort
- count[i] = count of a <= S[j] - S[i] <= b with j > i
- In merge, separate calculate answer and merge to 2 steps ```java public int countRangeSum(int[] nums, int lower, int upper) { int n = nums.length; long[] sums = new long[n + 1]; for (int i = 0; i < n; ++i) sums[i + 1] = sums[i] + nums[i]; return countWhileMergeSort(sums, 0, n + 1, lower, upper); }
private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) { if (end - start <= 1) return 0; int mid = (start + end) / 2; int count = countWhileMergeSort(sums, start, mid, lower, upper) + countWhileMergeSort(sums, mid, end, lower, upper); int j = mid, k = mid, t = mid; long[] cache = new long[end - start]; for (int i = start, r = 0; i < mid; ++i, ++r) { while (k < end && sums[k] - sums[i] < lower) k++; while (j < end && sums[j] - sums[i] <= upper) j++; while (t < end && sums[t] < sums[i]) cache[r++] = sums[t++]; cache[r] = sums[i]; count += j - k; } System.arraycopy(cache, 0, sums, start, t - start); return count; } ```
- Shuffling a linked list
- Find a permutation that causes worst case of Merge Sort
- LeetCode 148 - Sort LinkedList
- fake head ListNode fakehead = new ListNode(-1);
- Maximum Sum Path in Two Arrays
- We can switch from one array to another array only at common elements.
