Day 74: Nested List Weight Sum

Day 74 — Nested List Weight Sum

Coding problem

Solution outline (coding)

• DFS on nested structure: if integer, add depth * val; if list, recurse with depth+1.
• Iterative: stack of (iterator, depth).

Time complexity: O(n) — total nested integers.

Space complexity: O(d) — recursion depth.

from typing import List


class Solution:
  def depthSum(self, nestedList: List) -> int:
    def dfs(x, depth: int) -> int:
      if isinstance(x, int):
        return depth * x
      return sum(dfs(y, depth + 1) for y in x)

    return sum(dfs(x, 1) for x in nestedList)


# Input:  nestedList = [[1,1],2,[1,1]]  (each inner list is a nested level)
# Output: 10

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).
nested_lists(list_id, parent_id, weight). BigQuery: compute weighted sums with level-based weights and validate against business rules.

Tables implied by the prompt:

• nested_lists(list_id, parent_id, weight)

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 DFS 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 depth AS (
  SELECT list_id, parent_id, weight, 1 AS lvl FROM nested_lists WHERE parent_id IS NULL
  UNION ALL
  SELECT n.list_id, n.parent_id, n.weight, d.lvl + 1
  FROM nested_lists AS n
  JOIN depth AS d ON n.parent_id = d.list_id
)
SELECT SUM(weight * lvl) AS weighted_sum FROM depth;