Software Engineer · Phone Screen · Coding

Amazon — Software Engineer ✅ Passed

Level: Intern

Round: Phone Screen · Type: Coding · Difficulty: 7/10 · Duration: 60 min · Interviewer: Unfriendly

Topics: Data Structures, Algorithms, Hash Table

Location: Remote

Interview date: 2026-01-31

Summary

Round 1: Coding

Question: I had two coding questions in my phone screen. The first involved optimizing resource allocation among virtual machines, and the second involved partitioning a string prefix into equal blocks with consistent character frequencies.

Details

The coding questions I encountered were:

1. Virtual Machine Allocation:

   There are n types of virtual machines with given initial inventory counts. m customers request to rent machines. Each customer rents from the type with the highest current inventory. The revenue from each rental equals the minimum inventory count across all types. After a rental, the selected inventory is reduced by 1. The task is to calculate the total revenue after processing all m requests.

   • Approach: I used a max-heap (priority queue) to maintain the inventory counts, allowing for O(log n) retrieval of the maximum value. I maintained a variable to track the global non-zero minimum value. In each iteration, I extracted the max from the heap, added max + min to the total revenue. If max == min, it implies all inventories in the heap are equal, so after decrementing, the new minimum value becomes max – 1. This process was repeated m times.

2. Equal Partitioning of String Prefixes:

   Given a string, find the number of equal partitions for each prefix. Each partition must have the same length, and the frequency of each character must be identical across all partitions (e.g., ABBA can be divided into AB and BA because each contains 1 A and 1 B).

   • Approach: I precomputed prefix character counts and hash values. For each prefix length i, I calculated the greatest common divisor (GCD), G, of the total counts of each character. The number of blocks, k, must be a divisor of G. I iterated through the divisors of G in descending order, using hash values for O(1) verification of whether the character frequencies are equal across each block. The first k found is the answer.