Nested list weight sum: DFS, BFS, iterators and inverse weights

In this article

1. Before you start
2. Why interviewers ask this
3. Nested list weight sum from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

Nested list weight sum is a common warm-up in machine coding rounds, where a short first problem grows into several follow-ups.

Why interviewers ask this

The question looks like a warm-up and then grows follow-ups, which is exactly why interviewers keep it. The first version is short. The next asks for inverse weights, then an iterator that hands out the integers one at a time, then an asynchronous version, so the candidate who wrote the first answer carelessly pays for it three times. It appears in industry coding rounds, alongside other small design-a-data-structure problems such as least recently used (LRU) cache implementation in Python, and alongside multi-level problems that keep adding requirements, such as the CodeSignal in-memory database assessment.

More practice problems of this kind are collected in the interview learning library.

A weak answer writes recursion without saying why depth starts at 1 or what happens on a very deep list. A strong answer states the depth rule, picks a walk on purpose, gives the cost, and names the edge cases before being asked.

Nested list weight sum from first principles

Nested list

A nested list is a list whose items are each either an integer or another nested list, so the lists can sit inside one another to any depth.

Depth-weighted sum

A depth-weighted sum is the total of every integer in a nested list multiplied by its depth, where the depth is the number of lists you must enter to reach it, starting at 1 for the outer list.

Generator

A generator is a Python function that uses yield to hand out values one at a time and pauses between them, so it produces an iterator without a class.

Iterator

An iterator is an object that hands out the items of a collection one at a time, remembering where it stopped, and signals the end when none are left.

In plain words

Think of a set of boxes. Some boxes hold numbers and some hold smaller boxes. A number is worth its face value times the boxes you opened to reach it. Open the outer box, and its numbers count once. Open a box inside it, and those numbers count twice. The analogy breaks here: a nested list can be so deep that the computer, not the puzzle, runs out of room.

In one precise sentence: for each integer, multiply its value by the number of lists enclosing it, and add the products. Nothing else is needed. The rest of this page is only about how to walk the lists and how to cope when they nest very deeply.

Text description of the diagram

• In [[1,1],2,[1,1]] the integer 2 sits at depth 1 and contributes 2.
• The four 1s sit at depth 2 and contribute 8.
• The weighted sum is 10.

Step 1: Fix the depth rule

The outer list is depth 1, and every list you enter adds one. This is the rule that decides every answer, so state it aloud before coding. For [[1,1],2,[1,1]] the integer 2 sits directly in the outer list, so it has depth 1 and contributes 2. The four 1s sit one list deeper, so each has depth 2 and together they contribute 8.¹

Counting the outer list as depth 0 shifts every weight down by one, so the answer loses the sum of all the integers. In the run, the sum of all integers is 6, and the answer drops from 10 to 4.¹ That is the common error, and it costs the whole question. Input: the list and the rule. Output: a known weight for every integer. What you now know: depth is a count of enclosing lists, so a walk needs to carry that count.

Step 2: Walk the list and add value times depth

Walk the items of the current list in order. When an item is an integer, add its value times the current depth to a running total. An integer needs no further walking, because it holds nothing else.

The function below is the one that ran in the test: it takes a list and the depth to use, and the default of 1 encodes Step 1.¹

def dfs(x, depth=1):
    total = 0
    for v in x:
        total += v * depth if isinstance(v, int) else dfs(v, depth + 1)
    return total

The isinstance test separates an integer from a list, because a list must be walked and an integer must not be. The second half of the expression is Step 3. Input: a list and a depth. Output: the weighted sum of that list.

Step 3: Go one level deeper on every inner list

When an item is itself a list, call the same function on it with the depth increased by one and add the result. This is depth-first search (DFS): follow one branch to its end before looking at the next. It is correct because the weighted sum of a list is the sum of its integers' products plus the weighted sums of its sublists, each computed one level deeper.

Every item is looked at exactly once, so the time is linear in the number of integers and lists, written O(n). The space is the depth of the nesting, because each open list is a pending call on the call stack, the pile of unfinished function calls Python keeps. In the test, this recursive version, an explicit-stack version and a level-by-level version agreed on 2,000 random lists.¹

Step 4: Add up and return

