Nested List Weights

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

Config systems, org charts, and file-system scanners all share one data shape: a nested list whose leaves are integers. A JSON pricing config might charge per nesting level, an org rollup might weight headcount by distance from the CEO, and a manifest tool just wants the leaves back in order without loading everything eagerly. You will implement three contracts over one nested-list model, then make them survive shapes that are deep enough to break naive code.

A nested list is either an integer leaf or a list of nested lists. The top-level list sits at depth 1, a list inside it at depth 2, and so on. In [1, [2, 3], [[4]]] the 1 is at depth 1, 2 and 3 at depth 2, and 4 at depth 3.

Level 1 - Depth-weighted sum

def depth_sum(nested) -> int:
    """Each integer contributes value * depth (top-level depth 1)."""

Example:

depth_sum([1, [2, 3], [[4]]])  -> 23
# 1*1 + 2*2 + 3*2 + 4*3 = 1 + 4 + 6 + 12 = 23
 
depth_sum([6])                 -> 6
depth_sum([])                  -> 0

Level 2 - Reverse-weighted sum

def reverse_depth_sum(nested) -> int:
    """Each integer contributes value * (maxdepth - depth + 1), where maxdepth
    is the deepest integer's depth. Compute maxdepth first, then sum."""

The deepest integer gets weight 1, integers one level above it weight 2, and the top level gets weight maxdepth. Two passes are fine: compute maxdepth, then walk again to sum.

Example:

reverse_depth_sum([1, [2, 3], [[4]]])  -> 17
# maxdepth is 3, so weights are 3, 2, 2, 1:
# 1*3 + 2*2 + 3*2 + 4*1 = 3 + 4 + 6 + 4 = 17
 
reverse_depth_sum([6])                 -> 6
reverse_depth_sum([1, 2])              -> 3   # both at depth 1, weight 1
reverse_depth_sum([])                  -> 0

Level 3 - Lazy flatten iterator

class NestedIterator:
    def __init__(self, nested) -> None: ...
    def has_next(self) -> bool: ...
    def next(self) -> int: ...

Flatten the nested list lazily: next() returns the next integer in left-to-right order, and has_next() reports whether one remains. The iterator must do real lazy work - flattening the entire list up front into a materialized array defeats the point. An empty nested list (or one holding only empty lists) yields nothing. Calling next() when exhausted raises StopIteration (Python) or an Error (JavaScript/TypeScript).

Example:

it = NestedIterator([1, [2, 3], [[4]]])
it.has_next()  -> True
it.next()      -> 1
it.next()      -> 2
it.next()      -> 3
it.next()      -> 4
it.has_next()  -> False

Level 4 - Adversarial shapes

Empty lists at any depth: depth_sum([[], [[]], []]) == 0, reverse_depth_sum([[], [[]], []]) == 0, and NestedIterator([[], [[]], []]).has_next() == False.
Nesting 1000 levels deep must work in all three contracts without running out of memory or crashing. Build such inputs programmatically in your tests.
Negative and large leaf values.
A single integer wrapped once: [7].

Example:

deep = 7; repeat 1000 times: deep = [deep]
depth_sum(deep)          -> 7000        # 7 * 1000
reverse_depth_sum(deep)  -> 7           # the single leaf, weight 1
NestedIterator(deep)     -> yields just 7

Patterns used

Foundations primers this challenge draws on.

Stacks

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed