Compute inverse-depth weighted sum of nested lists
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Inverse-Depth Weighted Sum of a Nested List
You are given a **nested list** of integers. Each element is either:
- an integer, or
- another nested list.
Define the **depth** of an integer as the number of lists it is inside (top-level integers have depth 1).
Compute the **inverse-depth weighted sum**:
- Let `D` be the **maximum depth** in the structure.
- An integer at depth `d` has weight `D - d + 1`.
- Return the sum of `value * weight` over all integers.
### Input
- A nested list structure (you may assume an interface like:
- `isInteger()`, `getInteger()`, `getList()`), or an equivalent representation.
### Output
- An integer: the inverse-depth weighted sum.
### Example
Input: `[1, [4, [6]]]`
- Depths: `1` at depth 1, `4` at depth 2, `6` at depth 3. Max depth `D=3`.
- Weights: depth1 -> 3, depth2 -> 2, depth3 -> 1
- Sum = `1*3 + 4*2 + 6*1 = 17`
### Constraints
- Total number of integers across all lists can be up to e.g. `10^4`.
- Integers fit in 32-bit signed range.
Quick Answer: This question evaluates understanding of nested list traversal, depth computation, and weighted aggregation by the inverse of depth, focusing on concepts like maximum depth calculation and applying weights across hierarchical integer elements.
You are given a **nested list** of integers. Each element is either an integer or another nested list.
Define the **depth** of an integer as the number of lists it is inside (top-level integers have depth 1).
Compute the **inverse-depth weighted sum**:
- Let `D` be the **maximum depth** present in the structure.
- An integer at depth `d` has weight `D - d + 1` (so the **deepest** integers get weight 1, and shallower integers get larger weights).
- Return the sum of `value * weight` over all integers.
The input is provided as a nested list (a list whose elements are integers or further nested lists).
### Example
Input: `[1, [4, [6]]]`
- Depths: `1` at depth 1, `4` at depth 2, `6` at depth 3, so max depth `D = 3`.
- Weights: depth 1 -> 3, depth 2 -> 2, depth 3 -> 1.
- Sum = `1*3 + 4*2 + 6*1 = 17`.
Return `17`.
Constraints
- Total number of integers across all lists can be up to ~10^4.
- Integers fit in 32-bit signed range.
- An empty top-level list returns 0.
- Deeper integers receive smaller weights; the deepest integers always have weight 1.
Examples
Input: ([1, [4, [6]]],)
Expected Output: 17
Explanation: D=3. 1 at depth1 (w3), 4 at depth2 (w2), 6 at depth3 (w1): 1*3 + 4*2 + 6*1 = 17.
Input: ([[1, 1], 2, [1, 1]],)
Expected Output: 8
Explanation: D=2. 2 at depth1 (w2); four 1's at depth2 (w1): 2*2 + 4*1 = 8.
Hints
- Two passes are simplest: first compute the maximum depth D, then sum value * (D - depth + 1).
- Alternatively, run a BFS level by level, keep a running 'unweighted' accumulator that carries each level's prefix sum forward; the total accumulates each integer once per remaining level, which equals weighting by (D - depth + 1).
- Top-level integers are at depth 1, not depth 0 — be careful with the off-by-one in the weight formula.