Day 2 — Valid Anagram

Coding problem

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

Solution outline (coding)

  • If lengths differ, return False immediately.
  • Count characters in both strings with a fixed-size array (26 letters) or a hash map for Unicode.
  • Compare counts (or sort both strings and compare) — multisets must match exactly.

Time complexity: O(n) — one pass per string, where n is the length.

Space complexity: O(1) for 26 lowercase letters; O(k) for alphabet size k with a hash map.

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 interview practice

1. Interview question

Companies / track: Meta, Google

Meta and Google both lean on ads and product surfaces: event streams, CTR-style rates, windowed metrics, and careful handling of identity joins.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta, Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
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.

Tables implied by the prompt:

  • events(user_id, event_type, event_time)

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 Hashing / Sorting to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
  • Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).
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;