Compute inverse-depth weighted sum of a nested list
Company: Atlassian
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
You are given a **nested list** of integers, where each element is either:
- an integer, or
- a list that follows the same rule (i.e., a nested list).
Define the **depth** of an integer as the number of lists that contain it.
- Example: In `[1,[2,[3]]]`, the integer `1` has depth 1, `2` has depth 2, and `3` has depth 3.
Let `D` be the **maximum depth** among all integers in the structure. Compute the **inverse-depth weighted sum** where each integer with depth `d` is weighted by:
\[
weight(d) = D - d + 1
\]
Return the total weighted sum.
## Examples
- Input: `[1,[2,[3]]]`
- Maximum depth `D=3`
- Sum = `1*(3-1+1) + 2*(3-2+1) + 3*(3-3+1)` = `1*3 + 2*2 + 3*1 = 10`
- Output: `10`
- Input: `[[1,1],2,[1,1]]`
- Maximum depth `D=2`
- Output: `8`
## Constraints (reasonable interview constraints)
- Total number of integers `N` up to ~1e4.
- Total nested list elements (including lists) up to ~1e4.
- Integers fit in 32-bit signed range.
## Function Signature (language-agnostic)
`int inverseDepthSum(NestedList nested)`
Quick Answer: This question evaluates competency in working with nested data structures and depth-based aggregation, measuring the ability to reason about hierarchical list contents and weighted summation; it falls under the Coding & Algorithms domain and targets practical implementation skills rather than purely theoretical understanding.