Day 78: Longest Palindromic Substring

Day 78 — Longest Palindromic Substring

Coding problem

Solution outline (coding)

• Expand around centers: odd and even palindromes; track longest.
• DP: dp[i][j] true if s[i]==s[j] and inner is palindrome.
• Manacher O(n) is bonus.

Time complexity: O(n²) expand; O(n) Manacher optional.

Space complexity: O(1) expand; O(n²) DP table.

class Solution:
  def longestPalindrome(self, s: str) -> str:
    def expand(l: int, r: int) -> str:
      while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
      return s[l + 1 : r]

    best = ''
    for i in range(len(s)):
      best = max(best, expand(i, i), expand(i, i + 1), key=len)
    return best


# Input:  s = "babad"
# Output: "bab" or "aba"

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).
strings(text_id, content). BigQuery: find longest palindromic substring length via UDF and generate distribution across documents.

Tables implied by the prompt:

• strings(text_id, content)

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 DP / Expand 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.
• Rates: SAFE_DIVIDE or NULLIF; define numerator and denominator.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT text_id, LENGTH(content) AS len FROM strings LIMIT 10;