Heaps

Question 1

A program which takes a sequence of strings presented in “streaming” fashion: you cannot back up to read an earlier value. Your program must compute the k longest string in the sequence. All that is required is the k longest strings - it is not required to order these strings.

Time O(n log k)

Answer 1

public static List topK(int k, Iterator iter){

PriorityQueue minHeap = new PriorityQueue<>(k, (s1, s2) -> Integer.compare(s1.length(), s2.length()));

while(iter.hasNext()){

minHeap.add(iter.next());

if(minHeap.size() > k){

minHeap.poll();

}

}

return new ArrayList<>(minHeap);

}

Question 2

Write a program that takes as input a set of sorted sequences and computes the union of these sequences as a sorted sequence.

Time O(n log k)

Space O(k)

Answer 2

public class SortedArraysMerge {

private static class ArrayEntry {
public Integer value;
public Integer arrayId;

public ArrayEntry(Integer value, Integer arrayId) {
 this.value = value;
 this.arrayId = arrayId;
 }
 }

@EpiTest(testDataFile = “sorted_arrays_merge.tsv”)

public static List
mergeSortedArrays(List> sortedArrays) {

List\> iters = new ArrayList\<\>(sortedArrays.size());
 for (List array : sortedArrays) {
 iters.add(array.iterator());
 }
 PriorityQueue minHeap = new PriorityQueue\<\>(
 sortedArrays.size(), (o1, o2) -\> Integer.compare(o1.value, o2.value));
 for (int i = 0; i \< iters.size(); ++i) {
 if (iters.get(i).hasNext()) {
 minHeap.add(new ArrayEntry(iters.get(i).next(), i));
 }
 }

List result = new ArrayList\<\>();
 while (!minHeap.isEmpty()) {
 ArrayEntry headEntry = minHeap.poll();
 result.add(headEntry.value);
 if (iters.get(headEntry.arrayId).hasNext()) {
 minHeap.add(new ArrayEntry(iters.get(headEntry.arrayId).next(),
 headEntry.arrayId));
 }
 }
 return result;
 }

Question 3

An array is said to be k-increasing-decreasing if elements repeatedly increase up to a certain index after which they decrease, then again increase, a total of k times.

Design an efficient algorithem for sorting a k-increasing-decreasing array.

Time O(n log k)

Answer 3

public class SortIncreasingDecreasingArray {
 @EpiTest(testDataFile = "sort\_increasing\_decreasing\_array.tsv")

public static List sortKIncreasingDecreasingArray(List A) {

// Decomposes A into a set of sorted arrays.
List> sortedSubarrays = new ArrayList<>();
SubarrayType subarrayType = SubarrayType.INCREASING;
int startIdx = 0;
for (int i = 1; i <= A.size(); ++i) {
if (i == A.size() // A is ended. Adds the last subarray
|| (A.get(i - 1) < A.get(i) &&
subarrayType == SubarrayType.DECREASING) ||
(A.get(i - 1) >= A.get(i) &&
subarrayType == SubarrayType.INCREASING)) {
List subList = A.subList(startIdx, i);
if (subarrayType == SubarrayType.DECREASING) {
Collections.reverse(subList);
}
sortedSubarrays.add(subList);
startIdx = i;
subarrayType = (subarrayType == SubarrayType.INCREASING ? SubarrayType.DECREASING : SubarrayType.INCREASING);
}
}
return SortedArraysMerge.mergeSortedArrays(sortedSubarrays);
}

private enum Su

Question 4

Write a program which takes as input a very long sequence of numbers and prints the numbers in sorted order. Each number is at most k away from its correctly sorted poristion(k-sorted)

Time O(n log k)

Space O(k)

Answer 4

public class SortAlmostSortedArray {

public static List
sortApproximatelySortedData(Iterator sequence, int k) {

PriorityQueue minHeap = new PriorityQueue\<\>();
 // Adds the first k elements into minHeap. Stop if there are fewer than k
 // elements.
 for (int i = 0; i \< k && sequence.hasNext(); ++i) {
 minHeap.add(sequence.next());
 }

List result = new ArrayList<>();
// For every new element, add it to minHeap and extract the smallest.
while (sequence.hasNext()) {
minHeap.add(sequence.next());
Integer smallest = minHeap.remove();
result.add(smallest);
}

// sequence is exhausted, iteratively extracts the remaining elements.
result.addAll(Stream.generate(minHeap::remove)
.limit(minHeap.size())
.collect(Collectors.toList()));
return result;
}

Question 5

How would you compute the k stars which are closest to Earth?

Time O(n log k)

space O(k)

Answer 5

public class KClosestStars {
 @EpiUserType(ctorParams = {double.class, double.class, double.class})

public static class Star implements Comparable {
 private double x, y, z;

public Star(double x, double y, double z) {
 this.x = x;
 this.y = y;
 this.z = z;
 }

public double distance() { return Math.sqrt(x * x + y * y + z * z); }

@Override
public int compareTo(Star that) {
return Double.compare(this.distance(), that.distance());
}

@Override
public String toString() {
return String.valueOf(distance());
}
}

public static List findClosestKStars(Iterator stars, int k) {

// maxHeap to store the closest k stars seen so far.
PriorityQueue maxHeap =
new PriorityQueue<>(k, Collections.reverseOrder());
while (stars.hasNext()) {
// Add each star to the max-heap. If the max-heap size exceeds k, remove
// the maximum element from the max-heap.
Star star = stars.next();
maxHeap.add(star);
if (maxHeap.size() == k + 1) {
maxHeap.remove();
}
}

// Iteratively extract from the max-heap, which yields the stars sorted
// according from furthest to closest.
return Stream.generate(maxHeap::remove)
.limit(maxHeap.size())
.collect(Collectors.toList());
}

Question 6

Design an agorithm for computing the running median of a sequence.

Time O(log n)

Answer 6

public class OnlineMedian {

private static final int DEFAULT_INITIAL_CAPACITY = 16;

public static List onlineMedian(Iterator sequence) {

// minHeap stores the larger half seen so far.
 PriorityQueue minHeap = new PriorityQueue\<\>();
 // maxHeap stores the smaller half seen so far.
 PriorityQueue maxHeap = new PriorityQueue\<\>(
 DEFAULT\_INITIAL\_CAPACITY, Collections.reverseOrder());
 List result = new ArrayList\<\>();

while (sequence.hasNext()) {
int x = sequence.next();
minHeap.add(x);
maxHeap.add(minHeap.remove());
// Ensure minHeap and maxHeap have equal number of elements if
// an even number of elements is read; otherwise, minHeap must have
// one more element than maxHeap.
if (maxHeap.size() > minHeap.size()) {
minHeap.add(maxHeap.remove());
}

result.add((minHeap.size() == maxHeap.size() ? 0.5 * (minHeap.peek() + maxHeap.peek())
: (double)minHeap.peek()));
}
return result;
}

Question 7

Given a max-heap, represented as an array A, design an algorithm that computes the k largest elements stored in the max-heap. You cannot modify the heap.

Time O(k log k)

Spece O(k)

Answer 7

public class KLargestInHeap {

private static class HeapEntry {
public Integer index;
public Integer value;

public HeapEntry(Integer index, Integer value) {
 this.index = index;
 this.value = value;
 }
 }

private static final int DEFAULT_INITIAL_CAPACITY = 16;

@EpiTest(testDataFile = “k_largest_in_heap.tsv”)

public static List kLargestInBinaryHeap(List A, int k) {

if (k <= 0) {
return Collections.emptyList();
}

// Stores the (index, value)-pair in candidateMaxHeap. This heap is
// ordered by the value field.
PriorityQueue candidateMaxHeap =
new PriorityQueue<>(DEFAULT_INITIAL_CAPACITY,
(o1, o2) -> Integer.compare(o2.value, o1.value));
candidateMaxHeap.add(new HeapEntry(0, A.get(0)));
List result = new ArrayList<>();
for (int i = 0; i < k; ++i) {
Integer candidateIdx = candidateMaxHeap.peek().index;
result.add(candidateMaxHeap.remove().value);

Integer leftChildIdx = 2 \* candidateIdx + 1;
 if (leftChildIdx \< A.size()) {
 candidateMaxHeap.add(new HeapEntry(leftChildIdx, A.get(leftChildIdx)));
 }
 Integer rightChildIdx = 2 \* candidateIdx + 2;
 if (rightChildIdx \< A.size()) {
 candidateMaxHeap.add(
 new HeapEntry(rightChildIdx, A.get(rightChildIdx)));
 }
 }
 return result;
 }