Amazon intern OA 26 code
- Posted
- 31 Jan 2026
Summary
I completed an Online Assessment for an Amazon intern position, which involved solving two distinct coding challenges.
How it went
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.
Questions asked (2)
- 01
Maximize Revenue from Virtual Machine Rentals
Data Structures & Algorithms
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.
- 02
String Prefix Equal Block Division
Data Structures & Algorithms
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'.