SyntaxPilot
Courses/Python Coding Questions/Lesson 10
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python Coding Questions · Lesson 10 of 30

List questions VI

flatten a nested list (recursion vs a stack)chunk a listgroup by a key (defaultdict, itertools.groupby needs sorted input)

These are the notes for Python Coding Questions, episode 10, the last round of list questions. Three questions: flattening a nested list (a list with lists inside it, to any depth), splitting a list into chunks without losing the last few items, and grouping items by a key, the way a courier sorts parcels by city. Along the way you'll see why a one-line comprehension can only open one level, why recursion hits a wall at about 1,000 levels and how your own stack removes that wall, why floor division quietly drops a student, and why itertools.groupby gives the wrong answer on unsorted data.

Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real. Tracebacks show the file as main.py, as in the compiler; Python itself shortens very long recursive tracebacks with a "Previous line repeated" line.

Q1: Flatten a nested list

Real-life example: a big gift box. Inside are some sweets, and some smaller boxes, and one of those boxes has another box inside it. You want every sweet out, in one line, in the order you meet them. So you open every box you find, however deep it goes. In Python the box is a list, and the sweets are the numbers.

A nested list is a list that has other lists inside it. Flattening it means producing one plain list of all the non-list items, in order.

Input Output
[[1, 2], [3, [4, 5]], 6] [1, 2, 3, 4, 5, 6]
[1, [2, [3, [4]]]] (four levels) [1, 2, 3, 4]
[] []
[[[]]] (a box holding an empty box) []
one 7 inside 5,000 boxes [7]

Ask the interviewer: how deep can the nesting go? Is it known (say, always two levels) or any depth? Can there be loose items next to lists, like the 6 above? Should tuples (and other containers) be opened too, or only lists? Should strings be kept whole? (Almost always yes.) Must the order be kept? (Usually yes.)

Attempt 1: a comprehension with two fors

The quick answer from the course: a comprehension (a list built from a loop in one expression) with two fors: for each box, for each x in the box.

boxes = [[1, 2], [3, [4, 5]], 6]
print([x for box in boxes for x in box])

Output:

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    print([x for box in boxes for x in box])
                                       ^^^
TypeError: 'int' object is not iterable

Why it crashes: the inner for x in box loops over each item of boxes. The first two are lists, but the 6 at the end isn't a box: it's a sweet lying loose, and you can't loop over a number. Iterable means "something a for loop can walk through": lists, tuples, strings, dicts and ranges are iterable; an int is not.

Attempt 2: put the 6 in a box, or use sum(boxes, [])

Wrap the 6 in a list, and try a second trick you'll see online: sum with an empty list as the starting value (sum then "adds" the lists together with +).

boxes = [[1, 2], [3, [4, 5]], [6]]
print([x for box in boxes for x in box])
print(sum(boxes, []))

Output:

[1, 2, 3, [4, 5], 6]
[1, 2, 3, [4, 5], 6]

Why it's wrong: no crash, but [4, 5] is still inside a list. Both tricks open exactly one level of boxes. The number of fors is fixed when you write the code: two fors open two levels, and no more. Nobody told us how deep the boxes go, so a fixed number of loops can never be right. We need code that opens a box the same way, whatever is inside it. (sum(boxes, []) is also slow: each + copies the list built so far, so it is O(n²) on many boxes.)

Fix 1: recursion

For each x, ask: is it a box? isinstance(x, list) checks the type of a value: it is True when x is a list, and False for the 6 (an int).

If it's a box, call flatten on it: the same function, one level deeper. A function that calls itself is recursion. If it's a sweet, append it: that's the base case, the situation where the function stops calling itself.

def flatten(items):
    flat = []
    for x in items:
        if isinstance(x, list):
            flat.extend(flatten(x))      # a box: open it the same way
        else:
            flat.append(x)               # a sweet: keep it
    return flat

print(flatten([[1, 2], [3, [4, 5]], 6]))
print(flatten([]), flatten([[[]]]), flatten([1, [2, [3, [4]]]]))

deep = [7]
for _ in range(5_000):
    deep = [deep]                        # 5,000 boxes inside each other
print(flatten(deep))

Output (Python itself shortens the repeated lines):

[1, 2, 3, 4, 5, 6]
[] [] [1, 2, 3, 4]
Traceback (most recent call last):
  File "main.py", line 16, in <module>
    print(flatten(deep))
          ~~~~~~~^^^^^^
  File "main.py", line 5, in flatten
    flat.extend(flatten(x))      # a box: open it the same way
                ~~~~~~~^^^
  File "main.py", line 5, in flatten
    flat.extend(flatten(x))      # a box: open it the same way
                ~~~~~~~^^^
  File "main.py", line 5, in flatten
    flat.extend(flatten(x))      # a box: open it the same way
                ~~~~~~~^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

