Day 71: Random Pick with Weight

Day 71 — Random Pick with Weight

Coding problem

Solution outline (coding)

• Build prefix sums of weights; pickIndex draws uniform r in [0, total) and binary search prefix array.
• Alternatively alias method for O(1) pick — overkill for interviews unless asked.

Time complexity: O(log n) per pick; O(n) preprocess.

Space complexity: O(n) — prefix array.

import bisect
import random
from typing import List


class Solution:
  def __init__(self, w: List[int]):
    self.pref = []
    s = 0
    for x in w:
      s += x
      self.pref.append(s)

  def pickIndex(self) -> int:
    t = random.randint(1, self.pref[-1])
    return bisect.bisect_left(self.pref, t)


# Input:  w = [1,3], pickIndex returns 0 or 1 with weights
# Output: stochastic index

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).
weighted_choices(user_id, option, weight). BigQuery: simulate Random Pick with Weight by normalizing weights to probabilities and using RAND() with cumulative sums.

Tables implied by the prompt:

• weighted_choices(user_id, option, weight)
• RAND(…)

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

WITH w AS (
  SELECT option, weight, SUM(weight) OVER () AS tot FROM weighted_choices WHERE user_id = @uid
),
r AS (SELECT *, RAND() * tot AS pick FROM w)
SELECT option FROM r WHERE pick <= weight LIMIT 1;