Katkat
Back

Maximize Revenue from Depleting VM Stock

IBMSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Tests greedy optimization, sorting, and arithmetic progression math to compute maximum revenue from diminishing-value stock with large order quantities.

Problem Statement

A cloud computing service has several data centers, each holding a certain number of virtual machines (VMs) ready to be provisioned. The inventory is represented as an array of positive integers, inventory, where inventory[i] is the number of VMs available of type i.

Due to dynamic demand pricing, whenever you provision a VM of type i, the revenue generated equals the current remaining number of VMs of that type, after which inventory[i] decreases by 1.

You are tasked with fulfilling exactly orders VM requests. Find the maximum total revenue you can achieve by choosing which VMs to provision. Because the answer can be very large, return it modulo 10^9 + 7.

Function Signature

def max_vm_revenue(inventory: list[int], orders: int) -> int:
    pass

Input and Output Format

  • Input:
    • inventory: A list of integers representing the initial count of each VM type.
    • orders: An integer representing the total number of VMs to sell.
  • Output:
    • An integer representing the maximum revenue modulo 10^9 + 7.

Constraints

  • 1 <= len(inventory) <= 10^5
  • 1 <= inventory[i] <= 10^9
  • 1 <= orders <= min(sum(inventory), 10^9)

Examples

Example 1

Input: inventory = [2, 5], orders = 4
Output: 14
Explanation:
- 1st order: Pick from type with 5 VMs. Revenue = 5, inventory becomes [2, 4].
- 2nd order: Pick from type with 4 VMs. Revenue = 4, inventory becomes [2, 3].
- 3rd order: Pick from type with 3 VMs. Revenue = 3, inventory becomes [2, 2].
- 4th order: Pick from either type with 2 VMs. Revenue = 2, inventory becomes [1, 2] or [2, 1].
Total revenue = 5 + 4 + 3 + 2 = 14.

Example 2

Input: inventory = [3, 5], orders = 6
Output: 19
Explanation:
Provisioned values: 5, 4, 3, 3, 2, 2.
Total revenue = 5 + 4 + 3 + 3 + 2 + 2 = 19.

Edge Cases

  • All VM counts in inventory are equal.
  • orders is equal to sum(inventory), requiring selling out the entire stock.
  • Large values where naive decrements or priority queue simulations lead to Time Limit Exceeded (TLE).

Hints

Hint 1

To maximize revenue, you should always provision from whichever VM type currently has the highest remaining count.

Hint 2

Since orders and counts can reach 10^9, simulating one order at a time using a max-heap is too slow; group reductions across all tied maximum elements together.

Hint 3

Sort the inventory descending or use binary search to identify the cutoff value down to which items are sold, then use arithmetic progression sum formulas to accumulate revenue in bulk.

Follow-up questions

  • How does the binary search approach compare in time and space complexity to sorting the inventory array directly?
  • How would you modify your solution if each VM type had a minimum reserve count that could never be sold?
  • What changes would be required if each type had an individual decrement step k_i instead of decreasing by 1 with each sale?