Implement randomized Quickselect without k-shift bug
Company: Meta
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement randomized Quickselect to return the k-th largest element (1-based k, 1 ≤ k ≤ n) from an unsorted integer array. Use an in-place partition that places elements greater than the pivot to the left and less than the pivot to the right, returning the pivot’s final index p. Let rank = p - left + 1 (the number of elements ≥ pivot in the current subarray). If k == rank, return A[p]; if k < rank, recurse on [left..p-1]; otherwise recurse on [p+1..right] with k' = k - rank. Prove that this k-update rule prevents negative positions and off-by-one errors. Handle duplicates, very small arrays, and adversarial inputs by choosing a random pivot each iteration. Analyze expected time O(n) and worst-case time O(n^2), and specify auxiliary space. Finally, show how to adapt the same routine to find the k-th smallest and explain the difference from Quicksort.
Quick Answer: This question evaluates understanding of randomized Quickselect and selection algorithms, including in-place partition semantics for the k-th largest element, careful index and k-update reasoning to prevent k-shift/off-by-one bugs, handling duplicates and adversarial pivots, and analysis of expected versus worst-case time and auxiliary space.
Implement randomized Quickselect to return the k-th largest element (1-based k, 1 ≤ k ≤ n) from an unsorted integer array.
Use an in-place partition that places elements GREATER than the pivot to the left and elements LESS than the pivot to the right, returning the pivot's final index p. Let rank = p - left + 1 (the number of elements ≥ pivot in the current subarray, i.e. the pivot's 1-based rank within [left..right]).
- If k == rank, return A[p].
- If k < rank, recurse on the left side [left..p-1] keeping k unchanged.
- Otherwise recurse on the right side [p+1..right] with k' = k - rank.
The classic interview bug is writing the right-branch update as len(upper) - k instead of k - len(upper), which yields a negative target position. The rank-based form k' = k - rank above is always positive on the right branch (because we only take that branch when k > rank), which prevents negative positions and off-by-one errors.
Choose a random pivot each iteration to handle duplicates, very small arrays, and adversarial (already-sorted) inputs in expected O(n) time.
Return the value of the k-th largest element.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= k <= nums.length
- -10^9 <= nums[i] <= 10^9
- Array may contain duplicates
- k is 1-based (k = 1 means the maximum, k = n means the minimum)
Examples
Input: ([3, 2, 1, 5, 6, 4], 2)
Expected Output: 5
Explanation: Sorted descending: [6,5,4,3,2,1]; the 2nd largest is 5.
Input: ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
Expected Output: 4
Explanation: Descending with duplicates: [6,5,5,4,3,3,2,2,1]; the 4th largest is 4.
Hints
- Partition so that elements strictly greater than the pivot land to its left; then the pivot's 1-based rank within [left..right] is rank = p - left + 1.
- On the right branch you only recurse when k > rank, so k' = k - rank is always >= 1 — never write rank - k (that produces a negative target).
- Pick the pivot index uniformly at random each iteration to avoid O(n^2) on sorted/adversarial inputs; the iterative loop keeps auxiliary space at O(1).
- To find the k-th SMALLEST instead, either flip the comparison in partition (move LESS-than elements left) or call this routine with k' = n - k + 1.