Kth Smallest Instructions

Kth Smallest Instructions

1. What is this problem about?

The Kth Smallest Instructions interview question is a pathfinding and combinatorics problem. You are given a destination $(r, c)$ on a grid. You start at $(0, 0)$ and can only move Right ('H') or Down ('V'). You need to reach the destination using exactly $r$ vertical moves and $c$ horizontal moves. There are many such paths; your goal is to find the $k^{th}$ path when sorted lexicographically. Note that 'H' comes before 'V' alphabetically.

2. Why is this asked in interviews?

Amazon ask this coding problem to evaluate a candidate's mastery of Combinatorics and Greedy strategies. It tests whether you can use the combination formula $\binom{n}{k}$ to "count" how many paths start with a specific move, allowing you to skip entire groups of paths without generating them. It evaluations your Math interview pattern skills.

3. Algorithmic pattern used

This problem is solved using a Greedy Decision based on Combinations.

1. The Choice: At each step, you can either go 'H' or 'V'.
2. Counting Paths: If you choose 'H', you have $H-1$ horizontal and $V$ vertical moves remaining. The number of paths that could be formed starting with this 'H' is $\binom{(H-1) + V}{V}$.
3. Logic:
   • If $k \leq$ this count, the $k^{th}$ instruction must start with 'H'. Append 'H' and decrement $H$.
   • If $k >$ this count, the $k^{th}$ instruction must start with 'V'. Append 'V', subtract the count from $k$, and decrement $V$.
4. Repeat: Continue until the destination is reached.

4. Example explanation

Destination: (1, 1), $k = 2$.

• Options: HH (not possible), HV, VH.
• Step 1: Remaining H=1, V=1.
• If we pick 'H': remaining is H=0, V=1. Paths = $\binom{0+1}{1} = 1$.
• Since $k=2$ and $2 > 1$, we cannot pick 'H'.
• Pick 'V'. Result = "V". $k = 2 - 1 = 1$. V=0.
• Step 2: Remaining H=1, V=0. Only option is 'H'. Result: "VH".

5. Common mistakes candidates make

• Generating all paths: There are $\binom{H+V}{V}$ paths, which is too many to list or sort.
• Incorrect combination formula: Mistakes in calculating $\binom{n}{k}$, especially with large values (up to $\binom{30}{15}$).
• Lexicographical order: Forgetting that 'H' comes before 'V'.

6. Interview preparation tip

Learn the formula for n-choose-k and how to use Pascal's triangle to pre-calculate combinations. This "counting to skip" technique is the standard way to find the $k^{th}$ permutation or combination in Math interview patterns.