Selection and Partial Sorting

If a product asks for the top 10 items, sorting one million items completely may be wasteful. Selection asks for only the part of the order you need: kth largest, top k, or a bounded leaderboard.

Full Order Versus Partial Order

Full sorting gives every item a final rank. Partial sorting only guarantees the requested portion. A heap of size k is often strong when k is small, especially for streaming data where all items cannot be sorted at once.

Scenario: Dashboard Top Errors

An observability dashboard shows the top 20 error signatures in the last hour. Sorting every distinct signature is simple. But if cardinality is high and the dashboard updates continuously, a bounded heap or streaming heavy-hitter design may be better.

Same Pattern in Java, Python, and JavaScript

The following examples return the k largest values using a min-heap of size k.

import java.util.*;

class TopK {
    static List<Integer> topK(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int value : nums) {
            heap.add(value);
            if (heap.size() > k) heap.poll();
        }
        List<Integer> result = new ArrayList<>(heap);
        result.sort(Comparator.reverseOrder());
        return result;
    }
}

Tie Policy and Determinism

Selection is not complete without tie rules. If two products have the same score, should newer win, older win, lower ID win, or should the order be arbitrary? Production ranking systems need deterministic tie-breaking.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return the k largest values without fully sorting all values.
• Return the k most frequent numbers.
• Return k points closest to the origin.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class TopKAnswer {
    static List<Integer> topK(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int value : nums) {
            heap.offer(value);
            if (heap.size() > k) heap.poll();
        }
        List<Integer> result = new ArrayList<>(heap);
        result.sort(Comparator.reverseOrder());
        return result;
    }
}

import java.util.*;
class TopKFrequent { static List<Integer> topK(int[] nums, int k) { Map<Integer,Integer> count = new HashMap<>(); for (int x : nums) count.put(x, count.getOrDefault(x,0)+1); PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(count::get)); for (int x : count.keySet()) { heap.offer(x); if (heap.size() > k) heap.poll(); } return new ArrayList<>(heap); } }

import java.util.*;
class KClosest { static int[][] closest(int[][] points, int k) { Arrays.sort(points, Comparator.comparingInt(p -> p[0]*p[0] + p[1]*p[1])); return Arrays.copyOf(points, k); } }

Solved modelWorked Interview Answer

Return the k largest values without fully sorting all values. Maintain a min-heap of size k. The heap root is the weakest winner; any stronger candidate can replace it.

import java.util.*;

class TopKAnswer {
    static List<Integer> topK(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int value : nums) {
            heap.offer(value);
            if (heap.size() > k) heap.poll();
        }
        List<Integer> result = new ArrayList<>(heap);
        result.sort(Comparator.reverseOrder());
        return result;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Sorting everything when only k items are required.
• Using a heap without defining tie-breaking.
• Forgetting that heap output may not be sorted.
• Choosing quickselect when deterministic worst-case behavior is required.
• Ignoring k close to n, where full sort may be simpler.

Execution guardrailQuick-Start Checklist

• Ask whether full order is needed.
• Compare n and k.
• Choose sort, heap, or quickselect.
• Define tie policy.
• State output ordering guarantee.
• State runtime and memory.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice kth largest, top k frequent, k closest points, and streaming median later.
• Study heaps before priority queue module.
• Compare exact top-k with approximate heavy-hitter algorithms for streams.