Day 8: Valid Palindrome

Day 8 — Valid Palindrome

Coding problem

Solution outline (coding)

• Use two pointers at both ends of the string (after normalizing case and skipping non-alphanumeric).
• If characters differ, return False; move inward until pointers cross.
• Empty or single-character normalized strings are palindromes.

Time complexity: O(n) — each character examined at most once.

Space complexity: O(1) — only pointers if you filter in place; O(n) if you build a filtered string.

class Solution:
  def isPalindrome(self, s: str) -> bool:
    i, j = 0, len(s) - 1
    while i < j:
      while i < j and not s[i].isalnum():
        i += 1
      while i < j and not s[j].isalnum():
        j -= 1
      if s[i].lower() != s[j].lower():
        return False
      i += 1
      j -= 1
    return True


# Input:  s = "A man, a plan, a canal: Panama"
# Output: True

SQL interview practice

1. Interview question

Companies / track: Meta

Meta: expect event logging, ads / integrity, and social product analytics—deduping, sessionization, and window functions are frequent themes.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
pageviews(user_id, url, ts). BigQuery: normalize path (lowercase, remove non-alphanumerics), detect palindromes with STRING_REVERSE, flag per view, and compute share of users with at least one palindrome URL.

Tables implied by the prompt:

• pageviews(user_id, url, ts)
• path(lowercase, remove non-alphanumerics)

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 Two Pointers 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 norm AS (
  SELECT
    user_id,
    url,
    LOWER(REGEXP_REPLACE(url, r'[^a-zA-Z0-9]', '')) AS norm_path
  FROM pageviews
),
pal AS (
  SELECT
    user_id,
    url,
    norm_path = REVERSE(norm_path) AS is_palindrome
  FROM norm
)
SELECT
  SAFE_DIVIDE(COUNT(DISTINCT IF(is_palindrome, user_id, NULL)), COUNT(DISTINCT user_id)) AS share_users_with_palindrome
FROM pal;