Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Kth Smallest Number

Problem Statement

Given an unsorted array of numbers, find Kth smallest number in it.

Please note that it is the Kth smallest number in the sorted order, not the Kth distinct element.

Example 1:

Input: [1, 5, 12, 2, 11, 5], K = 3
Output: 5
Explanation: The 3rd smallest number is '5', as the first two smaller numbers are [1, 2].

Example 2:

Input: [1, 5, 12, 2, 11, 5], K = 4
Output: 5
Explanation: The 4th smallest number is '5', as the first three smaller numbers are
[1, 2, 5].

Example 3:

Input: [5, 12, 11, -1, 12], K = 3
Output: 11

.....

.....

.....

Like the course? Get enrolled and start learning!
M

Mike Xu

· 3 years ago

I think there is a mistake in the solution. The mutual recursion should be between median_of_medians and find_Kth_smallest_number_rec, rather than between median_of_medians and partition.

  • Having a mutual recursion between median_of_medians and partition: say we are at the end of median_of_medians and we have a medians list/array with 3 medians (let's say [95, 4, 5], and we call partition on this array. partition will call median_of_medians on this array, which will hit the first if statement inside median_of_medians and return the first median of the 3 medians (i.e.95). We are back in partition again and will try to find the pivot and do some sorting. This will sort the medians list/array into [4, 5, 95] and return the index of 95 which is equal to 2 inside this array (in reality it's m
P

Peter

· 4 years ago

An interesting problem, I think in a live coding test the max/min heap would pretty reasonable and show good knowledge of space/time complexity.

A

Adam Sweeney

· 4 years ago

The C++ solution is flawed. srand() should only be called once for the entire duration of a program. In the C++ solution, the function partition() calls srand(), but partition() is recursively called. This means that srand() is called multiple times, and it resets the PRNG every time it is called. If it is called multiple times in the same second, which is extremely likely, you get the exact same value every time, making it no better than the original QuickSelect algorithm. And that's before getting into the whole "rand() considered harmful" subject.

Show 2 replies
R

Richard Yuan

· 4 years ago

For using a max-heap vs. a min-heap, which solution in this case would an interviewer be looking for as the most optimal? It is hard to tell from the current time complexities listed which approach is fastest. Usually, we are taught that we would use the max-heap when we are looking for the Kth smallest number, but I understand that a min-heap could also be utilized to achieve the same goal.

Show 1 reply
M

Mike Xu

· 3 years ago

Could you elaborate on why "return partition(medians, 0, len(medians)-1)" is done when getting the medianOfMedians? Isn't it sufficient to do "return medianOfMedians(medians)"? Since calling partition with anything will just end up calling medianOfMedians with the same thing until it hits the base case of n

Show 2 replies