Katkat
Back

Maximize revenue by choosing one query type

SnowflakeSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests greedy optimization and modular arithmetic skills to determine the most profitable query strategy given a limited time window.

Problem Statement

You are managing a compute cluster and have a total time budget of T seconds. You are offered n types of queries. For each query type i, you are given:

  • duration[i]: The time in seconds it takes to process one query of this type.
  • revenue[i]: The monetary gain from completing one query of this type.

Because of cluster configuration constraints, you are allowed to choose exactly one query type to run repeatedly until the time budget T is exhausted. Your goal is to choose the query type that results in the maximum total revenue.

If two query types result in the same total revenue, choose the one with the smaller index i. If multiple queries are tied for the same revenue and index, the problem guarantees the input will be structured such that you pick the one that leaves the least remaining time unused. If still tied, pick the one with the lowest duration[i].

Function Signature

def maximize_revenue(T, duration, revenue):

Constraints

  • T is an integer where 1 <= T <= 10^12.
  • n (length of arrays) is 1 <= n <= 10^5.
  • duration[i] and revenue[i] are integers where 1 <= duration[i], revenue[i] <= 10^9.

Examples

Example 1: Input: T = 10, duration = [3, 4], revenue = [2, 3]

  • Query 0: 10 // 3 = 3 queries, 3 * 2 = 6 total revenue.
  • Query 1: 10 // 4 = 2 queries, 2 * 3 = 6 total revenue. Result: 0 (Tie-break on revenue: 6 vs 6; tie-break on index: 0 < 1).

Example 2: Input: T = 20, duration = [5, 2], revenue = [10, 4]

  • Query 0: 20 // 5 = 4 queries, 4 * 10 = 40 total revenue, 0 time remaining.
  • Query 1: 20 // 2 = 10 queries, 10 * 4 = 40 total revenue, 0 time remaining. Result: 0 (Tie-break on revenue: 40 vs 40; tie-break on index: 0 < 1).

Hints

Hint 1

Calculate the total revenue for each query type using the formula `(T // duration[i]) * revenue[i]`.

Hint 2

Be mindful that `T` can be very large, so use 64-bit integer arithmetic to prevent overflow during revenue calculations.

Hint 3

Use a single pass approach to track the best query found so far, updating your candidate whenever a new maximum is found or tie-breaking conditions are met.

Follow-up questions

  • How would your approach change if we could interleave different query types instead of choosing only one?
  • If we introduce a 'startup cost' for each query type that must be paid once before running it, how does this modify the optimization?
  • How would you optimize the search if the number of query types `n` were to grow to 10^9, but many queries shared the same ratio of `revenue/duration`?