Amazon SDE-1 OA (Aug 2) Question & Answer

Question 1

In an Amazon maintenance center, there exist $ n $ machines, each equipped with $ m (m \geq 2) $ power units. The power of the $ j $-th power unit in the $ i $-th machine is denoted as $ machine\_powers[i][j] $. The strength of a machine is defined as the minimum power among all its power units. We want to maximize the sum of strengths of all the machines. For this, we can perform the following 3-step operation multiple times (possibly 0):

• Select a machine that has not yet been marked.
• Transfer any one power unit from the selected machine to any other machine.
• Mark the selected machine and it cannot be chosen for further operations. However, marked machines can still receive power units from other machines.

Each machine can transfer at most one power unit during the entire process, only when it is unmarked. A machine can receive power units from multiple other machines, even after it has been marked. The operation can be performed multiple times, but only unmarked machines can be selected during each operation. Find the maximum sum of strengths of all machines.

Sample Test Case

- **Input**: - \( n = 2 \), \( m = 3 \) - \( power = [[2, 7, 4], [2, 4, 3]] \) - **Output**: \( 6 \) - **Explanation**: Move the power unit with power 2 from the first machine to the second machine. Then the strength = \( \min(7, 4) + \min(2, 4, 3, 2) = 4 + 2 = 6 \). So, the answer is 6.

Approach

For each machine $ i $, find $ a_i $ (smallest power) and $ b_i $ (second smallest). The optimal strategy is to transfer $ a_i $ from all machines except one receiver $ r $ to $ r $, making strengths $ b_i $ for $ i \neq r $ and $ \min(a_0, ..., a_{n-1}) $ for $ r $. Maximize the sum by:

Computing $ \text{sum_b} = \sum b_i $, $ \text{min_b} = \min b_i $, and $ \text{min_a} = \min a_i $. Returning $ \text{sum_b} - \text{min_b} + \text{min_a} $. Time complexity is $ O(n \cdot m) $, space complexity is $ O(1) $, fitting $ m \cdot n \leq 2 \times 10^5 $.

Code

```

<h3>Question 2</h3>
Statement:
Amazon has multiple delivery centers all over the world. A city is given in the form of a grid where the delivery centers are marked as 1 and all other places are marked as 0.
Distance between two cell is defined as the maximum absolute distance between x-coordinates and y-coordinates.
For example, distance between (1, 2) and (0, 4) is max(|1-0|, |2-4|) = 2.
The incovenience of the grid is defined as the maximum distance of any place marked 0 from its nearest delivery center.

Amazon is planning to open a new delivery center to reduce the incovenience of the grid. Minimize the inconvenience of the grid by converting at most one 0(any place) to 1(a delivery center) and report this minimum value.

Input

0 0 0 1
0 0 0 1

Distances to nearest delivery centeres
3 2 1 0
3 2 1 0
Initial incovenience is 3

Converting the (0, 0) to a delivery center
1 0 0 1
0 0 0 1

Now the inconvenience is 1 with distance as
0 1 1 0
1 1 1 0

Constraints
n, m <= 500

<h3>Approach</h3>
The problem involves finding the minimum inconvenience in a delivery grid, where inconvenience is defined as the maximum Chebyshev distance (maximum of absolute differences in x and y coordinates) from any cell to the nearest delivery center. The grid contains cells with values:

$ 1 $: Existing delivery centers.
$ 0 $: Potential locations for a new delivery center.

The goal is to determine the minimum inconvenience, considering the option to place one additional delivery center at any $ 0 $ cell to reduce the maximum distance.
Steps:

Initialization and BFS for Existing Centers:

Create a distance matrix $ dist[R][C] $ initialized with $ -1 $ (unvisited).
Identify all cells with $ grid[i][j] = 1 $ as starting points and set their distance to $ 0 $.
Use BFS with 8-directional movement (Chebyshev distance considers all 8 neighbors) to compute the shortest distance from each cell to the nearest existing delivery center.
If no delivery centers exist ($ q.isEmpty() $), compute the maximum Chebyshev distance from a potential new center at every cell to all other cells, and return the minimum of these.


Compute Initial Inconvenience:

After BFS, the initial inconvenience is the maximum value in $ dist $, representing the largest distance to the nearest existing center.


Evaluate New Delivery Center Placement:

Iterate over all cells where $ grid[i][j] = 0 $.
For each potential new center, calculate the new maximum distance by taking the minimum of the existing distance $ dist[x][y] $ and the Chebyshev distance to the new center for every cell $ (x, y) $.
Update the minimum inconvenience if the new maximum distance is smaller.


Return Result:

The minimum inconvenience is the smallest value found, either from the initial setup or after placing a new center.

<h3>Code</h3>