Day 81: Number of Connected Components

Day 81 — Number of Connected Components

Coding problem

Solution outline (coding)

• Union-Find on n nodes; for each edge, union(a,b).
• After all edges, count distinct roots — that is number of components.
• Compare to n and edge count for validation.

Time complexity: O(n α(n)) — inverse Ackermann.

Space complexity: O(n) — parent/rank arrays.

from typing import List


class Solution:
  def countComponents(self, n: int, edges: List[List[int]]) -> int:
    parent = list(range(n))

    def find(x: int) -> int:
      while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
      return x

    def union(a: int, b: int) -> None:
      ra, rb = find(a), find(b)
      if ra != rb:
        parent[rb] = ra

    for a, b in edges:
      union(a, b)
    return len({find(i) for i in range(n)})


# Input:  n = 5, edges = [[0,1],[1,2],[3,4]]
# Output: 2

SQL interview practice

1. Interview question

Companies / track: Google

Google: SQL screens usually assume BigQuery, Ads / Search / YouTube-style fact tables, and talking through bytes processed and partition pruning.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
graph_edges(src, dst). BigQuery: compute number of connected components using iterative labeling or precomputed union-find mapping in a table.

Tables implied by the prompt:

• graph_edges(src, dst)

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 Union-Find to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH nodes AS (
  SELECT src AS n FROM graph_edges
  UNION DISTINCT
  SELECT dst FROM graph_edges
),
e_cnt AS (SELECT COUNT(*) AS edge_count FROM graph_edges),
n_cnt AS (SELECT COUNT(*) AS node_count FROM nodes)
SELECT
  n_cnt.node_count,
  e_cnt.edge_count,
  e_cnt.edge_count = n_cnt.node_count - 1 AS passes_edge_count_rule
FROM n_cnt, e_cnt;