How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

Maximize revenue by choosing one query type

Quick Overview

This question evaluates optimization and numerical reasoning skills, specifically selecting a single repetitive action to maximize aggregate revenue under a tight time budget while handling integer division, large numeric bounds, and deterministic tie-breaking.

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given a virtual warehouse that can execute queries. There are **n** query types, and you must choose **exactly one** query type to run repeatedly for at most **k minutes**. For query type `i`: - Each run takes `time[i]` minutes (a positive integer). - Each run yields `profit[i]` revenue (a non-negative integer). - You may run the chosen query type any number of times back-to-back as long as total time does not exceed `k`. ### Task Return: 1. The **maximum total revenue** achievable within `k` minutes. 2. The **chosen query type index** (0-based) that achieves this maximum. If multiple query types yield the same maximum revenue, return the **smallest index**. ### Input - Integer `k` - Arrays `time[0..n-1]`, `profit[0..n-1]` ### Output - `(maxRevenue, bestIndex)` ### Constraints (typical) - `1 <= n <= 2e5` - `1 <= k <= 1e18` - `1 <= time[i] <= 1e18` - `0 <= profit[i] <= 1e18` ### Notes The chosen query type can be run `floor(k / time[i])` times.

Quick Answer: This question evaluates optimization and numerical reasoning skills, specifically selecting a single repetitive action to maximize aggregate revenue under a tight time budget while handling integer division, large numeric bounds, and deterministic tie-breaking.

You are given a virtual warehouse that can execute queries. There are n query types, and you must choose exactly one query type to run repeatedly for at most k minutes. For query type i, each run takes time[i] minutes and yields profit[i] revenue. You may run the chosen query type any number of times back-to-back as long as the total time does not exceed k. Return the maximum total revenue achievable and the 0-based index of the query type that achieves it. If multiple query types produce the same maximum revenue, return the smallest such index.

Constraints

1 <= n <= 2 * 10^5
1 <= k <= 10^18
time.length == profit.length == n
1 <= time[i] <= 10^18
0 <= profit[i] <= 10^18
The chosen query type i can be run floor(k / time[i]) times

Examples

Input: (10, [3, 4, 6], [5, 7, 14])

Expected Output: (15, 0)

Explanation: Query type 0 can run floor(10/3)=3 times for revenue 15. Types 1 and 2 each produce revenue 14, so the maximum is 15 at index 0.

Input: (10, [2, 5, 4], [4, 10, 8])

Expected Output: (20, 0)

Explanation: Type 0 produces 5*4=20 revenue, type 1 produces 2*10=20 revenue, and type 2 produces 2*8=16 revenue. The maximum revenue is tied between indices 0 and 1, so return the smaller index 0.

Input: (5, [6, 7, 8], [100, 200, 300])

Expected Output: (0, 0)

Explanation: No query type can run even once because every time[i] is greater than k. All revenues are 0, so return the smallest index 0.

Input: (20, [5, 4, 10], [0, 0, 1])

Expected Output: (2, 2)

Explanation: Types 0 and 1 have zero profit, so they produce 0 revenue. Type 2 can run twice and produces total revenue 2.

Input: (100, [9], [10])

Expected Output: (110, 0)

Explanation: There is only one query type. It can run floor(100/9)=11 times for total revenue 110.

Input: (1000000000000000000, [1, 2], [1000000000000000000, 1000000000000000000])

Expected Output: (1000000000000000000000000000000000000, 0)

Explanation: Type 0 can run 10^18 times with profit 10^18 each, producing 10^36 revenue. Type 1 runs 5*10^17 times and produces less revenue.

Hints

For a fixed query type i, compute how many times it can run within k minutes.
Scan all query types in index order and only update the answer when you find a strictly larger revenue.

Quick Overview