Solve matrix groups and recipe inventory

Q: Solve matrix groups and recipe inventory

This pair of problems evaluates block-wise grid processing and aggregation for minimum-value selection alongside dependency-resolution and resource-allocation reasoning for recipe inventory planning, testing competencies in array manipulation, tie-breaking and constraint handling, graph-based dependency management and cycle detection, and algorithmic complexity analysis; they are commonly asked to gauge an applicant's ability to implement correct, efficient solutions under input-size and edge-case constraints. They belong to the Coding & Algorithms domain with subdomains in data structures (arrays/grids), algorithm design and analysis, and graph theory, and primarily require practical application of algorithmic techniques with attention to time/space complexity rather than purely theoretical proofs.

Q: 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.

Question

Loading...

Problem 1: Find the smallest 3×3 group in a matrix

You are given an m × n 2D integer array grid.

Partition the grid into non-overlapping 3×3 blocks , aligned from the top-left corner.
- A block’s top-left corner is at (r, c) where r and c are multiples of 3.
- Consider only full 3×3 blocks (ignore leftover rows/columns if m or n is not a multiple of 3).
For each 3×3 block, compute its representative value = the minimum value in that block.

Task: Return the block whose representative value is the smallest among all blocks. Specify what you return, e.g.:

the smallest representative value, and
the top-left coordinate (r, c) of the corresponding 3×3 block (tie-breaking rule required).

Follow-up: A block is invalid if any cell equals 1. Ignore invalid blocks when selecting the minimum. If all blocks are invalid, return a sentinel value (e.g. null / (-1, -1, -1)).

Also discuss: time and space complexity.

Constraints (you may assume)

1 ≤ m, n ≤ 2000
grid[i][j] fits in 32-bit signed integer
Define a clear tie-breaker if multiple blocks share the same representative (e.g., smallest row, then smallest column).

Problem 2: Check if inventory can produce a desired recipe

You are given:

A set of recipes describing how to produce items.
- Each recipe defines: product -> [(ingredient1, qty1), (ingredient2, qty2), ...] .
- Ingredients may be raw materials or other products that also have recipes.
- Assume producing 1 unit of product consumes the listed quantities.
An inventory mapping item -> available_quantity for raw materials (and possibly some pre-made products).
A target : (target_item, target_quantity) .

Task: Determine whether it is possible to produce target_quantity units of target_item using the inventory and recipes.

Requirements / clarifications to address

You must define reasonable data structures for recipes and inventory.
Handle nested dependencies (e.g., cake needs sugar , and sugar needs cane ).
If there is a dependency cycle (directly or indirectly), treat production as impossible unless you explicitly justify another rule.
State expected time/space complexity in terms of number of items and total ingredient edges.

Example scenario (illustrative)

cake -> (sugar, 2), (flour, 3), (egg, 1)
sugar -> (cane, 5)
Inventory: cane=100, flour=10, egg=3
Query: can we make 2 cakes?