Quick Overview

Find the largest k occurrences with partition-based selection, sort only the output, and compare quickselect pivot risks with heap and full-sort alternatives.

Find the Largest K Elements with Partitioning

Company: AMD

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Return the largest k values from an array, preserving duplicate occurrences. Compare a heap solution with a partition-based selection approach and explain when each is attractive. Implement `largest_k(values: int[], k: int) -> int[]`. Return the selected values in nonincreasing order. The sorted output is a practice presentation convention; the selection itself should not require sorting the entire array. ### Constraints & Assumptions - `0 <= len(values) <= 200000`, `0 <= k <= len(values)`, and values lie in signed 32-bit range. - Duplicate values count separately. Return exactly k values; no distinct-value deduplication. - k=0 returns an empty list. k equal to the input length returns all values sorted descending. - The input may be modified internally, or copied if you state the additional memory cost. - Aim for expected O(n + k log k) time using selection plus output sorting. Discuss worst-case behavior rather than claiming a naive quickselect implementation is always linear. ### Examples ```text values = [7,1,9,9,3], k = 3 result = [9,9,7] ``` ```text values = [-4,-1,-3], k = 1 result = [-1] ``` The reported interview discussed a heap but preferred quickselect/quicksort-style partitioning. Explain pivot choice, duplicate handling, how the selected partition is identified, and why only that partition needs output sorting. Compare with O(n log k) heap work and full sorting, including streaming or very small-k cases. ```hint Separate selection from ordering Locate the boundary between selected and unselected values first. The required output order only concerns the k selected occurrences. ```

Overview: Find the largest k occurrences with partition-based selection, sort only the output, and compare quickselect pivot risks with heap and full-sort alternatives.

Read the full AMD Software Engineer interview experience this question came from

Return the largest k values from an array, preserving duplicate occurrences. Compare a heap solution with a partition-based selection approach and explain when each is attractive. Implement `largest_k(values: int[], k: int) -> int[]`. Return the selected values in nonincreasing order. The sorted output is a practice presentation convention; the selection itself should not require sorting the entire array. ### Constraints & Assumptions - `0 <= len(values) <= 200000`, `0 <= k <= len(values)`, and values lie in signed 32-bit range. - Duplicate values count separately. Return exactly k values; no distinct-value deduplication. - k=0 returns an empty list. k equal to the input length returns all values sorted descending. - The input may be modified internally, or copied if you state the additional memory cost. - Aim for expected O(n + k log k) time using selection plus output sorting. Discuss worst-case behavior rather than claiming a naive quickselect implementation is always linear. ### Examples ```text values = [7,1,9,9,3], k = 3 result = [9,9,7] ``` ```text values = [-4,-1,-3], k = 1 result = [-1] ``` The reported interview discussed a heap but preferred quickselect/quicksort-style partitioning. Explain pivot choice, duplicate handling, how the selected partition is identified, and why only that partition needs output sorting. Compare with O(n log k) heap work and full sorting, including streaming or very small-k cases. ```hint Separate selection from ordering Locate the boundary between selected and unselected values first. The required output order only concerns the k selected occurrences. ```

Constraints

  • 0 <= len(values) <= 200000; 0 <= k <= len(values); values are signed 32-bit integers.
  • Duplicate values count as separate occurrences; return exactly k selected values in nonincreasing order.
  • k=0 returns []; k equal to input length returns all values descending.
  • The implementation copies the input and accounts for that storage.
  • Select before sorting the output; do not sort the entire array unless it is the selected output.

Examples

Input: ([7, 1, 9, 9, 3], 3)

Expected Output: [9, 9, 7]

Explanation: Duplicate maxima remain separate selected occurrences.

Input: ([-4, -1, -3], 1)

Expected Output: [-1]

Explanation: All-negative input selects the greatest value.

Loading coding console...

Show the approach

Approach

Copy the input and select the ascending rank n-k, which separates the k largest occurrences into the final suffix. Use three-way partitioning into less than, equal to and greater than a pivot, narrowing only the part containing that rank. Equal values occupy a middle band, so duplicates neither disappear nor cause repeated one-element partitions. To avoid adversarial pivot behavior, choose a deterministic median-of-medians pivot: sort groups of at most five, move their medians into a prefix, recursively select the median of that prefix, then partition the active range. This guarantees a constant fraction can be discarded apart from a fixed-size remainder; the standard T(n)<=T(n/5)+T(7n/10+O(1))+O(n) recurrence yields worst-case O(n) selection. Only groups of at most five and the selected suffix are sorted, not the whole input unnecessarily. Finally sort the suffix descending and return exactly k values. The empty selection returns immediately; a full selection skips partitioning because all values are output. Total time is O(n+k log k) with O(n) copied storage and O(log n) selection recursion. A simpler randomized quickselect offers expected linear selection with less machinery but quadratic worst-case behavior; naive fixed pivots also admit quadratic examples. A size-k min-heap instead costs O(n log(k+1)) selection work and O(k) state, attractive for streaming or very small k. Full sorting costs O(n log n) and is simplest when all or nearly all values are needed.

Time complexity:
O(n + k log(k+1)) worst-case using median-of-medians selection
Space complexity:
O(n) copied input plus O(log n) selection stack and O(k) output