Coding & SQL Problems

from collections import Counter
from datetime import datetime, timedelta
import heapq

def top_k_active(events, k, now=None):
    now = now or datetime.utcnow()
    cutoff = now - timedelta(days=7)
    counts = Counter(
        e["user_id"] for e in events if e["event_at"] >= cutoff
    )
    # heapq.nlargest is O(n log k), better than full sort when k << n
    return heapq.nlargest(k, counts.items(), key=lambda x: x[1])

from datetime import timedelta

GAP = timedelta(minutes=30)

def sessionize(events):
    results = []
    if not events:
        return results
    prev_user = None
    prev_time = None
    session_id = 0
    count = 0
    for e in events:
        new_session = (
            prev_user != e["user_id"]
            or (e["event_at"] - prev_time) > GAP
        )
        if new_session:
            if prev_user is not None:
                results.append((prev_user, session_id, count))
            session_id = session_id + 1 if prev_user == e["user_id"] else 1
            count = 0
        count += 1
        prev_user = e["user_id"]
        prev_time = e["event_at"]
    # flush last session
    results.append((prev_user, session_id, count))
    return results

def subarray_sum_eq_k(nums, k):
    seen = {0: 1}      # prefix sum value → number of times seen
    running = 0
    answer = 0
    for n in nums:
        running += n
        # If running - k has been seen, that means there's a prefix
        # ending earlier whose removal leaves a subarray summing to k
        answer += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return answer

from collections import defaultdict
from datetime import timedelta

def cohort_retention(signups, events, max_weeks=4):
    # signups: dict user_id -> signup_date
    # events:  list of (user_id, event_date)
    cohort_size = defaultdict(int)
    retained   = defaultdict(set)
    for uid, signup in signups.items():
        cohort_week = signup - timedelta(days=signup.weekday())
        cohort_size[cohort_week] += 1
    for uid, ev_date in events:
        signup = signups.get(uid)
        if not signup:
            continue
        weeks_since = (ev_date - signup).days // 7
        if 1 <= weeks_since <= max_weeks:
            cohort_week = signup - timedelta(days=signup.weekday())
            retained[(cohort_week, weeks_since)].add(uid)
    return {
        (cw, wk): len(retained[(cw, wk)]) / cohort_size[cw]
        for (cw, wk) in retained
    }

import numpy as np

def flag_anomalies(series, window=28, k=3):
    """series: list of (date, value) sorted by date"""
    values = np.array([v for _, v in series])
    out = []
    for i in range(len(values)):
        lo = max(0, i - window)
        history = values[lo:i]
        if len(history) < 7:  # not enough history
            out.append(False)
            continue
        mu, sigma = history.mean(), history.std(ddof=1)
        out.append(abs(values[i] - mu) > k * sigma)
    return list(zip([d for d, _ in series], out))

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        if target - n in seen:
            return (seen[target - n], i)
        seen[n] = i
    return None

# All pairs
def all_pairs(nums, target):
    seen = {}
    out = []
    for i, n in enumerate(nums):
        for j in seen.get(target - n, []):
            out.append((j, i))
        seen.setdefault(n, []).append(i)
    return out

-- DENSE_RANK so ties share a rank: "second-highest distinct salary"
SELECT dept_id, salary
FROM (
  SELECT
    dept_id,
    salary,
    DENSE_RANK() OVER (PARTITION BY dept_id ORDER BY salary DESC) AS rk
  FROM employees
) t
WHERE rk = 2;

WITH first_signup AS (
  SELECT user_id, MIN(event_at) AS signup_at
  FROM events WHERE event = 'signup'
  GROUP BY user_id
),
first_upload AS (
  SELECT s.user_id, s.signup_at, MIN(e.event_at) AS upload_at
  FROM first_signup s
  JOIN events e
    ON e.user_id = s.user_id
   AND e.event = 'upload'
   AND e.event_at BETWEEN s.signup_at AND s.signup_at + INTERVAL '7 days'
  GROUP BY s.user_id, s.signup_at
),
first_publish AS (
  SELECT u.user_id, u.signup_at, u.upload_at, MIN(e.event_at) AS publish_at
  FROM first_upload u
  JOIN events e
    ON e.user_id = u.user_id
   AND e.event = 'publish'
   AND e.event_at BETWEEN u.upload_at AND u.upload_at + INTERVAL '7 days'
  GROUP BY u.user_id, u.signup_at, u.upload_at
)
SELECT
  (SELECT COUNT(*) FROM first_signup)  AS signups,
  (SELECT COUNT(*) FROM first_upload)  AS uploads,
  (SELECT COUNT(*) FROM first_publish) AS publishes;

WITH grouped AS (
  SELECT
    user_id,
    week,
    -- tabibitosan trick: weeks since epoch minus rank within user
    -- is constant within a consecutive run
    DATE_DIFF('week', DATE '1970-01-05', week) -
      ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY week) AS streak_key
  FROM weekly_active
),
streaks AS (
  SELECT
    user_id,
    streak_key,
    COUNT(*) AS streak_weeks
  FROM grouped
  GROUP BY user_id, streak_key
)
SELECT user_id, MAX(streak_weeks) AS longest_streak
FROM streaks
GROUP BY user_id;

import numpy as np

def ctr_with_se(imps, clicks):
    n = len(imps)
    mean_i = imps.mean()
    mean_c = clicks.mean()
    var_i = imps.var(ddof=1)
    var_c = clicks.var(ddof=1)
    cov_ic = np.cov(imps, clicks, ddof=1)[0, 1]
    ctr = mean_c / mean_i
    var_ctr = (var_c / mean_i**2
               - 2 * ctr * cov_ic / mean_i**2
               + ctr**2 * var_i / mean_i**2) / n
    return ctr, np.sqrt(var_ctr)