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,
extendcopies 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.batcheduses 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
- 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 withTypeError: 'int' object is not iterable. - How do you flatten any depth? Recursion: for each item, if
isinstance(x, list)flatten it andextend, elseappend. O(n) time. - 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. - 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.setrecursionlimitonly moves the wall. - Split a list into chunks of size k?
[items[i:i + k] for i in range(0, len(items), k)], oritertools.batched(items, k)on Python 3.12+ (tuples, any iterable). Slices stop at the end, so the short last chunk is kept. Guard againstk < 1, which would giveValueError: range() arg 3 must not be zero. - What's wrong with
range(len(items) // k)? Floor division drops the remainder, so the short last chunk silently disappears. - Group items by a key in O(n)?
defaultdict(list)andd[key].append(item)in one pass (orif key not in d: d[key] = [], orsetdefault). Reading a missing key on a defaultdict creates it; check withinor.get(). - When does
itertools.groupbygive 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 calllist(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 withTypeError: 'int' object is not iterable. Recursion withisinstance(x, list)opens any depth in O(n), but each level is one call waiting, and past 1,000 you getRecursionError. 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 withif key not in, usesetdefault, or usedefaultdict(list), in O(n); remember that reading a missing key on a defaultdict creates it.itertools.groupbyonly 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.