How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Meta during technical interviews.

Implement randomized Quickselect without k-shift bug

Quick Overview

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.

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.

Input: ([1], 1)

Expected Output: 1

Explanation: Single element; the 1st largest is the only element.

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

Expected Output: 7

Explanation: All duplicates; every order statistic equals 7.

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

Expected Output: -1

Explanation: All negatives; the largest (k=1) is -1.

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

Expected Output: -5

Explanation: All negatives; the 5th largest (k=n) is the minimum, -5.

Input: ([5, 4, 3, 2, 1], 5)

Expected Output: 1

Explanation: Already sorted descending (adversarial for fixed pivots); k=n returns the minimum, 1.

Input: ([2, 1], 1)

Expected Output: 2

Explanation: Two-element array; the 1st largest is 2.

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.

Quick Overview