← Google Interview Insights

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

Intermediate
May 2026

Summary

Google SWE coding round with a board game simulation problem. Pretty straightforward premise but the details matter more than they look.

Questions Asked (1)

Q1

Given a string representing a board where 'T' is a token, 'C' is a coin, and '.' is empty, calculate how many coins can be collected if tokens can move across the board (each coin collected only once).

Algorithms & Data Structures
Author's notes

My first read was 'oh this is just count the C characters' and I nearly said that out loud.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the movement rules and constraints, as the problem is underspecified. Then, model the board as a graph where tokens can move to collect coins, and propose an algorithm such as BFS/DFS or dynamic programming to maximize coin collection, ensuring each coin is collected once.

Pro tip: Demonstrate strong problem-solving by explicitly stating assumptions and asking clarifying questions before diving into a solution. This shows you can handle ambiguity and collaborate effectively, which is highly valued at Google.

1. Clarify the Problem

Ask questions to understand token movement rules, number of tokens, and whether tokens can share paths or collect multiple coins. Confirm if the goal is to maximize total coins collected or if there are other objectives.

2. Define the Model

Represent the board as a grid graph with cells as nodes and possible moves as edges. Identify tokens and coins as special nodes, and consider if tokens can move independently or if there are interactions.

3. Choose an Algorithm

Based on constraints, select an appropriate algorithm. For example, if tokens move independently and coins are collected by visiting cells, use BFS/DFS to find reachable coins. If tokens can cooperate, consider maximum bipartite matching or DP.

4. Handle Constraints and Edge Cases

Discuss time and space complexity, and how to handle large boards. Address edge cases like no tokens, no coins, or blocked paths.

5. Test and Validate

Walk through a small example to verify the approach. Mention potential pitfalls and how to debug or optimize the solution.

Key Points to Mention

  • Clarify movement rules: Can tokens move in all directions? Are there obstacles? Can tokens move through each other?
  • Model as a graph problem: Use BFS/DFS for reachability, or maximum flow/matching for assignment if tokens compete for coins.
  • Consider multiple tokens: If tokens are independent, sum reachable coins; if they interact, need to avoid double-counting coins.
  • Time and space complexity: Aim for O(R*C) or O(R*C*T) where T is number of tokens, and discuss optimizations.
  • Edge cases: No tokens, no coins, tokens surrounded by empty cells, coins unreachable.
  • Communication: Explain your thought process clearly and ask for feedback, as interviewers value problem-solving approach over just the answer.

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