Day 29: Number of Islands

Day 29 — Number of Islands

Coding problem

Solution outline (coding)

• Iterate cells; on unseen ‘1’, start DFS/BFS, mark visited cells as ‘0’ or use a visited set.
• Flood-fill to the entire island; increment island count per new start.
• Boundary check indices and water ‘0’.

Time complexity: O(m · n) — each cell constant work.

Space complexity: O(m · n) — recursion stack or queue in worst case.

from typing import List


class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
    if not grid:
      return 0
    m, n = len(grid), len(grid[0])

    def dfs(i: int, j: int) -> None:
      if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != '1':
        return
      grid[i][j] = '0'
      for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        dfs(i + di, j + dj)

    cnt = 0
    for i in range(m):
      for j in range(n):
        if grid[i][j] == '1':
          cnt += 1
          dfs(i, j)
    return cnt


# Input:  grid with "1" land and "0" water
# Output: island count

SQL interview practice

1. Interview question

Companies / track: Google, Meta

Meta and Google both lean on ads and product surfaces: event streams, CTR-style rates, windowed metrics, and careful handling of identity joins.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google, Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
grid(cell_id, row, col, is_land). BigQuery: approximate number of islands (4-neighbor connectivity) per snapshot and discuss feasibility vs approximations using clustering.

Tables implied by the prompt:

• grid(cell_id, row, col, is_land)
• islands(4-neighbor connectivity)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map BFS / DFS Flood Fill to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Sessions / streaks: often LAG/LEAD or gap flags, then aggregate; check boundary dates.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT snapshot_date, COUNT(DISTINCT CONCAT(CAST(row AS STRING), ':', CAST(col AS STRING))) AS land_cells
FROM grid
WHERE is_land
GROUP BY snapshot_date;