Day 2 — Valid Anagram

Coding problem

ProblemValid Anagram
LeetCode ID(s)LeetCode #242
DifficultyEasy
PatternHashing / Sorting
Company tagsMeta, Google
Suggested time10m

Solution outline (coding)

Focus on the Hashing / Sorting pattern. Start by writing out a few examples by hand, then identify the invariant you must maintain (e.g., prefix sums, window bounds, visited set, heap ordering). Aim for an implementation you can explain in under a minute, including time and space complexity.

Show Python solution
from collections import Counter


class Solution:
  def isAnagram(self, s: str, t: str) -> bool:
    if len(s) != len(t):
      return False

    return Counter(s) == Counter(t)


# Input:  s = "anagram", t = "nagaram"
# Output: True

SQL question

events(user_id, event_type, event_time). BigQuery: for each user, compare multiset of event_type in first 7 days since first event vs next 7 days; return users where they match.

How to approach (SQL)

Break the prompt into steps:

  • Identify source tables, required joins, and filters (especially on time partitions).
  • Decide where you need GROUP BY vs. window functions (e.g., ROW_NUMBER, SUM() OVER, COUNT() OVER).
  • For BigQuery, think about partitioning and clustering to avoid unnecessary full scans.
  • Write the query in stages (CTEs) so each step is easy to debug and reason about. Finish by checking edge cases: nulls, late events, duplicated keys, and extreme values.
Show SQL solution (BigQuery)
WITH first_event AS (
  SELECT
    user_id,
    MIN(event_time) AS first_ts
  FROM
    events
  GROUP BY
    user_id
),
tagged_events AS (
  SELECT
    e.user_id,
    e.event_type,
    e.event_time,
    DATE_DIFF(DATE(e.event_time), DATE(f.first_ts), DAY) AS day_offset
  FROM
    events AS e
  JOIN
    first_event AS f
  USING (user_id)
),
windowed_counts AS (
  SELECT
    user_id,
    CASE
      WHEN day_offset BETWEEN 0 AND 6 THEN 1  -- first 7 days
      WHEN day_offset BETWEEN 7 AND 13 THEN 2 -- next 7 days
      ELSE NULL
    END AS window_id,
    event_type,
    COUNT(*) AS cnt
  FROM
    tagged_events
  WHERE
    day_offset BETWEEN 0 AND 13
  GROUP BY
    user_id,
    window_id,
    event_type
),
pivoted AS (
  SELECT
    user_id,
    window_id,
    ARRAY_AGG(STRUCT(event_type, cnt) ORDER BY event_type) AS multiset
  FROM
    windowed_counts
  WHERE
    window_id IS NOT NULL
  GROUP BY
    user_id,
    window_id
),
reshaped AS (
  SELECT
    user_id,
    ARRAY_AGG(IF(window_id = 1, multiset, NULL) IGNORE NULLS)[SAFE_OFFSET(0)] AS multiset_first,
    ARRAY_AGG(IF(window_id = 2, multiset, NULL) IGNORE NULLS)[SAFE_OFFSET(0)] AS multiset_second
  FROM
    pivoted
  GROUP BY
    user_id
)
SELECT
  user_id
FROM
  reshaped
WHERE
  multiset_first IS NOT NULL
  AND multiset_second IS NOT NULL
  AND multiset_first = multiset_second;