Katkat
Back

Compute inverse-depth weighted sum of a nested list

AtlassianMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to traverse nested list structures using recursion or iterative stacks and compute a value based on the nesting depth of individual elements.

Problem Statement

Given a nested list of integers, compute the sum of all integers in the list, where each integer is weighted by the inverse of its nesting depth. The depth of an element is defined as the number of nested lists it is enclosed in. The top-level elements have a depth of 1.

For example, if the input is [1, [2, 3], [[4]]], the depths are:

  • 1: depth 1 (weight 1/1)
  • 2: depth 2 (weight 1/2)
  • 3: depth 2 (weight 1/2)
  • 4: depth 3 (weight 1/3)

The final result is (1 * 1) + (2 * 0.5) + (3 * 0.5) + (4 * 0.333...).

Function Signature

def weighted_inverse_sum(nested_list: list) -> float:

Constraints

  • The input can be a mix of integers or lists.
  • The nesting depth can be up to 100 levels.
  • An empty list should contribute 0 to the sum.

Examples

Example 1: Input: [1, [2, 2]] Calculation: 1/1 + (2/2 + 2/2) = 1 + 2 = 3.0 Output: 3.0

Example 2: Input: [[1, 1], 2, [1, [1]]] Calculation: (1/2 + 1/2) + (2/1) + (1/2 + 1/3) = 1 + 2 + 0.833 = 3.833... Output: 3.8333333333333335

Hints

Hint 1

Use a helper function that takes the current list and the current depth as parameters to keep track of the hierarchy.

Hint 2

If the current element is an integer, add (value / current_depth) to the running total.

Hint 3

If the current element is a list, recursively call the helper function with (current_depth + 1).

Follow-up questions

  • How would you modify the algorithm if the depth weight was calculated as (depth^2) instead of (1/depth)?
  • What are the space complexity implications of using recursion for a deeply nested list, and could you implement this using an iterative stack approach?
  • If the input list contained circular references (a list containing itself), how would you detect them to prevent an infinite loop?