How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium 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 Software Engineer candidates at Google during technical interviews.

Solve matrix groups and recipe inventory

Quick Overview

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.

Solve matrix groups and recipe inventory

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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: 1. 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. 2. An **inventory** mapping `item -> available_quantity` for raw materials (and possibly some pre-made products). 3. 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?

Quick Answer: 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.

Part 1: Smallest Valid 3x3 Block in a Matrix

You are given a 2D integer grid. Partition it into non-overlapping 3x3 blocks aligned from the top-left corner, so valid block top-left positions are (0,0), (0,3), (3,0), (3,3), and so on. Ignore leftover rows or columns that do not form a full 3x3 block. For each full 3x3 block, define its representative value as the minimum element inside that block. A block is invalid if any cell in that block equals 1. Among all valid full 3x3 blocks, return the one with the smallest representative value. Return a tuple (representative_value, row, col), where (row, col) is the top-left coordinate of the chosen block. If multiple valid blocks have the same representative value, break ties by smaller row, then smaller column. If there is no valid full 3x3 block, return (-1, -1, -1).

Constraints

1 <= number of rows, number of columns <= 2000
grid[i][j] fits in a 32-bit signed integer
Only full 3x3 blocks are considered
A block containing the value 1 is invalid and must be ignored

Examples

Input: ([[5,4,3,9,8,7],[6,2,8,5,4,6],[7,3,9,8,2,5],[10,11,12,0,3,4],[9,8,7,6,5,4],[3,2,9,7,8,9]],)

Expected Output: (0, 3, 3)

Explanation: There are four full 3x3 blocks. Their representative values are 2, 2, 2, and 0. The smallest is 0 at top-left coordinate (3, 3).

Input: ([[-1,5,6,-1,7,8],[9,10,11,12,13,14],[15,16,17,18,19,20],[21,22,23,24,25,26],[27,28,29,30,31,32],[33,34,35,36,37,38]],)

Expected Output: (-1, 0, 0)

Explanation: The top-left and top-right blocks both have representative value -1. Tie-breaking chooses the smaller row, then smaller column, so (0, 0) wins.

Input: ([[2,3,4,5,6,7],[8,1,9,4,5,6],[7,3,2,3,2,4],[9,8,7,6,1,4],[5,4,3,8,9,10],[11,12,13,14,15,16]],)

Expected Output: (2, 0, 3)

Explanation: Blocks at (0,0) and (3,3) are invalid because they contain 1. Among the remaining valid blocks, the smallest representative is 2 at (0, 3).

Input: ([[4,5,6,7],[8,9,10,11]],)

Expected Output: (-1, -1, -1)

Explanation: The grid does not contain any full 3x3 block.

Input: ([[2,3,4],[5,1,6],[7,8,9]],)

Expected Output: (-1, -1, -1)

Explanation: The only 3x3 block is invalid because it contains 1.

Hints

Scan only block starts at rows and columns that are multiples of 3.
While checking a 3x3 block, track both its minimum value and whether it contains a 1.

Part 2: Can Inventory Produce the Target Recipe?

You are given recipes, an inventory, and a production target. Each recipe has the form: product -> [(ingredient1, qty1), (ingredient2, qty2), ...] meaning that producing 1 unit of product consumes the listed ingredient quantities. Ingredients may themselves be products with recipes, creating nested dependencies. The inventory maps item names to available quantities. Inventory may contain both raw materials and already-made products. Task: determine whether it is possible to obtain target_quantity units of target_item. This problem uses the following explicit rule for cycles: if a dependency cycle is reachable from the target through the recipe graph, production is considered impossible and you must return False. This keeps the behavior deterministic. Return True if the target can be produced or already satisfied by inventory under that rule; otherwise return False.

Constraints

0 <= target_quantity <= 10^9
0 <= inventory[item] <= 10^9
Each recipe quantity is a positive integer
There is at most one recipe per product
Let V be the number of distinct items reachable from the target and E the number of ingredient references among them

Examples

Input: ({'cake': [('sugar', 2), ('flour', 3), ('egg', 1)], 'sugar': [('cane', 5)]}, {'cane': 100, 'flour': 10, 'egg': 3}, 'cake', 2)

Expected Output: True

Explanation: Two cakes need 4 sugar, 6 flour, and 2 eggs. The 4 sugar require 20 cane. Inventory has enough cane, flour, and eggs.

Input: ({'cake': [('sugar', 2), ('flour', 3), ('egg', 1)], 'sugar': [('cane', 5)]}, {'cane': 15, 'flour': 10, 'egg': 3}, 'cake', 2)

Expected Output: False

Explanation: Two cakes still need 20 cane through sugar production, but only 15 are available.

