Katkat
Back

Maximize Revenue from Depleting VM Inventory

IBMSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to efficiently manage and update a dynamic collection of items using a priority queue to always extract the maximum value.

Problem Statement

You are managing a cloud provider's inventory of Virtual Machines (VMs). You have an array inventory where each element represents the number of VMs available of a specific type. When you rent out one VM of a particular type, you earn a profit equal to the current number of available VMs of that type, and the stock of that type decreases by 1.

Given an array inventory and an integer orders representing the total number of VMs you must rent out, return the maximum profit you can achieve.

Function Signature

def maxProfit(inventory: List[int], orders: int) -> int:

Constraints

  • 1 <= inventory.length <= 10^5
  • 1 <= inventory[i] <= 10^9
  • 1 <= orders <= sum(inventory)

Examples

Example 1: Input: inventory = [2, 5], orders = 4 Output: 14 Explanation:

  • Rent from type 1 (5 VMs left): profit 5, inventory becomes [2, 4]
  • Rent from type 1 (4 VMs left): profit 4, inventory becomes [2, 3]
  • Rent from type 1 (3 VMs left): profit 3, inventory becomes [2, 2]
  • Rent from type 2 (2 VMs left): profit 2, inventory becomes [1, 2] Total profit: 5 + 4 + 3 + 2 = 14.

Example 2: Input: inventory = [3, 5], orders = 6 Output: 21

Edge Cases

  • orders equals the total sum of inventory.
  • inventory contains a single element.
  • Large values of inventory[i] require avoiding simulation-based approaches.

Hints

Hint 1

A direct simulation using a max-heap is inefficient given the constraints on inventory size; consider if you can process multiple units of the same type at once.

Hint 2

Since the profit is strictly decreasing as you rent more VMs, the problem can be viewed as choosing a threshold value T such that all VM types with stock > T are reduced to T.

Hint 3

Binary search on the minimum threshold value T allows you to find the exact number of VMs to rent in O(N log(max(inventory))) time.

Follow-up questions

  • How would your approach change if the profit for a VM was not the current stock count, but a fixed price per type?
  • What is the time complexity of your solution, and can you explain why binary search is preferred over a greedy simulation?
  • If the order requirement is extremely large, how do you handle potential integer overflows in your profit calculation?