Day 55: Network Delay Time

Day 55 — Network Delay Time

Coding problem

Solution outline (coding)

• Dijkstra from source K on weighted graph; min distance array.
• Relax edges with a min-heap (dist, node).
• Answer = max distance to any node; infinity means unreachable.

Time complexity: O((V + E) log V) with a binary heap.

Space complexity: O(V + E).

import heapq
from typing import List
from collections import defaultdict


class Solution:
  def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
    g = defaultdict(list)
    for u, v, w in times:
      g[u].append((v, w))
    dist = {k: 0}
    heap = [(0, k)]
    while heap:
      d, u = heapq.heappop(heap)
      if d != dist.get(u, float('inf')):
        continue
      for v, w in g[u]:
        nd = d + w
        if nd < dist.get(v, float('inf')):
          dist[v] = nd
          heapq.heappush(heap, (nd, v))
    if len(dist) < n:
      return -1
    return max(dist.values())


# Input:  times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
# 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, weight). BigQuery: approximate single-source shortest paths via iterative relaxation steps with staging tables; discuss cost and alternatives.

Tables implied by the prompt:

• graph_edges(src, dst, weight)

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 Dijkstra 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).

WITH RECURSIVE relax AS (
  SELECT @k AS node, 0 AS dist
  UNION ALL
  SELECT e.dst, r.dist + e.weight
  FROM relax AS r
  JOIN graph_edges AS e ON r.node = e.src
  WHERE r.dist < 1000
)
SELECT node, MIN(dist) AS approx_dist FROM relax GROUP BY node;