K-th Smallest Prime Fraction

K-th Smallest Prime Fraction

1. What is this problem about?

The K-th Smallest Prime Fraction interview question gives you a sorted array of prime numbers. You can form fractions arr[i] / arr[j] for all $i < j$. Your goal is to find the $k^{th}$ smallest fraction among all possible pairs.

2. Why is this asked in interviews?

Companies like Microsoft and Amazon ask the Prime Fraction coding problem to test your knowledge of Priority Queues and Binary Search on the answer. It’s a test of whether you can find an element in a virtually sorted set of combinations without generating all $O(N^2)$ fractions.

3. Algorithmic pattern used

This problem can be solved with a Min-Heap or Binary Search on Value.

• Min-Heap approach:
  1. For each $j$, the smallest fraction is arr[0] / arr[j]. Push all (arr[0]/arr[j], 0, j) into a Min-Heap.
  2. Pop the smallest element $k$ times.
  3. When you pop (val, i, j), push the next candidate (arr[i+1]/arr[j], i+1, j).
• Binary Search approach: Binary search for a value $X$ such that exactly $k$ fractions are $\leq X$.

4. Example explanation

arr = [1, 2, 3, 5], $k = 3$

1. Initial Heap: {1/5, 1/3, 1/2}.
2. Pop 1/5 (smallest). Push next for index $j=3$: 2/5. Heap: {1/3, 2/5, 1/2}.
3. Pop 1/3. Push next for index $j=2$: 2/3. Heap: {2/5, 1/2, 2/3}.
4. Pop 2/5. This is the $3^{rd}$ smallest. Result: [2, 5].

5. Common mistakes candidates make

• Generating all fractions: $O(N^2)$ time and space, which fails for $N=1000$ if $k$ is large.
• Precision errors: Using floating-point binary search without a strict epsilon or count check.
• Heap mapping: Forgetting to store the indices $(i, j)$ in the heap so you can find the "next" fraction.

6. Interview preparation tip

The "Pop and Push Next" heap pattern is essential for problems involving merging multiple sorted sequences (in this case, each denominator defines a sequence). This is a top-tier Heap interview pattern skill.