Google Interview Problem #6 — Tree Islands + Tic-Tac-Toe – VO help – interview coach

📌 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 — Tree Islands

Given a binary tree of 0s and 1s, an island is a connected group of 1s separated by 0s or boundaries.

To solve:

• DFS to find connected components
• Count the number of components
• Follow-up: compute distinct component sizes

✅ Part B — Tic-Tac-Toe

Given a 3×3 board, determine the result:

• Check rows/columns/diagonals
• If no winner, check for empty cells
• Return X / O / Tie / None