The total of the integers' products at the top level and the returned values of all sublists is the answer. For [1,[4,[6]]] that is 1 times 1, plus 4 times 2, plus 6 times 3, which is 1 plus 8 plus 18, so 27.¹ Return the total from the outer call and you are done. There is no separate combine stage, because adding as you go already built the result, and each inner call hands its subtotal to the call above it. The result is the same however the lists are nested. The step-through below follows exactly this list, one step per section above.

1 · Fix the depth rule2 · Add value times depth3 · Go one level deeper4 · Add and returnReplay

Step-by-step description

1. The outer list is depth 1.
2. The integer 1 is at depth 1.
3. Each inner list adds one to the depth.
4. The products sum to 27.

• The outer list is depth 1.
• The integer 1 contributes 1 times 1.
• The integer 4 at depth 2 contributes 8 and the integer 6 at depth 3 contributes 18.
• The weighted sum is 27.

Worked example

Two small lists, then a stress test, all run in Python 3.12; the lists are illustrative inputs and every output is saved.¹

The second column is the sum of Steps 1 to 4. The third column uses inverse weights: the deepest integers weigh 1, and an integer at depth d, where m is the depth of the deepest integer, weighs m minus d plus 1. Lists that hold no integer do not count towards m. For [[1,1],2,[1,1]] the maximum depth of an integer is 2, so the integer 2 weighs 2 and each 1 weighs 1: 4 plus 4 is 8. The inverse sum is 8 against 10 for the normal sum.¹

Text description of the diagram

• The weight of an integer is the maximum depth minus its depth plus 1.
• In [[1,1],2,[1,1]] the integer 2 weighs 2 and each 1 weighs 1.
• The inverse sum is 8, while the normal sum is 10.

Now the stress test, which is where recursion shows its limit. A list nested 500 levels deep summed correctly, and so did one nested 900 deep, but the recursive version raised RecursionError at a depth of 999 with Python's default limit of 1,000.¹ The Python documentation says the limit prevents infinite recursion from crashing the interpreter, and warns that raising it too high can lead to a crash (Python 3.15 documentation, as of October 2026). An explicit stack and a level-by-level walk both returned 700,000 for a list nested 100,000 deep, the correct 7 times 100,000.¹

Trade-offs and edge cases

The three walks give the same answer; they differ in how they fail.

Text description of the diagram

• On 10,000 inner lists side by side (depth 2), the stack of (list, depth) pairs peaked at 10,000 entries and a stack of iterators at 2.
• On a chain nested 900 deep, recursion (open frames) and a stack of iterators peaked at 900 and the stack of pairs at 1.

The diagram shows what the table cannot: the peak number of pending entries on two inputs. An explicit stack replaces the call stack with a list of pending (list, depth) pairs, so the depth is limited by memory, not by the interpreter. It pushes every inner list of the current list at once, so on 10,000 inner lists side by side (only 2 deep) its peak was 10,000 entries, while a stack of iterators, one per open list, peaked at 2 and held 900 on a chain 900 deep, where the recursion also held 900 frames and the stack of pairs only 1.¹

The level-by-level walk, which is breadth-first search (BFS), a walk that visits every item of one level before the next, uses a queue from the Python standard library: undefined, whose appends and pops at either end cost approximately constant time. A plain list's pop(0) shifts every element, which the same documentation says costs O(n).

Empty lists. A list such as [[], [[]]] has no integers and sums to 0; the walks handle it with no special case.

Negative integers and zero. They work unchanged: the product is simply negative or zero.

Booleans. In Python, True is an integer, so a boolean in the input is counted as 1; say so, or reject it explicitly.

Interviewer constraints. Ask whether the depth is bounded. If the depth is small, recursion is the clearest answer; if it is unbounded, switch to a stack.

How to answer it in an interview

The spoken structure: state the depth rule, name the walk and its cost, then name the failure mode and the variants.

Common mistakes