The gift box comes out perfectly. An empty list, a box holding an empty box, and four levels deep all work. flat.extend(other) adds every item of other to the end of flat (unlike append, which would add the whole list as one item).

Why the deep one crashes: every call to flatten that is still waiting for an inner call to finish sits on the call stack: Python's list of function calls in progress. Each level of nesting is one more call waiting. Python stops at about 1,000 calls waiting at once; that's its recursion limit, and 5,000 boxes need 5,000 calls. Python raises RecursionError instead of running out of memory. (sys.getrecursionlimit() prints 1000.)

You could raise the limit with sys.setrecursionlimit(10_000), but that only moves the wall, and a very deep stack can crash the Python process itself. The interview answer: keep your own pile of things to open.

Walking through the recursion

Adding an indent per level shows each call opening one box and handing its sweets back up:

def flatten(items, depth=0):
    pad = "    " * depth
    print(f"{pad}flatten({items})")
    flat = []
    for x in items:
        if isinstance(x, list):
            flat.extend(flatten(x, depth + 1))
        else:
            flat.append(x)
    print(f"{pad}-> {flat}")
    return flat

flatten([[1, 2], [3, [4, 5]], 6])

Output:

flatten([[1, 2], [3, [4, 5]], 6])
    flatten([1, 2])
    -> [1, 2]
    flatten([3, [4, 5]])
        flatten([4, 5])
        -> [4, 5]
    -> [3, 4, 5]
-> [1, 2, 3, 4, 5, 6]

The outer call opens [1, 2], then [3, [4, 5]], which itself opens [4, 5]. At the deepest point three calls are waiting at once: the depth of the list. That's why depth, not size, is what hits the recursion limit.

  • Time O(n), where n counts the sweets and the boxes: each one is looked at once. (Strictly, extend copies each inner result up one level, so very deep lists cost more; the stack version below avoids that.) Space O(d) for the waiting calls, where d is the depth, plus O(n) for the result.

Fix 2: your own stack

Real-life example: unpacking by hand. Everything goes in a pile on the table, and you always take the top thing. If it's a sweet, keep it. If it's a box, tip its contents back onto the pile. No function calls waiting, just one pile.

A stack is exactly that pile: the last thing you put on is the first you take off (LIFO, last in, first out). In Python it's a plain list: append puts on top, pop() takes off the top (the last item).

The one subtle part: tip a box's contents on in reverse, so the box's first item ends up on top and comes off first. That keeps the order.

def flatten(items):
    flat = []
    stack = list(reversed(items))        # a pile: the next thing on top
    while stack:
        x = stack.pop()                  # take the top thing
        if isinstance(x, list):
            stack.extend(reversed(x))    # a box: tip it onto the pile
        else:
            flat.append(x)
    return flat

print(flatten([[1, 2], [3, [4, 5]], 6]))
print(flatten([]), flatten([[[]]]), flatten([1, [2, [3, [4]]]]))

deep = [7]
for _ in range(5_000):
    deep = [deep]
print(flatten(deep))

Output:

[1, 2, 3, 4, 5, 6]
[] [] [1, 2, 3, 4]
[7]

Same answers, in the same order, and the 5,000 boxes give [7] with no error. while stack: keeps going while the list is not empty (an empty list counts as false). reversed(x) gives the items of x from last to first.

Walking through the stack

def flatten(items):
    flat = []
    stack = list(reversed(items))
    while stack:
        x = stack.pop()
        print(f"pop {x!s:<14} stack={stack}")
        if isinstance(x, list):
            stack.extend(reversed(x))
        else:
            flat.append(x)
    return flat

print(flatten([[1, 2], [3, [4, 5]], 6]))

Output:

pop [1, 2]         stack=[6, [3, [4, 5]]]
pop 1              stack=[6, [3, [4, 5]], 2]
pop 2              stack=[6, [3, [4, 5]]]
pop [3, [4, 5]]    stack=[6]
pop 3              stack=[6, [4, 5]]
pop [4, 5]         stack=[6]
pop 4              stack=[6, 5]
pop 5              stack=[6]
pop 6              stack=[]
[1, 2, 3, 4, 5, 6]

(The stack is printed after the pop. The top of the pile is the right end of the list.)

