Katkat

Parse a Nested-List String and Compute Its Weighted Sum

GoogleSoftware Engineer · Onsite

Last updated

Implement a parser that processes a string representation of a nested list and computes the depth-weighted sum of all non-negative integers contained within it.

Problem Statement

You are given a string s representing a valid nested list of non-negative integers. Each nested list starts with an opening bracket [ and ends with a closing bracket ]. Elements inside a list can be integers or further nested lists, separated by commas ,.

The outermost list has a depth of 1. Any nested list inside a list of depth d has a depth of d + 1.

Calculate and return the depth-weighted sum of all integers in the string. The depth-weighted sum is defined as the sum of each integer multiplied by its corresponding nesting depth.

Note:

  • The input string may contain arbitrary whitespace characters (spaces ' '), which should be ignored.
  • An empty list [] contributes 0 to the total sum.
  • Multi-digit numbers must be parsed properly.

Interface

def depth_weighted_sum(s: str) -> int:
    pass

Input & Output Format

  • Input: s (a string representing a syntactically valid nested list)
  • Output: An integer representing the total depth-weighted sum

Examples

Example 1

Input: s = "[[1, 1], 2, [1, 1]]"
Output: 10
Explanation:
- Four 1's at depth 2: 4 * (1 * 2) = 8
- One 2 at depth 1: 1 * (2 * 1) = 2
Total sum = 8 + 2 = 10

Example 2

Input: s = "[1, [4, [6]]]"
Output: 27
Explanation:
- 1 at depth 1: 1 * 1 = 1
- 4 at depth 2: 4 * 2 = 8
- 6 at depth 3: 6 * 3 = 18
Total sum = 1 + 8 + 18 = 27

Example 3

Input: s = "[10, [ ], [20, [30]]]"
Output: 140
Explanation:
- 10 at depth 1: 10 * 1 = 10
- [] has no numbers
- 20 at depth 2: 20 * 2 = 40
- 30 at depth 3: 30 * 3 = 90
Total sum = 10 + 40 + 90 = 140

Constraints

  • 2 <= len(s) <= 10^5
  • 0 <= integer value <= 10^6
  • The string s is guaranteed to be a valid representation of a nested list.
  • The depth of nested lists will not exceed 10^4.

Edge Cases to Consider

  • Consecutive brackets such as [[]] or [[[1]]].
  • Multi-digit numbers adjacent to closing brackets (e.g., [123]).
  • Varied spacing between brackets, numbers, and commas.

Hints

Hint 1

You do not need to build a full abstract syntax tree (AST) or nested list structure in memory; a linear scan is sufficient.

Hint 2

Track the current depth using an integer counter that increments on '[' and decrements on ']'.

Hint 3

Accumulate digits into a temporary number variable and commit the weighted value whenever a non-digit delimiter (such as ',', ']', or whitespace) is encountered.

Follow-up questions

  • What if the weighting is reversed, where elements at the maximum depth have weight 1 and elements at depth 1 have the largest weight (max_depth)?
  • How would your approach change if integers could also be negative?
  • How would you modify the parser to validate that the string is syntactically well-formed (e.g., balanced brackets, proper comma placement) instead of assuming valid input?