Round 1
Questions:
Question 1
AWS provides scalable systems. A set of n servers are used for horizontally scaling an application. The goal is to have the computational power of the servers in non-decreasing order. To do so, you can increase the computational power of each server in any contiguous segment by x.
Choose the values of x such that after the computational powers are in non-decreasing order, the sum of the x values is minimum.
Example
There are n = 5 servers and their computational power = [3, 4, 1, 6, 2].
Add 3 units to the subarray (2, 4) and 4 units to the subarray (4, 4). The final arrangement of the servers is: [3, 4, 4, 9, 9]. The answer is 3 + 4 = 7.
Function Description
Complete the function makePowerNonDecreasing in the editor below.
makePowerNonDecreasing has the following parameter(s):
int power[n]: the computational powers of n different servers
Returns
int: the minimum possible sum of integers required to make the array non-decreasing
Constraints
• 1 ≤ n ≤ 10^5
• 1 ≤ power[i] ≤ 10^9
Question 2
Amazon uses small, Roomba-shaped robots, called "Drives". They deliver large stacks of products to human workers by following set paths around the warehouse.
The warehouse can be represented in the form of a cartesian plane, where robots are located at integral points of the form (x, y). When a product is to be delivered to some point (i, j), the nearest robot is sought and chosen. Thus if a robot is surrounded by other robots nearby, it will seldom be chosen for work. More formally, a robot is said to be idle if it has a robot located above, below, left, and right of it. It is guaranteed that no two robots are at the same location.
Given the locations of n robots, find the number of idle robots.
Function Description
Complete the function numidleDrives in the editor below.
numidleDrives has the following parameters:
int x[n]: x[i] is the x-coordinate of the ith robot, where 0 ≤ i < n.
int y[n]: y[i] is the y-coordinate of the ith robot, where 0 ≤ si ≤ n.
Returns
int: the number of idle robots
Constraints
• 1 ≤ n ≤ 10^5
• -10^9 ≤ [xi], [yi] ≤ 10^9
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.