Day 30: Clone Graph

Day 30 — Clone Graph

Coding problem

Solution outline (coding)

• Map old node → cloned node with a hash map.
• BFS/DFS from a start node: for each neighbor, create clone if missing, then wire edges.
• Return clone of the start node.

Time complexity: O(V + E) — vertices and edges.

Space complexity: O(V) — clone storage + map.

from typing import Optional


class Node:
  def __init__(self, val=0, neighbors=None):
    self.val = val
    self.neighbors = neighbors if neighbors is not None else []


class Solution:
  def cloneGraph(self, node: Optional[Node]) -> Optional[Node]:
    if not node:
      return None
    seen = {}

    def dfs(n: Node) -> Node:
      if n in seen:
        return seen[n]
      c = Node(n.val)
      seen[n] = c
      for nb in n.neighbors:
        c.neighbors.append(dfs(nb))
      return c

    return dfs(node)


# Input:  adjacency list for connected graph
# Output: deep copy with same structure

SQL interview practice

1. Interview question

Companies / track: Meta

Meta: expect event logging, ads / integrity, and social product analytics—deduping, sessionization, and window functions are frequent themes.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
graph_edges(src, dst). BigQuery: store adjacency as ARRAYs and write a query/UDF to clone a graph structure into a normalized table; discuss versioning.

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 BFS/DFS + Hash Map 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.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH agg AS (
  SELECT src, ARRAY_AGG(dst ORDER BY dst) AS nbrs
  FROM graph_edges
  GROUP BY src
)
SELECT src, nbrs FROM agg;