Compute inverse-depth weighted sum of nested lists

Q: Compute inverse-depth weighted sum of nested lists

This is a Coding & Algorithms interview question from LinkedIn for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.