Single Query Type, Max Revenue in K Minutes

A virtual warehouse can execute one of `n` query types. Each query type has a per-run revenue and per-run duration. Pick a single query type and run it as many times as fits in `k` minutes; return the chosen type and the maximum total revenue. Requirements Input: n query types, each with (duration_i, revenue_i). Time budget: k minutes. Only one query type may be selected; that type runs back-to-back, integer count of times. Output: the selected query type index and the maximum total revenue achievable. Ties between query types are broken arbitrarily unless specified. Notes For each candidate type i, the number of runs fitting in k minutes is floor(k / duration_i), and the total revenue is floor(k / duration_i) * revenue_i. One linear scan over the types, track the maximum revenue and the corresponding type. O(n). This is not the knapsack variant — the single-type constraint collapses the search space dramatically. Edge cases: duration_i > k (zero runs, zero revenue for that type), duration_i == 0 (degenerate; clarify), multiple types tied on max revenue (return any). Common stumbling: candidates immediately reach for unbounded-knapsack DP and over-complicate the round. Read the constraint that only one type may be chosen. Preparation Implement the linear scan in under 5 minutes; spend the rest of the round on follow-ups the interviewer raises (allowing multiple types, partial runs, etc.). Be ready to articulate why this is not a knapsack — the single-type constraint is what makes the linear scan optimal.