Find Kth largest element in an array

Question

I am preparing for interviews where my code would be judged based on optimizations, OOP concepts, code readability as well as my knowledge of JAVA and design patterns.

What comments will you give in code review for the below code?

This is my code for Kth Largest element in an Array. The logic is to create a K size max heap, and then add the smallest K elements to the heap. Total array size can be equal to INT_MAX and k can be as small as 2

import java.util.Comparator;
import java.util.PriorityQueue;


public class CustomArray {

    class DecreasingComparator implements Comparator<Long> {

        @Override
        public int compare(Long firstNumber , Long secondNumber) {
            return (int) (secondNumber - firstNumber);
        }
    }

    public long findKthLargestElement(long[] input, int k) {
        if(k < 1 || k > input.length) {
            throw new IllegalArgumentException("Invalid k, should be between 1 and arra length");
        }

        PriorityQueue<Long> heap = new PriorityQueue<>(k, new DecreasingComparator());

        for(int i=0; i<k;i++) {
            heap.add(input[i]);
        }
        for(int i=k; i<input.length;i++) {
            if(heap.peek() > input[i]) {
                heap.poll();
                heap.add(input[i]);
            }
        }

        return heap.poll();
    }
}

Answer 1

Total array size can be equal to INT_MAX and k can be as small as 2

Why not 1?

---

    @Override
    public int compare(Long firstNumber , Long secondNumber) {
        return (int) (secondNumber - firstNumber);
    }

I found myself several time staring at such a line and being sure, there can be NPE there! But it can and I'd suggest to add explicit checks (throwing is correct, my point is to do it explicitly).

The Comparator is seriously broken:

• casting from long to int can overflow
• subtraction can overflow, too

Use Long.compare.

---

PriorityQueue<Long> heap = new PriorityQueue<>(k, new DecreasingComparator());

That makes it simple, but boxing is not free. While a few small values get cached in a cache in java.lang.Long, for others an object must be created. This takes 16 bytes and the heap contains a reference to it (4 or 8 bytes). So you need 20 or 24 bytes per long in addition to the 8 it takes in the input array.

This may make a few megabytes if you want the millionth element. There's also an allocation, but with current smart GCs it's usually no big deal.

---

There's no need for a decreasing comparator, as you could find the input.length+1-kth smallest element instead.

Or you could use both and select the one giving you a smaller queue.

---

    for(int i=0; i<k;i++) {
        heap.add(input[i]);
    }
    for(int i=k; i<input.length;i++) {
        if(heap.peek() > input[i]) {
            heap.poll();
            heap.add(input[i]);
        }
    }

This is smart and avoids most of the boxing (for small k). It could use some comments and a lot of tests.

Answer 2

In Java 8, you can use Comparator.reverseOrder() instead of writing a custom comparator to do reverse sorting. You would then also avoid the potential overflow from subtracting and casting.

PriorityQueue<Long> heap = new PriorityQueue<>(k, Comparator.reverseOrder());

Answer 3

The class is named CustomArray but there is no visible reason why. Even Solver would be a better name, because this class certainly is not a custom array.

The class DecreasingComparator should be static, as it makes no reference to members of the enclosing class. And you don't need to create a new instance of this class every time you want to find a kth element. You could have just one instance and reuse it, since the class has no data, only logic. Of course, as 200_success already said, no need for a custom implementation at all.

Answer 4

This version uses Java 8's streams. I think it is relatively easy to understand, and I think that accounts for a lot in an interview. Sort array and take kth element (skip input.length - k to account for reverse order).

public long findKthLargestElement(long[] input, int k) {
    if(k < 1 || k > input.length) {
        throw new IllegalArgumentException("Invalid k, should be between 1 and array length");
    }

    return Arrays.stream(input)
            .sorted()
            .skip(input.length - k)   // jump to kth element
            .findFirst()              // retrieve element
            .getAsLong();             // no need for optional long, just return value
}

Using Java streams shows that you understand how they work and that you keep up with technology, even if they don't use Java 8 (or above, if and when they come out). They might feel that you could teach something to the programmers already hired.