Day 6: Longest Consecutive Sequence

Day 6 — Longest Consecutive Sequence

Coding problem

Solution outline (coding)

• Insert all numbers into a hash set for O(1) membership.
• For each number x, only start a sequence if x - 1 is not in the set (avoids recounting).
• Walk x+1, x+2, … while present and track streak length; keep the maximum.

Time complexity: O(n) — each number is visited only as a sequence start or in one forward walk.

Space complexity: O(n) — the hash set.

from typing import List


class Solution:
  def longestConsecutive(self, nums: List[int]) -> int:
    s = set(nums)
    best = 0
    for x in s:
      if x - 1 in s:
        continue
      y = x + 1
      while y in s:
        y += 1
      best = max(best, y - x)
    return best


# Input:  nums = [100,4,200,1,3,2]
# Output: 4

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).
logins(user_id, login_date). BigQuery: use gaps-and-islands to compute longest streak of consecutive login_date per user and return users with max_streak >= 10 plus streak bounds.

Tables implied by the prompt:

• logins(user_id, login_date)

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 Hash Set to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Sessions / streaks: often LAG/LEAD or gap flags, then aggregate; check boundary dates.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH ordered AS (
  SELECT
    user_id,
    login_date,
    DATE_DIFF(login_date, LAG(login_date) OVER (PARTITION BY user_id ORDER BY login_date), DAY) AS gap
  FROM logins
),
flags AS (
  SELECT
    user_id,
    login_date,
    SUM(CASE WHEN gap IS NULL OR gap > 1 THEN 1 ELSE 0 END) OVER (PARTITION BY user_id ORDER BY login_date) AS grp
  FROM ordered
),
streaks AS (
  SELECT user_id, grp, COUNT(*) AS streak_len, MIN(login_date) AS streak_start, MAX(login_date) AS streak_end
  FROM flags
  GROUP BY user_id, grp
)
SELECT user_id, streak_start, streak_end, streak_len
FROM streaks
WHERE streak_len >= 10;