Maximize revenue by choosing one query type
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.