Input: ({'sandwich': [('bread', 2), ('cheese', 1)], 'bread': [('flour', 3)]}, {'bread': 1, 'flour': 3, 'cheese': 1}, 'sandwich', 1)

Expected Output: True

Explanation: One sandwich needs 2 bread and 1 cheese. Inventory already has 1 bread and 1 cheese, so only 1 more bread must be produced, which needs 3 flour.

Input: ({'C': [('A', 1)], 'A': [('B', 1)], 'B': [('A', 1)]}, {}, 'C', 1)

Expected Output: False

Explanation: A reachable dependency cycle A -> B -> A exists, so production is impossible under the stated rule.

Input: ({}, {}, 'anything', 0)

Expected Output: True

Explanation: Producing zero units is always possible.

Hints

First detect whether the target's reachable recipe graph contains a cycle.
If the graph is acyclic, process items from product to ingredients and accumulate total demand for each item.

Quick Overview

Solve matrix groups and recipe inventory

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Part 1: Smallest Valid 3x3 Block in a Matrix

Constraints

1 <= number of rows, number of columns <= 2000
grid[i][j] fits in a 32-bit signed integer
Only full 3x3 blocks are considered
A block containing the value 1 is invalid and must be ignored

Examples

Input: ([[5,4,3,9,8,7],[6,2,8,5,4,6],[7,3,9,8,2,5],[10,11,12,0,3,4],[9,8,7,6,5,4],[3,2,9,7,8,9]],)

Expected Output: (0, 3, 3)

Explanation: There are four full 3x3 blocks. Their representative values are 2, 2, 2, and 0. The smallest is 0 at top-left coordinate (3, 3).

Input: ([[-1,5,6,-1,7,8],[9,10,11,12,13,14],[15,16,17,18,19,20],[21,22,23,24,25,26],[27,28,29,30,31,32],[33,34,35,36,37,38]],)

Expected Output: (-1, 0, 0)

Explanation: The top-left and top-right blocks both have representative value -1. Tie-breaking chooses the smaller row, then smaller column, so (0, 0) wins.

Input: ([[2,3,4,5,6,7],[8,1,9,4,5,6],[7,3,2,3,2,4],[9,8,7,6,1,4],[5,4,3,8,9,10],[11,12,13,14,15,16]],)

Expected Output: (2, 0, 3)

Explanation: Blocks at (0,0) and (3,3) are invalid because they contain 1. Among the remaining valid blocks, the smallest representative is 2 at (0, 3).

Input: ([[4,5,6,7],[8,9,10,11]],)

Expected Output: (-1, -1, -1)

Explanation: The grid does not contain any full 3x3 block.

Input: ([[2,3,4],[5,1,6],[7,8,9]],)

Expected Output: (-1, -1, -1)

Explanation: The only 3x3 block is invalid because it contains 1.

Hints

Scan only block starts at rows and columns that are multiples of 3.
While checking a 3x3 block, track both its minimum value and whether it contains a 1.

Part 2: Can Inventory Produce the Target Recipe?

Constraints

0 <= target_quantity <= 10^9
0 <= inventory[item] <= 10^9
Each recipe quantity is a positive integer
There is at most one recipe per product
Let V be the number of distinct items reachable from the target and E the number of ingredient references among them

Examples

Input: ({'cake': [('sugar', 2), ('flour', 3), ('egg', 1)], 'sugar': [('cane', 5)]}, {'cane': 100, 'flour': 10, 'egg': 3}, 'cake', 2)

Expected Output: True

Explanation: Two cakes need 4 sugar, 6 flour, and 2 eggs. The 4 sugar require 20 cane. Inventory has enough cane, flour, and eggs.

Input: ({'cake': [('sugar', 2), ('flour', 3), ('egg', 1)], 'sugar': [('cane', 5)]}, {'cane': 15, 'flour': 10, 'egg': 3}, 'cake', 2)

Expected Output: False

Explanation: Two cakes still need 20 cane through sugar production, but only 15 are available.

Input: ({'sandwich': [('bread', 2), ('cheese', 1)], 'bread': [('flour', 3)]}, {'bread': 1, 'flour': 3, 'cheese': 1}, 'sandwich', 1)

Expected Output: True

Explanation: One sandwich needs 2 bread and 1 cheese. Inventory already has 1 bread and 1 cheese, so only 1 more bread must be produced, which needs 3 flour.

Input: ({'C': [('A', 1)], 'A': [('B', 1)], 'B': [('A', 1)]}, {}, 'C', 1)

Expected Output: False

Explanation: A reachable dependency cycle A -> B -> A exists, so production is impossible under the stated rule.

Input: ({}, {}, 'anything', 0)

Expected Output: True

Explanation: Producing zero units is always possible.

Hints

First detect whether the target's reachable recipe graph contains a cycle.
If the graph is acyclic, process items from product to ingredients and accumulate total demand for each item.