Parse a Nested-List String and Compute Its Weighted Sum
GoogleSoftware Engineer · OnsiteLast 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
[]contributes0to 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^50 <= integer value <= 10^6- The string
sis 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?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.