Amazon OA SDE 2 DSA Solution discussion
Summary
I discussed the solution to a 2‑D grid minimization problem that appeared in an Amazon SDE 2 online assessment.
Full Experience
I will be discussing the below problem:
The Intuition 1:
BFS, since the 2d array with equal cost and 8d movement {up,left,right,down,up-left,up-right,down-left,down-right} and bfs computes shortest path with ease in this setup.
The Intuition 2: Binary Search, since the problem asks us to minimize and if inconvenience incv is possible then any value greater than incv is eliminated.
Solution: The problem boils down to simple finding out possibility of achieving the minimum inconvenience.
Apply binary search on the inconvenience range 0 to max(n,m).
For any possible inconvenience incv, color all the achievable blocks to 1 using BFS from all the already colored nodes.
For all the uncolored blocks i.e blocks with value 0. For any (x,y) the extra source must lie inside (row,col):
x-incv <= row <= x+incv
y-incv <= col <= y+incv
If there exist an non empty intersection of (row,col) for all the uncolored blocks then the incv is possible and hence all the greater can be rejected.
If you like pattern based DSA breakdowns like this, I share more FAANG interview preparation notes on www.faangplus.com
Interview Questions (1)
Minimize Inconvenience in a 2D Grid
Given a 2‑D grid where each cell can be either blocked or unblocked, you can move in 8 directions (up, down, left, right, and the four diagonals) with equal cost. The task is to find the minimum possible inconvenience value such that by placing an extra source cell, all unblocked cells become reachable. Inconvenience is defined as the maximum Manhattan distance from the extra source to any uncolored (value 0) cell. Determine the smallest inconvenience that makes the whole grid reachable.
Approach: Use binary search on the inconvenience value from 0 to max(n,m). For each candidate value, perform BFS from all already colored cells to mark reachable cells. Then check if there exists a position for the extra source whose Manhattan distance to every uncolored cell is ≤ the candidate inconvenience. If such a position exists, the candidate is feasible.