Compute a Depth-Weighted Sum of a Nested List
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Depth-Weighted Sum of a Nested List
## Problem
A nested value is either an integer or a list of nested values. Integers in the outermost list have depth `1`; entering another list increases the depth by `1`.
Return the sum of every integer multiplied by its depth.
### Function Contract
Implement `depthWeightedSum(nestedList)`.
- Input: an outer list whose elements are integers or nested lists.
- Output: the integer depth-weighted sum.
### Rules and Edge Cases
- The outer list or any inner list may be empty.
- Integer values may be zero or negative.
- Nesting may be uneven: siblings do not need to have the same depth.
### Examples
```text
Input: [3, 8, [2, 14], [2, [91]]]
Output: 320
Calculation: 3*1 + 8*1 + 2*2 + 14*2 + 2*2 + 91*3 = 320
```
```text
Input: [[], [5]]
Output: 10
```
```hint Carry the current depth
Each recursive call or breadth-first layer needs to know the multiplier for integers at that level.
```
```hint Consider extreme nesting
Compare the memory behavior of recursion with an explicit queue or stack when the structure is very deep.
```
Quick Answer: Compute the depth-weighted sum of integers in an unevenly nested list. Compare recursive and iterative traversals while handling empty lists, negative values, and nesting deep enough to risk stack overflow.