Day 26: Lowest Common Ancestor

Day 26 — Lowest Common Ancestor

Coding problem

Solution outline (coding)

• If root is p or q, return root; else search left and right subtrees.
• If both sides return non-null, root is the LCA; if only one side, return that non-null.
• This post-order style works when p and q are guaranteed in the tree.

Time complexity: O(n) — may visit many nodes in worst case.

Space complexity: O(h) — recursion stack.

from typing import Optional


class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


class Solution:
  def lowestCommonAncestor(
    self, root: TreeNode, p: TreeNode, q: TreeNode
  ) -> TreeNode:
    if not root or root is p or root is q:
      return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
      return root
    return left or right


# Input:  standard BST/tree with p,q nodes
# Output: their LCA node

SQL interview practice

1. Interview question

Companies / track: Meta, Google

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 **Meta, Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
file_system(path, parent_path, is_dir). BigQuery: given 2 paths, compute their lowest common ancestor directory using string operations and ARRAYs.

Tables implied by the prompt:

• file_system(path, parent_path, is_dir)

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 DFS to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Rates: SAFE_DIVIDE or NULLIF; define numerator and denominator.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

-- Longest common path prefix = directory LCA for POSIX-style paths.
WITH pair AS (
  SELECT @path_a AS a, @path_b AS b
)
SELECT
  ARRAY_TO_STRING(
    ARRAY(
      SELECT part FROM UNNEST(SPLIT((SELECT a FROM pair), '/')) AS part WITH OFFSET oa
      INNER JOIN UNNEST(SPLIT((SELECT b FROM pair), '/')) AS part_b WITH OFFSET ob
        ON oa = ob AND part = part_b
    ),
    '/'
  ) AS lca_path_prefix;