Day 33: Word Ladder

Day 33 — Word Ladder

Coding problem

Solution outline (coding)

• BFS from beginWord: try changing one letter at a time using a word set for O(1) membership.
• Each level = one transformation; stop when you reach endWord (shortest path in unweighted graph).
• Prune using only words still in the dictionary.

Time complexity: O(N · L²) typical — N words, length L, neighbor generation.

Space complexity: O(N) — BFS queue + seen set.

from collections import deque
from typing import List


class Solution:
  def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
    words = set(wordList)
    if endWord not in words:
      return 0
    q = deque([(beginWord, 1)])
    seen = {beginWord}
    L = len(beginWord)
    while q:
      w, d = q.popleft()
      if w == endWord:
        return d
      arr = list(w)
      for i in range(L):
        old = arr[i]
        for c in 'abcdefghijklmnopqrstuvwxyz':
          arr[i] = c
          nw = ''.join(arr)
          if nw in words and nw not in seen:
            seen.add(nw)
            q.append((nw, d + 1))
        arr[i] = old
    return 0


# Input:  beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
# Output: 5

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).
dictionary(word) and edges for words differing by 1 letter. BigQuery: estimate shortest transformation path length between two words via precomputed layers.

Tables implied by the prompt:

• dictionary(word)

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

-- Precompute one-edit neighbors offline; here: sample pairs of same length from dictionary.
SELECT a.word AS w1, b.word AS w2
FROM dictionary AS a
JOIN dictionary AS b
  ON a.word < b.word AND LENGTH(a.word) = LENGTH(b.word)
LIMIT 500;