Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Google onsite coding round with a grid-based constraint satisfaction problem. The question looked like a straightforward 2D array thing until the rules started stacking up and I realized brute force wasn't going to cut it cleanly.

Questions Asked (1)

Given a 2D grid containing houses (H), flowers (F), and plantable spaces (O), determine whether you can place flowers on O spaces such that: no row or column contains more than one flower, and every house has exactly one adjacent flower that is not shared with any other house. Return a boolean. Follow-up: return all valid grid configurations instead.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The two constraints together are what make this annoying.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a constraint satisfaction problem where each flower placement must satisfy row/column uniqueness and cover exactly one adjacent house. Use backtracking with pruning to explore valid placements, and for the follow-up, collect all solutions. Discuss trade-offs between exhaustive search and heuristic optimizations.

Pro tip: Start by clarifying constraints and edge cases (e.g., houses with no adjacent O, multiple houses sharing a potential flower) to show thoroughness. Then, propose a backtracking solution but also mention how to optimize using bitmasks or bipartite matching for large grids.

1. Clarify and Restate

Confirm the rules: each row/column at most one flower, each house exactly one adjacent flower, and flowers only on O. Ask about grid size limits and whether diagonal adjacency counts.

2. Model as Constraints

Represent the grid and identify all possible flower positions (O cells). For each house, list adjacent O cells that could serve as its unique flower. Note that a flower can only serve one house.

3. Design Backtracking Algorithm

Recursively place flowers on valid O cells, ensuring row/column uniqueness and that each house gets exactly one flower. Use pruning: if a house has no available adjacent O or multiple houses compete for the same flower, backtrack early.

4. Handle Follow-up: All Configurations

Modify the backtracking to collect all valid complete assignments instead of stopping at the first. Ensure no duplicates and consider symmetry if applicable.

5. Analyze Complexity and Optimize

Discuss time/space complexity (exponential in worst case). Mention optimizations: bitmask for rows/columns, precomputing house-flower adjacency, or reducing to exact cover / bipartite matching.

Key Points to Mention

Constraint satisfaction and backtracking as the core approach
Pruning strategies to reduce search space (e.g., forward checking, MRV heuristic)
Handling the 'exactly one adjacent flower per house' constraint without sharing
Row and column uniqueness constraints
Complexity analysis and potential optimizations (bitmask, matching)
Edge cases: houses with no adjacent O, multiple houses sharing a single O, empty grid

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.