Popped Box or sweet? Action Pile after (top on the right) flat
[1, 2] box tip 2, 1 on [6, [3, [4, 5]], 2, 1] []
1 sweet keep [6, [3, [4, 5]], 2] [1]
2 sweet keep [6, [3, [4, 5]]] [1, 2]
[3, [4, 5]] box tip [4, 5], 3 on [6, [4, 5], 3] [1, 2]
3 sweet keep [6, [4, 5]] [1, 2, 3]
[4, 5] box tip 5, 4 on [6, 5, 4] [1, 2, 3]
4, 5, 6 sweets keep [] [1, 2, 3, 4, 5, 6]

Forget reversed when tipping a box (stack.extend(x)), and the same input comes out as [2, 1, 5, 4, 3, 6]: each box's last item lands on top and comes off first.

  • Time O(n): every item and box is pushed once and popped once. Space O(n): the stack holds at most the items still waiting. No recursion, so no depth limit.

Tuples, and why not "anything iterable"

isinstance(x, list) only opens lists. If tuples should be opened too, pass a tuple of types: isinstance(x, (list, tuple)). With that change, [1, (2, 3), [4, ("five", [6])]] flattens to [1, 2, 3, 4, 'five', 6], and strings stay whole.

Don't be tempted to open "anything you can loop over" (hasattr(x, "__iter__")): a string is iterable, and each of its characters is a string of length 1, which contains itself. flatten(["hi"]) then never reaches a base case and ends in RecursionError: maximum recursion depth exceeded. List the container types you mean.

Q2: Split a list into chunks

Real-life example: a teacher has 7 students and wants project groups of 3. Three, three, and one. The last group is short, but Meera still gets a group. The teacher would never leave Meera out. Our first program will.

A chunk is a small piece of a fixed size. Chunking a list means cutting it into consecutive pieces of that size; only the last piece may be shorter.

Input (items, size) Output
7 students, 3 [['Asha', 'Ravi', 'Neha'], ['Kabir', 'Priya', 'Arjun'], ['Meera']]
[1, 2, 3, 4], 2 [[1, 2], [3, 4]]
[1, 2], 5 (size bigger than the list) [[1, 2]]
[], 3 []
anything, 0 a clear ValueError

Ask the interviewer: should a short last chunk be kept, dropped, or padded with a filler value? Lists or tuples as chunks? What should happen with size 0 or a negative size? Is the input a list (which can be sliced) or any iterable, like a file or a generator?

Attempt 1: count the groups with //

How many groups? Seven, floor divided by three. // is floor division: divide and round down to a whole number. For each group number g, slice from g * 3, three students. A slice items[a:b] is a new list of the items from index a up to, but not including, b.

students = ["Asha", "Ravi", "Neha", "Kabir", "Priya", "Arjun", "Meera"]