• "The outer list is depth 0." (wrong) Every weight drops by one, and the result loses the sum of all integers: 10 becomes 4 on the example. (right) "The outer list is depth 1."
• "Recursion is always fine." (wrong) A list nested 999 deep raised an error in Python's default setup. (right) "Recursion for bounded depth, a stack when depth is unbounded."
• "Check type(v) == list." (wrong) A tuple inside the input is then multiplied as if it were an integer: tuple * depth repeats the tuple, and adding that to an int raises TypeError. (right) "Test for an integer, recurse only into lists (or tuples), and reject anything else on purpose."
• "Flatten first, then weight." (wrong) Flattening throws the depth away, so the weights are lost. (right) "Carry the depth with each integer."

Follow-up questions

What if your input is not a list?

Decide the contract and say it. The recursive dfs above treats every non-integer item as a container: it raised TypeError on a bare integer and on None, flattened a tuple like a list, and raised RecursionError on [1, "ab"], since a one-character string iterates to itself.¹ The test iterator (NestedIterator) instead accepts only integers, lists and tuples and raises TypeError otherwise, and the same guard fits dfs: check isinstance(x, (list, tuple)) and raise TypeError for anything else, which gave TypeError on 5, None and the string and 10 on the first example.¹ Either accept only lists and raise a clear error, or document what you accept.

How do you build an iterator that outputs values in sequence?

An iterator is an object whose __next__ method returns the next value and raises StopIteration at the end (Python tutorial, as of October 2026). For a nested list, keep a stack of iterators and, on each call, advance the top one until you find an integer, pushing a new iterator for every inner list. It stays lazy: the test returned the first two integers of a list holding a 100,000-deep chain without walking the chain.¹

If the input is wrapped in an interface with isInteger(), getInteger() and getList() methods, the same walk applies with the isinstance test replaced by isInteger(). For a class with state to save and restore (getState, setState) or an iterator of iterators, see low level design interview questions. A generator with yield from (Python Enhancement Proposal (PEP) 380) is shorter but recursive, so it meets the same depth limit.

How do you extend it to 2D and to an async iterator?

Rows of a grid are one level of nesting, so the same iterator already handles 2D input. For asynchronous data, an async def function containing yield is an asynchronous generator that async for consumes (PEP 525). Await the fetch of each lazy sub-list before pushing its iterator; the test returned 1 to 5 in order.¹ When several consumers share one iterator, concurrency questions apply: guard the shared stack.

What other edge cases are you thinking about?

Empty lists and empty input produce no values, and a deep chain needs a stack. Negative numbers work unchanged. Booleans count as integers in Python. A sublist shared in two places is counted twice, and a list that contains itself loops forever with a stack or a queue, or hits RecursionError with recursion, unless you track visited lists by id.

How do you compute an inverse-depth weighted sum of a nested list?

The deepest integer must weigh 1, so take the maximum depth D from the deepest integer, not the deepest list. In one level-by-level pass keep S, the plain sum, and W, the depth-weighted sum, and return (D + 1) times S minus W. The popular running-sum shortcut breaks when the deepest lists are empty: on [1,[[]]] the usual queue-of-elements version gives 2 where the answer is 1, and on [[1,1],2,[1,1],[[[]]]] it gives 14 where the answer is 8.¹ The test gave 8 and 17 for the two examples, 8 for [[1,1],2,[1,1],[[[]]]] and 1 for [1,[[]]], and matched an independent two-pass method on 2,000 random lists.¹

What are the time and space complexity?

Time is O(n) in the total number of integers and lists, since each is visited once. Space is O(d) for recursion or for a stack of iterators, where d is the depth. A stack of (list, depth) pairs is O(n) in the worst case, because it pushes all inner lists of a list at once: 10,000 side-by-side inner lists, only 2 deep, peaked at 10,000 entries.¹ The queue is O(w), where w is the widest level.

Sources

1. sys: sys.getrecursionlimit and sys.setrecursionlimit — Python 3.15 documentation (date = read date), 24 Oct 2026
2. The Python Tutorial: Iterators and Generators — Python 3.15 documentation (date = read date), 24 Oct 2026
3. collections: deque — Python 3.15 documentation (date = read date), 24 Oct 2026
4. PEP 525: Asynchronous Generators — Python Enhancement Proposals (Selivanov), 28 Jul 2016
5. PEP 380: Syntax for Delegating to a Subgenerator — Python Enhancement Proposals (Ewing), 13 Feb 2009