Inverse-Depth Weighted Sum of a Nested Integer List
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a nested list of integers, written as a string in bracket notation such as `"[3,[2,[5]]]"`. Each element of a list is either an integer or another list.
The **depth** of an integer is the number of lists that contain it, counting the outermost list. In `"[3,[2,[5]]]"`, `3` has depth 1, `2` has depth 2 and `5` has depth 3. Let `maxDepth` be the largest depth of any integer in the input. The **weight** of an integer is `maxDepth - depth + 1`, so the most deeply nested integers have weight 1 and the integers directly inside the outermost list have the largest weight.
Return the sum, over every integer in the input, of the integer multiplied by its weight.
### Function Signature
```python
def inverse_depth_weighted_sum(nested: str) -> int:
```
### Rules
- The string follows this grammar and contains no whitespace: a list is `[`, then zero or more elements separated by `,`, then `]`; an element is an integer or a list; an integer is an optional `-` followed by decimal digits, with no leading zeros other than the single digit `0` (so `-0` never appears).
- The whole string is exactly one list, the outermost one.
- Only integers determine `maxDepth`. Empty lists, however deeply nested, contribute nothing and do not raise `maxDepth`.
- If the input contains no integers at all, for example `"[]"` or `"[[],[[]]]"`, return `0`.
### Constraints
- `2 <= len(nested) <= 10^5`
- `nested` is valid under the grammar above.
- Every integer is between `-100` and `100` inclusive.
- Lists are nested at most 50 deep, counting the outermost list.
- Under these bounds the result fits in a signed 32-bit integer.
### Examples
**Example 1**
- Input: `nested = "[[2,2],3,[2,2]]"`
- Output: `14`
- Explanation: `maxDepth` is 2. The four `2`s have depth 2 and weight 1, contributing `8`; the `3` has depth 1 and weight 2, contributing `6`.
**Example 2**
- Input: `nested = "[3,[2,[5]]]"`
- Output: `18`
- Explanation: `maxDepth` is 3, so the weights of `3`, `2` and `5` are 3, 2 and 1: `3*3 + 2*2 + 5*1 = 18`.
**Example 3**
- Input: `nested = "[2,[[]],[-1]]"`
- Output: `3`
- Explanation: The empty list inside `[[]]` holds no integer, so `maxDepth` is 2, not 3. The result is `2*2 + (-1)*1 = 3`.
Overview: Compute a weighted sum over a nested list of integers given in bracket notation, where integers closer to the top level weigh more and the deepest ones weigh one. Tests parsing nested structure, tracking depth, handling empty lists and negative values, and keeping the work to a single pass.
Read the full LinkedIn Software Engineer interview experience this question came from
You are given a nested list of integers, written as a string in bracket notation such as `"[3,[2,[5]]]"`. Each element of a list is either an integer or another list.
The **depth** of an integer is the number of lists that contain it, counting the outermost list. In `"[3,[2,[5]]]"`, `3` has depth 1, `2` has depth 2 and `5` has depth 3. Let `maxDepth` be the largest depth of any integer in the input. The **weight** of an integer is `maxDepth - depth + 1`, so the most deeply nested integers have weight 1 and the integers directly inside the outermost list have the largest weight.
Implement `inverse_depth_weighted_sum(nested)`, which returns the sum, over every integer in the input, of the integer multiplied by its weight.
### Rules
- The string follows this grammar and contains no whitespace: a list is `[`, then zero or more elements separated by `,`, then `]`; an element is an integer or a list; an integer is an optional `-` followed by decimal digits, with no leading zeros other than the single digit `0` (so `-0` never appears).
- The whole string is exactly one list, the outermost one.
- Only integers determine `maxDepth`. Empty lists, however deeply nested, contribute nothing and do not raise `maxDepth`.
- If the input contains no integers at all, for example `"[]"` or `"[[],[[]]]"`, return `0`.
- The answer is a single integer, so it is unique for every valid input.
### Constraints
- `2 <= len(nested) <= 10^5`
- `nested` is valid under the grammar above.
- Every integer is between `-100` and `100` inclusive.
- Lists are nested at most 50 deep, counting the outermost list.
- Under these bounds the result fits in a signed 32-bit integer.
### Examples
**Example 1**
- Input: `nested = "[[2,2],3,[2,2]]"`
- Output: `14`
- Explanation: `maxDepth` is 2. The four `2`s have depth 2 and weight 1, contributing `8`; the `3` has depth 1 and weight 2, contributing `6`.
**Example 2**
- Input: `nested = "[3,[2,[5]]]"`
- Output: `18`
- Explanation: `maxDepth` is 3, so the weights of `3`, `2` and `5` are 3, 2 and 1: `3*3 + 2*2 + 5*1 = 18`.
**Example 3**
- Input: `nested = "[2,[[]],[-1]]"`
- Output: `3`
- Explanation: The empty list inside `[[]]` holds no integer, so `maxDepth` is 2, not 3. The result is `2*2 + (-1)*1 = 3`.
Constraints
- 2 <= len(nested) <= 10^5
- nested is valid under the stated grammar (no whitespace, exactly one outermost list)
- -100 <= every integer <= 100
- Lists are nested at most 50 deep, counting the outermost list
- The result fits in a signed 32-bit integer
Examples
Input: ("[]",)
Expected Output: 0
Input: ("[5]",)
Expected Output: 5
Hints
- You never need to build the nested structure; a single left-to-right scan that tracks the current depth is enough to know each integer's depth.
- The weight depends on maxDepth, which you only know at the end. Can you rewrite sum(v * (maxDepth - depth + 1)) as a combination of quantities you can accumulate without knowing maxDepth yet?
- Update maxDepth only when you actually read an integer, so empty lists never affect it.