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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

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

Compute total revenue from greedy VM rentals

Quick Overview

This question evaluates understanding of greedy allocation strategies and the ability to maintain dynamic summaries (tracking current maximum and smallest positive inventories) under sequential state updates, reflecting algorithmic thinking and data-structure manipulation.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You manage **n** VM types. VM type *i* starts with inventory `a[i]` (number of available instances). There are **m** customers arriving one by one. For each customer: 1. The customer rents **one** instance from the VM type that currently has the **largest** inventory (if there are ties, any tied type may be chosen). 2. Let `maxInv` be that largest inventory *before* the rental. 3. Let `minPosInv` be the **smallest positive** inventory among all VM types *before* the rental (ignore VM types with inventory 0). 4. The revenue from this rental is `maxInv + minPosInv`. 5. After the rental, the chosen VM type’s inventory decreases by 1. Assume it is guaranteed that the total initial inventory is at least `m`. **Task:** Compute the total revenue after processing all `m` customers. #### Input - Integers `n`, `m` - Array `a[1..n]` of non-negative integers #### Output - A single integer: the total revenue. #### Notes - If multiple VM types share the same maximum inventory, any choice among them leads to a valid simulation. - `minPosInv` is always defined because total remaining inventory is positive while customers remain. #### Example If `a = [2, 1]`, `m = 2`: - Step 1: `maxInv=2`, `minPosInv=1`, revenue `3`, inventories -> `[1,1]` - Step 2: `maxInv=1`, `minPosInv=1`, revenue `2`, inventories -> `[0,1]` Total revenue = `5`.

Quick Answer: This question evaluates understanding of greedy allocation strategies and the ability to maintain dynamic summaries (tracking current maximum and smallest positive inventories) under sequential state updates, reflecting algorithmic thinking and data-structure manipulation.

Part 1: Compute Total Revenue from Greedy VM Rentals

You are given the current stock of n VM types and an integer m. Customers arrive one by one. For each customer, choose a VM type with the largest positive stock. Let max_stock be that chosen stock before the rental, and let min_stock be the smallest positive stock among all VM types before the rental. The revenue from this rental is max_stock + min_stock. Then decrease the chosen stock by 1. If all stocks are 0 before some request, stop early and ignore the remaining customers. Return the total revenue after processing at most m requests.

Constraints

1 <= len(stocks) <= 2 * 10^5
0 <= stocks[i] <= 10^9
0 <= m <= 2 * 10^5
The answer may exceed 32-bit integer range.

Examples

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

Expected Output:

Explanation: The revenues are 5, 4, 3, and 3, for a total of 15.

Input: ([3, 3], 3)

Expected Output:

Explanation: The revenues are 6, 5, and 4.

Input: ([0, 0, 0], 5)

Expected Output:

Explanation: No VM is available for the first customer, so the process stops immediately.

Input: ([1], 3)

Expected Output:

Explanation: Only one rental is possible. Its revenue is 1 + 1 = 2.

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

Expected Output:

Explanation: Zero-stock types are ignored when computing the minimum positive stock. The two revenues are 2 and 2.

Hints

You need to repeatedly know both the current maximum stock and the current minimum positive stock.
A max-heap and a min-heap with lazy deletion let you update one chosen stock in O(log n) per customer.

Part 2: Maximum Equal-Frequency Blocks for Every Prefix

Given a string s consisting of uppercase English letters, compute an array ans where ans[i - 1] is the maximum number of contiguous blocks into which the prefix s[:i] can be split such that: (1) all blocks have the same length, and (2) every block has exactly the same character frequencies. The blocks do not need to be identical strings; they only need to be anagrams of one another. For example, the prefix 'ABBA' can be split into 'AB' and 'BA', so its value is 2.

Constraints

0 <= len(s) <= 3000
s contains only characters 'A' to 'Z'

Examples

Input: "ABBA"

Expected Output:

Explanation: Only the full prefix 'ABBA' can be split into 2 valid blocks: 'AB' and 'BA'.

Input: "AABB"

Expected Output:

Explanation: The prefix 'AA' can be split into 'A' and 'A', but 'AABB' cannot be split into 2 valid blocks because 'AA' and 'BB' have different frequencies.

Input: "AAAA"

Expected Output:

Explanation: Every prefix of length i can be split into i single-character blocks, all with the same frequencies.

Input: ""

Expected Output:

Explanation: There are no prefixes in an empty string.

Input: "ABABAB"

Expected Output:

Explanation: The full prefix can be split into 3 blocks: 'AB', 'AB', 'AB'.

Hints

If a prefix is split into k valid blocks, then the total count of every character in that prefix must be divisible by k. So k must divide the gcd of the character counts.
Compare blocks by their frequency signature, not by the raw substring. A prefix-frequency hash can make each block comparison O(1).

Quick Overview