How should I practice QuickSelect Kth Smallest?

Start by reading the full statement, solve the visible examples, then compare the pattern against related ByteDance phone screen problems in FastPrep.

Is QuickSelect Kth Smallest associated with ByteDance?

FastPrep tags this as a ByteDance phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

QuickSelect Kth Smallest

Learn this problem

● Medium

ByteDanceFULLTIMEPHONE SCREEN

Problem statement

Given an integer array nums and an integer k, return the kth smallest value in the array.

k is one-indexed. Duplicate values occupy separate ranks, just as they do in the fully sorted array.

Solve the problem with a selection algorithm whose expected running time is O(n).

Function

kthSmallest(nums: int[], k: int) → int

Examples

Example 1

nums = [3,2,1,5,6,4]k = 2return = 2

In sorted order the values are [1,2,3,4,5,6], so the second smallest value is 2.

Example 2

nums = [7,7,2,9,1]k = 4return = 7

The sorted ranks are [1,2,7,7,9]. Counting duplicates separately, rank 4 contains 7.

Constraints

1 <= nums.length <= 100000
-10^9 <= nums[i] <= 10^9
1 <= k <= nums.length