Day 15: Reverse Linked List

Day 15 — Reverse Linked List

Coding problem

Solution outline (coding)

• Iteratively: keep prev = None, cur = head, and repeatedly set cur.next = prev, then advance.
• Alternatively recurse: reverse head.next then attach head at the tail of the reversed rest.
• Watch for cycles — always break the forward link you are rewiring.

Time complexity: O(n) — visit each node once.

Space complexity: O(1) iterative; O(n) call stack if recursive.

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


class Solution:
  def reverseList(self, head: ListNode) -> ListNode:
    prev = None
    cur = head
    while cur:
      nxt = cur.next
      cur.next = prev
      prev = cur
      cur = nxt
    return prev


# Input:  1->2->3->4->5
# Output: 5->4->3->2->1

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, ts, event_type). BigQuery: build ordered ARRAY of event_type per user/day, and another query that returns reversed sequence; discuss pros/cons of storing ordered arrays.

Tables implied by the prompt:

• events(user_id, ts, event_type)

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 Linked List 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.
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH daily AS (
  SELECT user_id, DATE(ts) AS d, ARRAY_AGG(event_type ORDER BY ts) AS fwd,
    ARRAY_REVERSE(ARRAY_AGG(event_type ORDER BY ts DESC)) AS rev
  FROM events
  GROUP BY user_id, d
)
SELECT user_id, d, fwd, rev FROM daily;