Day 13: Binary Search + Search Insert Position

Day 13 — Binary Search + Search Insert Position

Coding problem

Solution outline (coding)

• 704: classic binary search on sorted array — compare mid to target and shrink lo/hi.
• 35 (search insert position): use while lo < hi with mid = (lo+hi)//2 and bias to find first position ≥ target.
• Prove termination: interval shrinks; know whether to use <= vs < on bounds for your template.

Time complexity: O(log n) per search on an array of length n.

Space complexity: O(1).

from typing import List


class Solution:
  def search(self, nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
      mid = (lo + hi) // 2
      if nums[mid] == target:
        return mid
      if nums[mid] < target:
        lo = mid + 1
      else:
        hi = mid - 1
    return -1

  def searchInsert(self, nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums)
    while lo < hi:
      mid = (lo + hi) // 2
      if nums[mid] < target:
        lo = mid + 1
      else:
        hi = mid
    return lo


# Input:  search(nums=[-1,0,3,5,9,12], target=9) -> 4
# Output: searchInsert([1,3,5,6], 5) -> 2

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).
metrics(date, customer_id, metric_value) partitioned by date. BigQuery: show how proper date filters and clustering make existence checks over ranges behave like binary search over partitions, not full scans.

Tables implied by the prompt:

• metrics(date, customer_id, metric_value)

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 Binary Search 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.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

-- Partition pruning: filter on partition column first; clustering narrows row scans.
SELECT customer_id, metric_value
FROM metrics
WHERE date BETWEEN DATE_SUB(CURRENT_DATE(), INTERVAL 7 DAY) AND CURRENT_DATE()
  AND customer_id IN UNNEST(@customer_ids);