Katkat
Back

Construct connected crop layout and safe paths

GoogleMachine Learning Engineer · Technical Screen
HardMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a constructive grid layout that satisfies connectivity and size constraints, followed by pathfinding through dynamic or constrained environments.

Problem Statement

You are designing a vertical farming layout on a 2D grid of size N x N. The grid contains K distinct crop types, each requiring a specific number of cells S_i. You must partition the grid into K connected regions such that:

  1. Each region i has exactly S_i cells.
  2. All regions are connected (orthogonally).
  3. Every cell (r, c) must belong to exactly one region.

After designing the layout, define a 'safe path' between two points A and B as the shortest Manhattan path where no cell in the path contains a crop type that is 'vulnerable'. A crop type i is vulnerable if its region is adjacent to a boundary of the grid.

Implement the function design_and_navigate(N, crop_requirements, start, end):

Input

  • N: Integer, grid dimension.
  • crop_requirements: A list of integers [S_1, S_2, ..., S_K] where sum(S_i) == N * N.
  • start, end: Tuples (r, c) representing coordinates.

Output

  • Return a 2D list (grid) representing the layout (use integers 1 to K for labels).
  • Return the length of the shortest safe path between start and end, or -1 if no such path exists.

Examples

N = 3, crops = [4, 5]
# A valid layout fills the grid such that regions are connected.
# The pathfinding ignores any cell belonging to a region type touching the edge.

Constraints

  • N <= 50.
  • K <= 10.
  • Time complexity should be efficient enough to handle backtracking or grid-filling heuristics.

Hints

Hint 1

Use a backtracking approach with pruning to fill the grid, prioritizing connectivity by checking the adjacency of newly added cells to the existing cluster.

Hint 2

For the pathfinding, first identify which crop regions touch the grid boundary to mark all cells in those regions as 'unsafe'.

Hint 3

Once the safe grid is determined, use Breadth-First Search (BFS) to find the shortest Manhattan distance path avoiding unsafe cells.

Follow-up questions

  • How would your approach change if the regions were required to be convex?
  • If the grid size N increased to 10^6, how would you reformulate the layout problem to avoid explicit grid construction?
  • What if the 'vulnerability' was dynamic and changed based on the total number of neighbors of the same crop type?