Round 1
Questions:
Problem 1: Minimum Starting Health to Win the Game
In Amazon Prime Games, a player needs to pass n rounds sequentially. The rules are as follows:
- The player loses power[i] health to complete round i.
- The player's health must always be greater than 0 at all times.
- The player can use armor in only one round, which prevents damage of min(armor, power[i]) for that round.
- You need to determine the minimum starting health required for the player to win the game.
Example 1: Input:
power = [1, 2, 6, 7] armor = 5
Output:
12
Explanation:
Starting health = 12
Round 1: Health = 12 - 1 = 11
Round 2: Health = 11 - 2 = 9
Round 3: Health = 9 - (6 - 5) = 8
Round 4: Health = 8 - 7 = 1
The minimum starting health required to win the game is 12.
Example 2: Input:
power = [1, 2, 3] armor = 1
Output:
6
Explanation:
Starting health = 6
Round 1: Health = 6 - 1 + 1 (armor) = 6
Round 2: Health = 6 - 2 = 4
Round 3: Health = 4 - 3 = 1
The minimum starting health required to win the game is 6.
class Result { public static long getMinimumValue(List<Integer> power, int armor) { // Write your code here } }
Input Format:
The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of rounds.
The next n lines contain integers power[i] (1 ≤ power[i] ≤ 10^9) — the health cost to complete each round.
The last line contains an integer armor (1 ≤ armor ≤ 10^9) — the maximum amount of health that may be returned by armor.
Output Format:
Return a single integer — the minimum starting health required to win the game.
Candidate's Approach
The approach involves calculating the health required for each round while considering the use of armor optimally. The algorithm iterates through the rounds, adjusting the health based on the damage taken and the armor used in the most beneficial round.
Interviewer's Feedback
The candidate successfully completed the first question with all test cases passing.
Problem 2: Sum of System Vulnerability over All Subsegments
An application at Amazon is deployed on n servers connected linearly. The vulnerability of the ith server is given by vulnerability[i]. The system vulnerability of a contiguous segment of servers, i.e., a subsegment, is defined as the product of the number of servers and the maximum vulnerability of the servers in that segment.
Given the array vulnerability, find the sum of system vulnerabilities over all the subsegments of servers. Since the answer can be large, report it modulo 10^9 + 7.
Example 1: Input:
vulnerability = [4, 2, 1, 2]
Output:
59
Explanation: For each subsegment, calculate the number of servers, maximum vulnerability, and system vulnerability:
Subsegment Number of servers Maximum Vulnerability System Vulnerability [4] 1 4 1 * 4 = 4 [4, 2] 2 4 2 * 4 = 8 [4, 2, 1] 3 4 3 * 4 = 12 [4, 2, 1, 2] 4 4 4 * 4 = 16 [2] 1 2 1 * 2 = 2 [2, 1] 2 2 2 * 2 = 4 [2, 1, 2] 3 2 3 * 2 = 6 [1] 1 1 1 * 1 = 1 [1, 2] 2 2 2 * 2 = 4 [2] 1 2 1 * 2 = 2 Sum of system vulnerabilities = 4 + 8 + 12 + 16 + 2 + 4 + 6 + 1 + 4 + 2 = 59
Example 2: Input:
vulnerability = [4, 4]
Output:
16
Explanation: For each subsegment, calculate the number of servers, maximum vulnerability, and system vulnerability:
Subsegment Number of servers Maximum Vulnerability System Vulnerability [4] 1 4 1 * 4 = 4 [4, 4] 2 4 2 * 4 = 8 [4] 1 4 1 * 4 = 4 Sum of system vulnerabilities = 4 + 8 + 4 = 16
class Result { public static int getSystemVulnerabilitySum(List<Integer> vulnerability) { // Write your code here } }
Input Format:
The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of servers.
The next n lines contain integers vulnerability[i] (1 ≤ vulnerability[i] ≤ 10^5) — the vulnerability of each server.
Output Format:
Return a single integer — the sum of system vulnerabilities modulo 10^9 + 7.
Candidate's Approach
The candidate attempted to calculate the sum of system vulnerabilities by iterating through all possible subsegments, but faced challenges with performance, resulting in only 1 out of 15 test cases passing.
Interviewer's Feedback
The candidate only passed 1 out of 15 test cases for the second question. They need to optimize their approach to handle larger inputs effectively.