Day 16: Merge Two Sorted Lists

Day 16 — Merge Two Sorted Lists

Coding problem

Solution outline (coding)

• Use a dummy head to avoid edge cases; keep a tail pointer for the merged list.
• Repeatedly append the smaller of list1.val and list2.val and advance that list.
• When one list empties, attach the remainder of the other.

Time complexity: O(n + m) — each node appended once.

Space complexity: O(1) — only pointer rewiring.

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


class Solution:
  def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode()
    cur = dummy
    while l1 and l2:
      if l1.val <= l2.val:
        cur.next = l1
        l1 = l1.next
      else:
        cur.next = l2
        l2 = l2.next
      cur = cur.next
    cur.next = l1 or l2
    return dummy.next


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

SQL interview practice

1. Interview question

Companies / track: Meta

Meta: expect event logging, ads / integrity, and social product analytics—deduping, sessionization, and window functions are frequent themes.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
orders_a(order_id, user_id, created_at) and orders_b(order_id, user_id, created_at). BigQuery: merge these two sorted streams into a single time-ordered view per user, flagging duplicates and conflicting records.

Tables implied by the prompt:

• orders_a(order_id, user_id, created_at)
• orders_b(order_id, user_id, created_at)

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 Merge to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Dedup: ROW_NUMBER() or explicit keys; state first vs last row wins.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH merged AS (
  SELECT 'a' AS src, order_id, user_id, created_at FROM orders_a
  UNION ALL
  SELECT 'b' AS src, order_id, user_id, created_at FROM orders_b
),
ranked AS (
  SELECT *, ROW_NUMBER() OVER (PARTITION BY user_id, order_id ORDER BY created_at) AS rn
  FROM merged
)
SELECT * FROM ranked ORDER BY user_id, created_at;