Query Kth Smallest Trimmed Number

Query Kth Smallest Trimmed Number

What is this problem about?

The Query Kth Smallest Trimmed Number problem gives you an array of equal-length number strings and queries (k, trim). Each query trims each number to its last trim digits and returns the k-th smallest among those trimmed values (using original index for tiebreaking). This coding problem uses multiple sorting approaches including radix sort. The array, sorting, heap, string, and quickselect interview pattern is comprehensively tested.

Why is this asked in interviews?

Goldman Sachs and DE Shaw ask this to test string-based sorting with custom comparators and the ability to choose the right sorting approach (heap for k-th element, radix sort for efficiency). The k-th smallest query maps directly to partial sorting algorithms.

Algorithmic pattern used

Sort by trimmed suffix + index. For each query (k, trim): extract (trimmed_string, original_index) pairs for all numbers. Sort by (trimmed_string, original_index). Return original_index of the k-th element. Optimize with radix sort for multiple queries on the same trim length.

Example explanation

nums=["102","473","251","814"], queries=[(1,1),(2,3),(4,2)].

• Query (1,1): trim to last 1 digit: [2,3,1,4]. Sorted: [(1,2),(2,0),(3,1),(4,3)]. 1st smallest → index 2.
• Query (2,3): full strings sorted: [(102,0),(251,2),(473,1),(814,3)]. 2nd → index 0.
• Query (4,2): last 2 digits: [02,73,51,14]. Sorted: [(02,0),(14,3),(51,2),(73,1)]. 4th → index 1.

Common mistakes candidates make

• Not including original index in tiebreaking.
• Using integer comparison instead of string lexicographic comparison for trimmed numbers.
• Off-by-one in k (1-indexed vs 0-indexed).
• Not handling equal trimmed strings (smallest original index wins).

Interview preparation tip

Kth Smallest Trimmed Number tests custom comparator sorting. The key: sort by (trimmed_string_lexicographic, original_index). String comparison of zero-padded numbers equals numeric comparison. For multiple queries with the same trim length, batch and reuse sorted order. Practice similar "sort with custom key, find kth element" problems — quickselect or heap are both valid.