Google 面试题 #6 —— 树结构岛屿计数 + 井字棋结果判断 – 一亩三分地 – 谷歌面经 – 代面试 – 面试辅助

📌 Part A — Tree Islands Problem

Question:
In a tree of zeros and ones, an island is defined as a group of ones that are surrounded by zeros or are at the boundary of the tree.

Example:

        0(1)
       /    \
   1(2)      1(3)
    /          \
  0(5)         1(4)
   /  \
 1(6)  1(7)
  \      \
 1(8)    1(9)

Find the number of islands in the tree.

In the above example, there are 4 islands.

📌 Part A — Follow-up

Find the number of distinct island sizes.
Size = number of 1s in the island.

In the above example, distinct sizes are 1 and 2.

📌 Part B — Tic-Tac-Toe Judgment

/**
 * Determines the game outcome after a player's turn in Tic-Tac-Toe.
 *
 * @param board The current state of the game board. A 3x3 array where:
 *        'X' → Player X's mark
 *        'O' → Player O's mark
 *        ' ' → Empty cell
 *
 * @return:
 *        "X"    → X won
 *        "O"    → O won
 *        "Tie"  → Game is a draw
 *        "None" → Game is still ongoing
 */

✅ Part A：树中的岛屿

给定一个树，每个节点是 0 或 1。
岛屿：相邻的 1 组成的连通块，被 0 或边界隔离。

要求：

1. 统计岛屿数量
2. Follow-up：统计不同大小的岛屿数量

核心思路：

• DFS 遍历树
• 访问到 1 时展开整块区域
• 每块作为一个岛屿
• Follow-up 使用 set 去重岛屿大小

✅ Part B：井字棋胜负判断

输入 3×3 棋盘，判断结果：

• X 赢
• O 赢
• 平局
• 未结束

核心思路：

• 检查 3 行、3 列、2 斜线
• 优先判断胜负
• 再根据是否有空格 → Tie or None

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 OpenAI、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。