Panda Guru LogoPanda
Guru

Amazon Software Development Engineer Full-Time Online Assessment

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:

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.