Day 61: Implement Trie

Day 61 — Implement Trie

Coding problem

Solution outline (coding)

• Trie node: map char → child and is_end flag.
• insert walks/creates path; search and startsWith walk with different end checks.

Time complexity: O(L) per op for word length L.

Space complexity: O(total chars) — trie nodes.

class TrieNode:
  def __init__(self):
    self.children = {}
    self.end = False


class Trie:
  def __init__(self):
    self.root = TrieNode()

  def insert(self, word: str) -> None:
    n = self.root
    for ch in word:
      n = n.children.setdefault(ch, TrieNode())
    n.end = True

  def search(self, word: str) -> bool:
    n = self.root
    for ch in word:
      if ch not in n.children:
        return False
      n = n.children[ch]
    return n.end

  def startsWith(self, prefix: str) -> bool:
    n = self.root
    for ch in prefix:
      if ch not in n.children:
        return False
      n = n.children[ch]
    return True


# Input:  insert "apple", search "app" -> False, startsWith "app" -> True
# Output: as above

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).
autocomplete(prefix, full_string). BigQuery: implement trie-like behavior using prefix tables and compute suggestion lists per prefix with popularity ranking.

Tables implied by the prompt:

• autocomplete(prefix, full_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 Trie 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).

SELECT prefix, ARRAY_AGG(full_string ORDER BY popularity DESC LIMIT 10) AS suggestions
FROM autocomplete
GROUP BY prefix;