Design a Class with Save and N-th Smallest Query

Coding · Medium · Free problem

Implement run_ops(ops), which replays a list of operations on an order-statistic store.

Each operation is one of: - ["save", x] — store the integer x (duplicates are kept). - ["query", n] — return the n-th smallest stored integer (1-indexed; duplicates count as distinct positions).

Return the list of results, one per query op, in the order the queries appear. save ops produce no output.

Function signature: run_ops(ops) where ops is a list of ["save", x] / ["query", n] operations, returning a list of ints.

Example

run_ops([["save",5],["save",3],["save",8],["save",1],["save",3],["query",1],["query",2],["query",3],["query",4]]) -> [1, 3, 3, 5]

After the saves the sorted store is [1, 3, 3, 5, 8], so the 1st/2nd/3rd/4th smallest values are 1, 3, 3, 5 respectively.

Hints

  1. Ask the interviewer: are saves or queries more frequent? The answer determines which operation to optimize.
  2. For the general case, you need a data structure that supports both dynamic insertion and rank-based access efficiently. Think balanced BST augmented with subtree sizes.
  3. An order-statistic tree gives $O(\log k)$ for both save and query. In Python, sortedcontainers.SortedList provides this. For save-heavy workloads, an unsorted list with quickselect is better.

Worked Solution

Maintain a running collection of every integer added by a save op. For each query n op, the n-th smallest stored value (1-indexed, duplicates counted) is simply the element at index n-1 of the sorted collection. Collect one result per query op and return them in order — save ops produce no output.

```python def run_ops(ops): store = [] results = [] for op in ops: kind = op[0] if kind == "save": store.append(op[1]) elif kind == "query": n = op[1] results.append(sorted(store)[n - 1]) return results ```

Intuition

This problem is really about understanding the time-space trade-off spectrum in data structure design. At one extreme, you do no work on insert and all work on query (unsorted list + quickselect). At the other extreme, you do all work on insert and none on query (sorted array). The balanced BST sits in the middle, splitting the work evenly with $O(\log k)$ for both.

In real systems -- and in trading infrastructure -- this trade-off shows up constantly. A limit order book, for example, needs fast insertion of new orders and fast queries for the best bid/offer (a special case of the 1st-smallest query). The choice between a sorted structure and a heap depends on exactly what queries you need. Interviewers want to see that you think about the workload before jumping to a solution.

Related problems

Open the full interactive solver →