Day 52: Alien Dictionary

Day 52 — Alien Dictionary

Coding problem

Solution outline (coding)

• Build directed edges from adjacent words: first differing letters a → b.
• Run topological sort; if cycle, return "".
• Compare word to prefix of next for invalid prefix case ("abc" before "ab").

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

Space complexity: O(V + E).

from typing import List
from collections import defaultdict, deque


class Solution:
  def alienOrder(self, words: List[str]) -> str:
    g = defaultdict(set)
    indeg = {c: 0 for w in words for c in w}
    for a, b in zip(words, words[1:]):
      for x, y in zip(a, b):
        if x != y:
          if y not in g[x]:
            g[x].add(y)
            indeg[y] += 1
          break
      else:
        if len(a) > len(b):
          return ''
    q = deque([c for c in indeg if indeg[c] == 0])
    order = []
    while q:
      c = q.popleft()
      order.append(c)
      for v in g[c]:
        indeg[v] -= 1
        if indeg[v] == 0:
          q.append(v)
    if len(order) != len(indeg):
      return ''
    return ''.join(order)


# Input:  words = ["wrt","wrf","er","ett","rftt"]
# Output: one valid order e.g. "wertf"

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).
alien_dict(words, order_string). BigQuery: validate that words respect character ordering by mapping chars to ranks and comparing adjacent words.

Tables implied by the prompt:

• alien_dict(words, order_string)

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 Topological Sort to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH chars AS (
  SELECT word, GENERATE_ARRAY(0, LENGTH(word) - 1) AS idxs
  FROM alien_dict
),
ranks AS (
  SELECT word, ARRAY_AGG(SUBSTR(word, i + 1, 1) ORDER BY i) AS letters FROM chars, UNNEST(idxs) AS i
  GROUP BY word
)
SELECT word, letters FROM ranks ORDER BY word LIMIT 20;