PPractick

The problem

A delivery app wants the k-th fastest delivery time of the day to set a realistic promise for customers. Sorting all times is O(n log n). Keeping a max-heap of the k smallest times seen so far is O(n log k): its root is the largest of those k, which is exactly the k-th smallest. Any new time smaller than the root replaces it. It's the mirror image of the k-th largest problem.

Example: [7, 10, 4, 3, 20, 15], k = 3 → 7.

Function signature

int kthSmallest(const vector<int>& arr, int k);  // 1 <= k <= n

Test cases

Input (arr, k)	Output	Explanation
([7, 10, 4, 3, 20, 15], 3)	7	Sorted: 3, 4, 7, …
([7, 10, 4, 20, 15], 4)	15
([1], 1)	1
([5, 5, 5, 1], 2)	5	Duplicates count
([2, -1, 0], 1)	-1	The minimum

(Confirm: k-th smallest counting duplicates; 1 ≤ k ≤ n.)

How interviewers phrase it

• "Given an array and a number k, find the k-th smallest element" (GeeksforGeeks "Kth smallest element"), "using a priority queue".

Clarifying questions to ask

1. Counting duplicates? (Yes.)
2. Is k always valid?
3. Can I modify the array? (If so, quickselect is an option.)

Follow-ups to expect

1. "Why a max-heap?"
2. "Why not a min-heap of everything?"
3. "When is the size-k heap better?"
4. "Quickselect?"
5. "Complexity?"

Related questions

• Implement Min Heap Medium
• Check if an array represents a min heap Medium
• Convert Min Heap to Max Heap Medium
• K-th Largest element in an array Medium
• Task Scheduler Medium
• Hand of Straights Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in