Amazon intern OA 26 code

T1: Problem statement: There are n types of virtual machines with given initial inventories. m customers rent machines one by one, and each time the customer rents the type with the largest current inventory. The revenue from each rental is determined by the current inventory value. After a rental, the selected inventory is decreased by 1. Compute the total revenue after processing all m requests.

Approach: Use a max-heap (priority queue) to maintain the inventories so that the maximum value can be retrieved in O(log n) time. Meanwhile, maintain a variable to track the global minimum non-zero inventory. At each step, extract the maximum value max from the heap and add max + min to the total revenue. If max == min, it means all inventories in the heap are equal; after decreasing by 1, the minimum value will also become max − 1. Repeat this process m times.

T2: Problem statement: Given a string, for each prefix, compute the maximum number of equal blocks it can be divided into. The blocks must all have the same length, and for each character, its frequency must be identical across all blocks. For example, the prefix "ABBA" (length 4) can be split into "AB" and "BA", since both blocks contain exactly one 'A' and one 'B'.

Approach: Precompute prefix character frequency counts and hash values. For each prefix of length i, compute the greatest common divisor (G) of the total counts of all characters. The number of blocks k must be a divisor of G. Enumerate the divisors of G from largest to smallest, and for each candidate k, use the hash values to verify in O(1) time whether all blocks have identical character frequencies. The first valid k found is the answer for that prefix.