The Slow Leak

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L3
Asked in
Foursquare

Problem

A metrics rollup arrives in nested: a list where each element is either a leaf reading or another sub-group, with sub-groups nested to arbitrary depth. Return one flat list of every reading in left-to-right order. Treat a string as a single reading that stays intact rather than splitting into characters, and let an empty sub-group contribute nothing.

Nested groups. One flat stream.

Example 1

Input:

nested = [1,[2,3],[4,[5]]]

Output:

[1,2,3,4,5]

Example 2

Input:

nested = ["ok",[],["warn",["crit"]]]

Output:

["ok","warn","crit"]

Worked solution and explanation

What this really is

Strip the metrics costume and this is depth-first flattening of a tree, with one landmine buried in Python's type system: a string is iterable. The instant you decide 'if it is iterable, recurse into it,' you have signed up to recurse into 'crit' character by character, then into 'c', which is a length-1 string that is iterable again, and so on until the stack gives out. Anyone can write the recursion. What separates candidates is the single guard that pulls strings out as leaves, and writing it BEFORE the iterability check, not after.

The trap

Iterability check first
if hasattr(item, '__iter__'): recurse. A string passes that test, so 'crit' recurses into 'c', 'r', 'i', 't', each a length-1 string that is iterable again. The descent never reaches a non-iterable, so you get a RecursionError or an effective hang.
Leaf check first
if isinstance(item, str) or not hasattr(item, '__iter__'): append. Strings short-circuit into the result before the iterability test ever runs, and only real sub-groups get recursed into.

Building it

Step 1: Classify each element

For each element, decide leaf or group. A leaf is a string or anything without __iter__; everything else is a sub-group. Putting the string clause first is what makes the type guard correct, not just present.

Step 2: Recurse into sub-groups

When an element is a sub-group, flatten it with the same function and splice its readings in with extend. Recursion handles arbitrary depth for free: you never need to know how deep the export nests.

Step 3: Let order fall out of the traversal

Because you append leaves and splice recursive results in the order you meet them, the natural left-to-right, depth-first order falls out with no sorting or bookkeeping. Empty sub-groups simply yield an empty splice.

The solution

Recursive flatten with a leaf-first guard
def flatten_iter(nested) -> list:
    result = []
    for item in nested:
        if isinstance(item, str) or not hasattr(item, "__iter__"):
            result.append(item)
        else:
            result.extend(flatten_iter(item))
    return result

The string check sits ahead of the iterability check on purpose.

Common follow-up questions