FastPrep
Problem · Greedy

Minimize Total Time

● HardGoogleONSITE INTERVIEW
See Google hiring insights

You are given two integer arrays:

  • int[] multiples: the multipliers available in the shop
  • int[] prices: the corresponding prices for each multiplier

    • Both arrays have the same length n, and the i-th multiplier (multiples[i]) costs prices[i] coins to purchase.

    You start with:

  • 0 coins
  • A base gain rate of 1 coin per second

    • When you purchase a multiplier, your coin gain rate is multiplied by that value. For example:

  • Start: gain = 1x
  • Buy 3x -> gain becomes 3x
  • Buy 4x -> gain becomes 3 × 4 = 12x

    • You can only make purchases when you have enough coins to afford the multiplier.

    Your goal is to purchase all the multipliers, in some order, such that the total time taken to finish all purchases is minimized.

    Function Description

    Complete the function minimizeTotalTime in the editor.

    minimizeTotalTime has the following parameters:

    1. int[] multiples: an array of multipliers available in the shop
    2. int[] prices: an array of corresponding prices for each multiplier

    Returns

    int[]: an array of indices representing the order in which to purchase the multipliers to minimize the total time

    Examples
    01 · Example 1
    multiples = [3, 100, 30]
prices = [5, 30, 15]
return = [0, 2, 1]
    [0, 2, 1] Buy 3x, then 30x, then 100x
    Constraints
    :O
    More Google problems
    drafts saved locally
    public int[] minimizeTotalTime(int[] multiples, int[] prices) {
  // write your code here
}
    multiples[3, 100, 30]
    prices[5, 30, 15]
    expected[0, 2, 1]
    sign in to submit