Day 28: Review – Week 4

Day 28 — Review – Week 4

Coding problem

Solution outline (coding)

• Review tree BFS/DFS, LCA, and vertical order — one weak area from each.
• Re-derive the three templates from memory on paper.
• List edge cases: empty tree, single node, skewed chain.

Time complexity: Varies.

Space complexity: Varies.

class ReviewDay:
  """Practice / review: Review – Week 4."""

  def practice_plan(self):
    return [
      "Pick 2–3 problems from this phase; re-solve timed without notes.",
      "For each: pattern name, time/space complexity, one alternative approach.",
    ]


# Input:  (your choice of problems from this week or phase)
# Output: a short list of gaps to drill before the next session

SQL interview practice

1. Interview question

Companies / track: Review / mixed (see weekly theme)

This is a review / mixed day. Expect SQL that blends data quality, funnels, and metric definitions—the same mix you see across consumer tech and ads analytics.

What you are asked to write (SQL prompt):

Review / mixed week — use the same tables and deliverables as in a standard onsite SQL round.
Create generic BigQuery helpers (views/CTEs) that implement DFS and BFS on hierarchy tables, and add timing metadata to compare their performance.

Tables implied by the prompt:

• helpers(views/CTEs)

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 Review to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Cost: selective columns, partition pruning, avoid SELECT * when tables are huge.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

-- Store graph as adjacency ARRAY; BFS one layer per query iteration in scripts, or use recursive CTE for small graphs.
WITH RECURSIVE bfs AS (
  SELECT @start AS node, 0 AS depth
  UNION ALL
  SELECT e.dst, b.depth + 1
  FROM bfs AS b
  JOIN graph_edges AS e ON b.node = e.src
  WHERE b.depth < 20
)
SELECT node, MIN(depth) FROM bfs GROUP BY node;