Day 54: Minimum Height Trees

Day 54 — Minimum Height Trees

Coding problem

Solution outline (coding)

• Leaf stripping: repeatedly remove leaves until ≤2 nodes remain — those are MHT roots.
• Or think in terms of longest path / tree diameter endpoints.
• BFS level-by-level from leaves inward.

Time complexity: O(n).

Space complexity: O(n) — adjacency + queue.

from typing import List
from collections import defaultdict, deque


class Solution:
  def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
    if n == 1:
      return [0]
    g = defaultdict(set)
    for a, b in edges:
      g[a].add(b)
      g[b].add(a)
    leaves = deque([i for i in range(n) if len(g[i]) == 1])
    rem = n
    while rem > 2:
      for _ in range(len(leaves)):
        u = leaves.popleft()
        rem -= 1
        for v in g[u]:
          g[v].remove(u)
          if len(g[v]) == 1:
            leaves.append(v)
        g[u].clear()
    return list(leaves)


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

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).
Same network. BigQuery: approximate roots with minimal height by sampling and precomputing eccentricity-like metrics.

Tables implied by the prompt:

• Infer schemas from the prompt and state them before coding.

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 Topological / BFS 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).

SELECT src, COUNT(*) AS deg FROM network_edges GROUP BY src ORDER BY deg DESC LIMIT 5;