How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Google during technical interviews.

Construct connected crop layout and safe paths

Q: Construct connected crop layout and safe paths

This question evaluates constructive grid design and graph-based pathfinding skills, specifically the ability to produce connected labeled regions that meet size constraints and to reason about shortest paths and path-safety metrics based on Manhattan distance.

Problem A — Construct a garden with connected crop regions

You are given an N × M rectangular grid (a garden) that must be fully planted using k crop types labeled a, b, ..., k.

You are also given required counts for each crop: counts = [c1, c2, ..., ck] such that:

c1 + c2 + ... + ck = N * M

Task

Construct and output any N × M grid assignment of crop labels such that:

Every cell is assigned exactly one crop.
Crop i appears exactly ci times.
For each crop type, all its cells form one connected component under 4-directional adjacency (up/down/left/right).

If it is impossible, output that it cannot be done.

Follow-up (non-rectangular garden)

Now the garden is the union of two squares:

One square of size N × N
One square of size M × M

They are stacked vertically with their left edges aligned, and they do not overlap. (So the overall shape may be non-rectangular if N ≠ M.)

You are given k crops with counts summing to N^2 + M^2.

Construct and output a planting for this shape such that each crop’s cells are 4-connected within the shape.

Problem B — Grid shortest path and maximize distance from a cat

You are given an N × N grid where:

0 = land (walkable)
1 = water (blocked)

You are also given two land cells:

S = start
T = target

Movement is allowed only on land cells and only in 4 directions.

Task 1

Find the shortest path from S to T (or the shortest path length). If no path exists, report failure.

Follow-up (maximize minimum Manhattan distance to a cat)

In addition, one cell contains a cat at position C (not necessarily on the path).

For any path P from S to T (moving only on land), define the path’s “safety” as:

$\text{safety}(P) = \min_{v \in P} \; \text{ManhattanDistance}(v, C)$

where Manhattan distance is |r1 - r2| + |c1 - c2|.

Find a path from S to T that maximizes this safety value (i.e., maximizes the minimum Manhattan distance to the cat among all cells on the path). If no path exists, report failure.

(You may return either the maximum achievable safety value, or the corresponding path.)

Problem A — Construct a garden with connected crop regions

You are given an N × M rectangular grid (a garden) that must be fully planted using k crop types labeled a, b, ..., k.

You are also given required counts for each crop: counts = [c1, c2, ..., ck] such that:

c1 + c2 + ... + ck = N * M

Task

Construct and output any N × M grid assignment of crop labels such that:

Every cell is assigned exactly one crop.
Crop i appears exactly ci times.
For each crop type, all its cells form one connected component under 4-directional adjacency (up/down/left/right).

If it is impossible, output that it cannot be done.

Follow-up (non-rectangular garden)

Now the garden is the union of two squares:

One square of size N × N
One square of size M × M

They are stacked vertically with their left edges aligned, and they do not overlap. (So the overall shape may be non-rectangular if N ≠ M.)

You are given k crops with counts summing to N^2 + M^2.

Construct and output a planting for this shape such that each crop’s cells are 4-connected within the shape.

Problem B — Grid shortest path and maximize distance from a cat

You are given an N × N grid where:

0 = land (walkable)
1 = water (blocked)

You are also given two land cells:

S = start
T = target

Movement is allowed only on land cells and only in 4 directions.

Task 1

Find the shortest path from S to T (or the shortest path length). If no path exists, report failure.

Follow-up (maximize minimum Manhattan distance to a cat)

In addition, one cell contains a cat at position C (not necessarily on the path).

For any path P from S to T (moving only on land), define the path’s “safety” as:

$\text{safety}(P) = \min_{v \in P} \; \text{ManhattanDistance}(v, C)$

where Manhattan distance is |r1 - r2| + |c1 - c2|.

Find a path from S to T that maximizes this safety value (i.e., maximizes the minimum Manhattan distance to the cat among all cells on the path). If no path exists, report failure.

(You may return either the maximum achievable safety value, or the corresponding path.)

Construct connected crop layout and safe paths

Quick Overview

Problem A — Construct a garden with connected crop regions

Task

Follow-up (non-rectangular garden)

Problem B — Grid shortest path and maximize distance from a cat

Task 1

Follow-up (maximize minimum Manhattan distance to a cat)

Comments (0)

Construct connected crop layout and safe paths

Quick Overview

Problem A — Construct a garden with connected crop regions

Task

Follow-up (non-rectangular garden)

Problem B — Grid shortest path and maximize distance from a cat

Task 1

Follow-up (maximize minimum Manhattan distance to a cat)

Comments (0)