groups = []
for g in range(len(students) // 3):          # how many groups of 3?
    groups.append(students[g * 3 : g * 3 + 3])
print(groups)

Output:

[['Asha', 'Ravi', 'Neha'], ['Kabir', 'Priya', 'Arjun']]

Why it's wrong: two groups of three, and Meera is gone. No error at all. 7 // 3 is 2: floor division throws away the remainder (7 % 3, the 1 left over), and the remainder is exactly the students in the short group. You'd need to round up instead (a trick like -(-7 // 3)), which gets fiddly (7 // 3 is 2, 7 % 3 is 1, -(-7 // 3) is 3).

The fix: let range count the start positions

range(start, stop, step) counts from start, adding step each time, stopping before stop. So range(0, len(items), size) gives the start of every chunk: 0, 3, 6. Slice from i to i + size.

import itertools

students = ["Asha", "Ravi", "Neha", "Kabir", "Priya", "Arjun", "Meera"]

def chunks(items, size):
    return [items[i : i + size] for i in range(0, len(items), size)]

print(*chunks(students, 3), sep="\n")            # one group per line
print(chunks([1, 2, 3, 4], 2), chunks([1, 2], 5), chunks([], 3))
print(*itertools.batched(students, 3), sep="\n")  # Python 3.12+: tuples
print(chunks(students, 0))

Output:

['Asha', 'Ravi', 'Neha']
['Kabir', 'Priya', 'Arjun']
['Meera']
[[1, 2], [3, 4]] [[1, 2]] []
('Asha', 'Ravi', 'Neha')
('Kabir', 'Priya', 'Arjun')
('Meera',)
Traceback (most recent call last):
  File "main.py", line 11, in <module>
    print(chunks(students, 0))
          ~~~~~~^^^^^^^^^^^^^
  File "main.py", line 6, in chunks
    return [items[i : i + size] for i in range(0, len(items), size)]
                                         ~~~~~^^^^^^^^^^^^^^^^^^^^^
ValueError: range() arg 3 must not be zero

Three groups, and Meera is in the last one. Four items in pairs, a size bigger than the list, and an empty list all work.

Why it never crashes at the end: the last start is 6, and the slice students[6:9] asks for items 6, 7 and 8, but there is only item 6. A slice that runs past the end just stops at the end. Even students[9:12] is just []. Indexing past the end is different: students[9] raises IndexError: list index out of range.

itertools.batched(items, n), new in Python 3.12, does the same job and gives tuples. It works on any iterable, not just lists, and it is lazy: it hands out one batch at a time instead of building them all at once, which is why we unpack it with * to print them. print(*groups, sep="\n") unpacks a list into separate arguments and prints each on its own line. On 3.13, batched(items, 3, strict=True) refuses a short last batch with ValueError: batched(): incomplete batch.

And size 0: ValueError: range() arg 3 must not be zero. A step of zero would loop forever (0, 0, 0, ...), so Python refuses. A ValueError means "the type is fine, but this value isn't allowed".

The guard: fail early, with a clear message

That message talks about range and "arg 3", not about chunks, which confuses whoever calls our function. So check the size first and raise a clear error of your own. A check like this at the top of a function is called a guard.

def chunks(items, size):
    if size < 1:
        raise ValueError("size must be at least 1")
    return [items[i : i + size] for i in range(0, len(items), size)]

print(chunks(list(range(1, 11)), 4))
try:
    chunks([1, 2, 3], 0)
except ValueError as e:
    print("error:", e)

Output:

[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10]]
error: size must be at least 1

Ten numbers in fours: four, four, and two. And a clear message for size zero. size < 1 also catches negative sizes, which would otherwise give an empty list with no warning. try/except ValueError as e catches the error so the program can print it and carry on.

Walking through the starts

chunks(students, 3), seven students:

i (from range(0, 7, 3)) Slice Result
0 students[0:3] ['Asha', 'Ravi', 'Neha']
3 students[3:6] ['Kabir', 'Priya', 'Arjun']
6 students[6:9] (stops at 7) ['Meera']
9 (not produced: 9 ≥ 7) loop ends
  • Time O(n): every item is copied into exactly one chunk. Space O(n) for the chunks. itertools.batched uses O(size) at a time if you process each batch and throw it away.

Q3: Group by a key

Real-life example: a courier office has a pile of parcels, each with a name and a city. They need one bag per city. When a parcel for a new city comes along, they open a new bag.

In Python that's a dictionary (a store of key → value pairs with fast lookup): the key is the city, and the value is the list of names. The key decides which bag a parcel goes in. Each order is a tuple (name, city): a fixed-size group of values in brackets.

Input (orders) Output
[("Asha", "Pune"), ("Ravi", "Delhi"), ("Neha", "Pune"), ("Kabir", "Goa"), ("Meera", "Delhi")] {'Pune': ['Asha', 'Neha'], 'Delhi': ['Ravi', 'Meera'], 'Goa': ['Kabir']}
[] {}

Ask the interviewer: should the groups be in order of first appearance, or sorted by key? Should the items inside a group keep their original order? What do you return: a dict of lists, or a list of (key, group) pairs? Is the data already sorted by the key?

Attempt 1: append to a plain dict

orders = [("Asha", "Pune"), ("Ravi", "Delhi"), ("Neha", "Pune"),
          ("Kabir", "Goa"), ("Meera", "Delhi")]

by_city = {}
for name, city in orders:
    by_city[city].append(name)
print(by_city)

Output:

Traceback (most recent call last):
  File "main.py", line 6, in <module>
    by_city[city].append(name)
    ~~~~~~~^^^^^^
KeyError: 'Pune'

Why it crashes: the very first parcel. There's no Pune bag yet. Reading a missing key from a plain dictionary raises KeyError, and append needs the list to exist first. The courier opens a new bag; we have to as well. (for name, city in orders unpacks each tuple into two names.)

The fixes: if city not in, then defaultdict(list)

Fix one: if the city isn't in the dictionary yet, start it with an empty list, then append. Fix two: a defaultdict, from the collections module, is a dict that, when a key is missing, calls a factory you give it to make a starting value. defaultdict(list) calls list(), which makes an empty list: a new bag on demand.

from collections import defaultdict

orders = [("Asha", "Pune"), ("Ravi", "Delhi"), ("Neha", "Pune"),
          ("Kabir", "Goa"), ("Meera", "Delhi")]

by_city = {}
for name, city in orders:
    if city not in by_city:
        by_city[city] = []                   # first parcel: a new bag
    by_city[city].append(name)
print(by_city)

grouped = defaultdict(list)                  # a missing key starts as list()
for name, city in orders:
    grouped[city].append(name)
print(dict(grouped))
print(grouped["Agra"], len(grouped))         # careful: reading a key creates it

Output:

{'Pune': ['Asha', 'Neha'], 'Delhi': ['Ravi', 'Meera'], 'Goa': ['Kabir']}
{'Pune': ['Asha', 'Neha'], 'Delhi': ['Ravi', 'Meera'], 'Goa': ['Kabir']}
[] 4

Both give the same groups: Pune has Asha and Neha, Delhi has Ravi and Meera, and Goa has Kabir. Dicts keep keys in the order they were first added, so the cities come out in order of first appearance, and the names inside each bag keep the order of the orders.

The gotcha: reading creates the key. Look at the last line. Just reading grouped["Agra"] gave an empty list, and now there are four cities. With a defaultdict, even looking at a missing key creates it. To check without creating, use in or .get(): on the three-city dict, "Agra" in grouped is False and grouped.get("Agra") is None, and len(grouped) stays 3.

d.setdefault(key, []).append(name) is a third way on a plain dict: it returns d[key], first setting it to [] if it was missing. Before returning a defaultdict, turn it into a plain dict with dict(grouped), so callers don't create keys by accident.

  • Time O(n): one pass, and each dict lookup is O(1) on average. Space O(n) for the groups.

Attempt 3: itertools.groupby on unsorted data

The standard library also has groupby, in itertools. It takes a key function (a function that, given one item, returns the value to group by; here one that returns the city) and gives each key with its group of items.

from itertools import groupby

orders = [("Asha", "Pune"), ("Ravi", "Delhi"), ("Neha", "Pune"),
          ("Kabir", "Goa"), ("Meera", "Delhi")]

def city(order):
    return order[1]

for c, group in groupby(orders, key=city):
    print(c, [name for name, _ in group])

Output:

Pune ['Asha']
Delhi ['Ravi']
Pune ['Neha']
Goa ['Kabir']
Delhi ['Meera']

Why it's wrong: Pune, then Delhi, then Pune again, Goa, and Delhi again. Five groups for three cities. groupby only groups items that sit next to each other. Every time the key changes, it starts a new group; it never looks back. Think of a queue at a counter: the clerk starts a new group whenever the next person is from a different city than the one before. (_ is the usual name for a value you don't need.)

The fix: sort by the same key first

from itertools import groupby

orders = [("Asha", "Pune"), ("Ravi", "Delhi"), ("Neha", "Pune"),
          ("Kabir", "Goa"), ("Meera", "Delhi")]

def city(order):
    return order[1]

for c, group in groupby(sorted(orders, key=city), key=city):
    print(c, [name for name, _ in group])

Output:

Delhi ['Ravi', 'Meera']
Goa ['Kabir']
Pune ['Asha', 'Neha']

Three groups, now in alphabetical order. sorted(orders, key=city) puts every city's parcels together. Sort by the same key you group by, or the neighbours still won't match. Python's sort is stable (items with equal keys keep their original order), so Ravi still comes before Meera.

But sorting costs O(n log n); the defaultdict needs no sorting: O(n). Use groupby when the data is already sorted (log lines by date, rows from a database ORDER BY), or when you want the groups in key order.

One more groupby trap: each group is used up

Each group is an iterator: an object that hands out items one at a time and can only be walked through once. It is also tied to the main groupby: as soon as you move to the next key, the previous group is used up.

Save the (key, group) pairs in a list first and call list(g) on them afterwards, and on Pune, Delhi, Pune you get [('Pune', []), ('Delhi', []), ('Pune', [])]: every saved group is empty. Turn each group into a list inside the loop: {c: list(g) for c, g in groupby(...)}.

Common mistakes (and what you really see)

Mistake What you see Why Fix
[x for box in boxes for x in box] with a loose 6 TypeError: 'int' object is not iterable the inner for loops over a number recursion, or a stack
the same comprehension, or sum(boxes, []) [1, 2, 3, [4, 5], 6]: still boxed, no error fixed loops open a fixed depth recursion, or a stack
recursion on 5,000 levels RecursionError: maximum recursion depth exceeded the limit is 1,000 calls waiting your own stack
stack, but stack.extend(x) [2, 1, 5, 4, 3, 6]: order broken the box's last item ends up on top stack.extend(reversed(x))
opening anything with __iter__ RecursionError on ["hi"] a 1-letter string contains itself isinstance(x, (list, tuple))
range(len(items) // size) Meera left out, no error // drops the remainder range(0, len(items), size)
chunks(items, 0) ValueError: range() arg 3 must not be zero a zero step a guard: if size < 1: raise ValueError(...)
itertools.batched(items, 0) ValueError: n must be at least one batches of nothing check the size
items[len(items)] IndexError: list index out of range indexing past the end (slices don't raise) slice, or check the length
d[key].append(x) on a plain dict KeyError: 'Pune' no list yet if key not in d, setdefault, or defaultdict(list)
grouped["Agra"] on a defaultdict, just to look [], and len goes from 3 to 4 reading a missing key creates it "Agra" in grouped or grouped.get("Agra")
groupby(unsorted, key=...) Pune and Delhi twice groups neighbours only sorted(data, key=...) with the same key first
saving groupby's groups for later every group [] each group is a one-time iterator list(g) inside the loop

Your turn: depth of a nested list (solution)

Write a function that says how deep a nested list goes: how many boxes deep. [1, [2, [3, [4]]]] is 4 deep. A plain list like [1, 2] is 1 deep, and so is the empty list [] (it is still one box). Do it with recursion first, then with a stack that stores each box together with its depth.

Solution

Recursion: a list's depth is 1 (itself) plus the depth of its deepest inner list, or plus 0 if it has none. The base case is a list with no lists inside: the loop finds nothing, and it returns 1.

Stack: push (box, depth) pairs. The outer list is (items, 1). Pop a pair, remember the biggest depth seen, and push every inner list with depth + 1. Order doesn't matter here (we only want the maximum), so no reversed is needed. No recursion, so no depth limit.

def depth(items):
    deepest_inside = 0
    for x in items:
        if isinstance(x, list):
            deepest_inside = max(deepest_inside, depth(x))
    return 1 + deepest_inside        # this box, plus the deepest box inside it

def depth_stack(items):
    best = 0
    stack = [(items, 1)]             # (a box, how deep that box is)
    while stack:
        box, d = stack.pop()
        best = max(best, d)
        for x in box:
            if isinstance(x, list):
                stack.append((x, d + 1))
    return best

tests = [[1, [2, [3, [4]]]], [1, 2], [], [[[]]], [[1, 2], [3, [4, 5]], 6]]
for t in tests:
    print(t, "->", depth(t), depth_stack(t))

deep = [7]
for _ in range(5_000):
    deep = [deep]
print(depth_stack(deep))

Output:

[1, [2, [3, [4]]]] -> 4 4
[1, 2] -> 1 1
[] -> 1 1
[[[]]] -> 3 3
[[1, 2], [3, [4, 5]], 6] -> 3 3
5001

[[[]]] is 3 boxes deep even though it holds no sweets. The deep test is 5,001 (the starting [7] plus 5,000 wrappers), which depth would fail on with RecursionError, just like flatten. Both are O(n) time; the recursion uses O(d) call-stack space, the stack version up to O(n) list space.

Practice questions (with solutions)

1. Depth of a nested list. That's the "your turn" question above; try it before you open its solution.

2. Flatten a dict of dicts into 'a.b' keys. {"db": {"host": "localhost", "port": 5432}, "debug": True} → {'db.host': 'localhost', 'db.port': 5432, 'debug': True}. Config files often look like this.

Solution

The same shape as flatten: a value that is a dict is a box, so recurse into it with the key so far as a prefix; anything else is a sweet, stored under the full dotted key. An empty dict is kept as a value, or its key would vanish.

def flatten_dict(d, prefix=""):
    flat = {}
    for key, value in d.items():
        full = f"{prefix}.{key}" if prefix else key
        if isinstance(value, dict) and value:
            flat.update(flatten_dict(value, full))   # a dict inside: go deeper
        else:
            flat[full] = value
    return flat

config = {"db": {"host": "localhost", "port": 5432},
          "debug": True,
          "app": {"name": "shop", "theme": {"color": "blue"}}}
print(flatten_dict(config))
print(flatten_dict({}), flatten_dict({"a": {}}))

Output:

{'db.host': 'localhost', 'db.port': 5432, 'debug': True, 'app.name': 'shop', 'app.theme.color': 'blue'}
{} {'a': {}}

O(n) over all keys at all levels (plus building the key strings). d.items() gives (key, value) pairs; flat.update(other) copies every pair of other into flat. For very deep configs, the stack trick works here too: push (prefix, dict) pairs.

3. Chunks that overlap by one (a sliding window). Size 2 over ["Mon", "Tue", "Wed", "Thu", "Fri"] → [['Mon', 'Tue'], ['Tue', 'Wed'], ['Wed', 'Thu'], ['Thu', 'Fri']]. Useful for "compare each day with the next".

Solution

A sliding window is a chunk that moves forward one item at a time instead of a whole size. So the start goes up by 1, and the last start is len(items) - size (the last place a full window fits), hence range(len(items) - size + 1). Windows are always full, so a list shorter than the size gives none.

def windows(items, size):
    if size < 1:
        raise ValueError("size must be at least 1")
    return [items[i : i + size] for i in range(len(items) - size + 1)]

days = ["Mon", "Tue", "Wed", "Thu", "Fri"]
print(windows(days, 2))
print(windows([1, 2, 3, 4, 5], 3))
print(windows([1, 2], 5), windows([], 2))

import itertools
print(list(itertools.pairwise(days)))

Output:

[['Mon', 'Tue'], ['Tue', 'Wed'], ['Wed', 'Thu'], ['Thu', 'Fri']]
[[1, 2, 3], [2, 3, 4], [3, 4, 5]]
[] []
[('Mon', 'Tue'), ('Tue', 'Wed'), ('Wed', 'Thu'), ('Thu', 'Fri')]

range with a negative stop (2 - 5 + 1 = -2) is simply empty, so no special case is needed. Time O(n × size), since each window is a copy. For windows of exactly 2, itertools.pairwise (Python 3.10+) does it lazily, as tuples.

4. Group words by their first letter. ["apple", "banana", "avocado", "cherry", "blueberry", "Apricot"] → {'a': ['apple', 'avocado', 'Apricot'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}.

Solution

Q3 again, with the key w[0].lower() (the first letter, made lowercase so "Apricot" joins "apple"). The defaultdict is O(n); the groupby version must sort by the same key first, O(n log n).

from collections import defaultdict
from itertools import groupby

words = ["apple", "banana", "avocado", "cherry", "blueberry", "Apricot"]

by_letter = defaultdict(list)
for w in words:
    by_letter[w[0].lower()].append(w)
print(dict(by_letter))

def first(w):
    return w[0].lower()

print({k: list(g) for k, g in groupby(sorted(words, key=first), key=first)})
print(dict(by_letter).get("z", []))

Output:

{'a': ['apple', 'avocado', 'Apricot'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}
{'a': ['apple', 'avocado', 'Apricot'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}
[]

.get("z", []) returns the default without adding a key. Watch out for an empty string in the list: ""[0] raises IndexError: string index out of range, so skip empty words (if w:) if they can appear.

Quick quiz

What does this print?

from itertools import groupby
word = "aabccca"
print([k for k, g in groupby(word)])

(A) ['a', 'b', 'c'] (B) ['a', 'b', 'c', 'a'] (C) ['a', 'a', 'b', 'c', 'c', 'c', 'a'] (D) TypeError

Answer

(B). groupby starts a new group every time the value changes: aa, b, ccc, a. The last 'a' is not next to the first ones, so it is a new group. With no key function, the item itself is the key.

['a', 'b', 'c', 'a']

Interview questions

  1. Why can't a comprehension flatten a list of unknown depth? Its number of fors is fixed when you write it, so it opens a fixed number of levels. On loose items it also crashes with TypeError: 'int' object is not iterable.
  2. How do you flatten any depth? Recursion: for each item, if isinstance(x, list) flatten it and extend, else append. O(n) time.
  3. What's the base case, and what limits recursion in Python? The base case is a non-list item, where no further call is made. Every waiting call sits on the call stack, and Python's default recursion limit is 1,000, so deeper nesting raises RecursionError: maximum recursion depth exceeded.
  4. How do you avoid the recursion limit? Use your own stack (a list): pop the top item; if it's a list, push its contents reversed so the order is kept; else append it. O(n) time, O(n) space, no depth limit. Raising sys.setrecursionlimit only moves the wall.
  5. Split a list into chunks of size k? [items[i:i + k] for i in range(0, len(items), k)], or itertools.batched(items, k) on Python 3.12+ (tuples, any iterable). Slices stop at the end, so the short last chunk is kept. Guard against k < 1, which would give ValueError: range() arg 3 must not be zero.
  6. What's wrong with range(len(items) // k)? Floor division drops the remainder, so the short last chunk silently disappears.
  7. Group items by a key in O(n)? defaultdict(list) and d[key].append(item) in one pass (or if key not in d: d[key] = [], or setdefault). Reading a missing key on a defaultdict creates it; check with in or .get().
  8. When does itertools.groupby give wrong groups? When the input isn't sorted by the same key: it only groups neighbours. Sort first (O(n log n)), or use a dict (O(n)). Its groups are one-time iterators, so call list(g) inside the loop.

Glossary

Term Meaning Example
Nested list A list that has other lists inside it [[1, 2], [3, [4, 5]], 6]
Flatten Turn a nested list into one plain list, in order → [1, 2, 3, 4, 5, 6]
Depth How many boxes deep a nested list goes [1, [2, [3, [4]]]] is 4
Comprehension Build a new list from a loop in one expression [x for box in boxes for x in box]
Iterable Something a for loop can walk through lists, strings, ranges (not an int)
TypeError Raised when a value is the wrong type for the operation 'int' object is not iterable
isinstance(x, T) True if x is of type T (or one of a tuple of types) isinstance(x, (list, tuple))
extend vs append extend adds every item of a list; append adds one item flat.extend([4, 5])
Recursion A function that calls itself on a smaller piece flatten(x) inside flatten
Base case The case where a recursive function stops calling itself a non-list item: just append it
Call stack Python's list of function calls still in progress one call per level of nesting
Recursion limit The most calls that may wait at once (default 1,000) sys.getrecursionlimit() → 1000
RecursionError Raised when the recursion limit is exceeded maximum recursion depth exceeded
Stack A pile where the last thing put on is the first taken off stack.append(x), stack.pop()
LIFO Last in, first out: how a stack behaves the top of the pile
reversed(x) The items of x from last to first keeps the order on a stack
Chunk A consecutive piece of a fixed size; only the last may be shorter ['Meera']
Floor division // Divide and round down, dropping the remainder 7 // 3 → 2
Remainder % What's left over after floor division 7 % 3 → 1
range(start, stop, step) Counts from start by step, stopping before stop range(0, 7, 3) → 0, 3, 6
Slice A new list from index a up to (not including) b; stops at the end students[6:9] → ['Meera']
IndexError Raised when indexing past the end of a list students[9]
ValueError Raised when a value of the right type isn't allowed range() arg 3 must not be zero
Guard A check at the top of a function that rejects bad input early if size < 1: raise ...
Iterator An object that hands out items one at a time, only once each groupby group
Lazy Produces items only when asked, not all at once itertools.batched
itertools.batched Chunks any iterable into tuples (Python 3.12+) batched(students, 3)
Sliding window A chunk that moves forward one item at a time itertools.pairwise
Dictionary (dict) Key → value store with fast lookup {'Pune': ['Asha']}
Key The value that decides which group an item goes in the city
Tuple A fixed-size group of values in brackets ("Asha", "Pune")
Unpacking Splitting a tuple into separate names for name, city in orders
KeyError Raised when reading a missing key from a plain dict KeyError: 'Pune'
setdefault Returns d[k], first setting it to a default if missing d.setdefault(c, []).append(n)
defaultdict A dict that creates a missing key's value with a factory defaultdict(list)
Factory A function called to make a new starting value list → []
.get(k, default) Read a key without error and without creating it grouped.get("Agra") → None
Key function A function that, given an item, returns what to sort or group by def city(order): return order[1]
itertools.groupby Groups neighbouring items with the same key needs sorted input
Stable sort Items with equal keys keep their original order Ravi stays before Meera
O(n), O(n log n) Time grows like n, or like n × log n (sorting) dict grouping; sort + groupby

Summary

  • Flatten: a comprehension (or sum(boxes, [])) opens a fixed number of levels and crashes on loose items with TypeError: 'int' object is not iterable. Recursion with isinstance(x, list) opens any depth in O(n), but each level is one call waiting, and past 1,000 you get RecursionError. Your own stack (pop the top, tip boxes back on reversed) has no depth limit: O(n) time and space.
  • Chunks: range(len(items) // size) silently drops the short last chunk. range(0, len(items), size) with slices keeps it, because slices stop at the end. itertools.batched (3.12+) does the same as tuples. Guard against size 0 (ValueError: range() arg 3 must not be zero) with a clear error of your own. O(n).
  • Group by: appending to a missing key raises KeyError. Check with if key not in, use setdefault, or use defaultdict(list), in O(n); remember that reading a missing key on a defaultdict creates it. itertools.groupby only groups neighbours, so sort by the same key first, O(n log n).

Next episode: String questions I: reversing a string with [::-1], checking a palindrome while ignoring case and punctuation, and counting vowels.