Day 17: Linked List Cycle + Cycle II

Day 17 — Linked List Cycle + Cycle II

Coding problem

Solution outline (coding)

• Cycle (141): fast and slow pointers; if they meet, a cycle exists.
• Entry (142): after meet, reset one pointer to head; move both one step until they meet at the cycle start.
• Alternatively use a set of visited nodes — simpler but O(n) space.

Time complexity: O(n) — linear in list length.

Space complexity: O(1) for Floyd; O(n) with a hash set.

class ListNode:
  def __init__(self, x):
    self.val = x
    self.next = None


class Solution:
  def hasCycle(self, head: ListNode) -> bool:
    slow = fast = head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow is fast:
        return True
    return False

  def detectCycle(self, head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow is fast:
        break
    else:
      return None
    p = head
    while p is not slow:
      p = p.next
      slow = slow.next
    return p


# Input:  cycle at node index 1 -> hasCycle True, detectCycle returns that node
# Output: no cycle -> hasCycle False, detectCycle None

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).
sessions(user_id, session_id, start_ts, end_ts). BigQuery: detect cycles/overlaps where sessions overlap in time for the same user; return overlapped intervals and total overlapped duration.

Tables implied by the prompt:

• sessions(user_id, session_id, start_ts, end_ts)

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 Fast / Slow Pointer to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Filter time first: predicate on DATE(ts) / partition column before heavy joins; state the window in plain English.
• Sessions / streaks: often LAG/LEAD or gap flags, then aggregate; check boundary dates.
• Rates: SAFE_DIVIDE or NULLIF; define numerator and denominator.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH pairs AS (
  SELECT
    a.user_id,
    a.session_id AS s1,
    b.session_id AS s2,
    GREATEST(a.start_ts, b.start_ts) AS overlap_start,
    LEAST(a.end_ts, b.end_ts) AS overlap_end
  FROM sessions AS a
  JOIN sessions AS b
    ON a.user_id = b.user_id AND a.session_id < b.session_id
  WHERE a.end_ts > b.start_ts AND b.end_ts > a.start_ts
)
SELECT user_id, s1, s2, overlap_start, overlap_end,
  TIMESTAMP_DIFF(overlap_end, overlap_start, SECOND) AS overlap_sec
FROM pairs;