These are the notes for Python Coding Questions, episode 9, the fifth round of list questions. Three questions: merging two sorted lists into one (and a bug that silently drops numbers), the intersection and union of two lists when items repeat (where sets quietly throw the repeats away and collections.Counter saves the day), and the classic maximum subarray sum, solved with Kadane's algorithm, including the trap when every number is negative. Along the way you'll meet two pointers, the stable merge, the difference between x in list and x in set, and how to go from O(n³) to O(n).
Every program was run with Python 3.13 (python3 main.py), the SyntaxPilot compiler's Python command. Every output below is real; timings depend on the machine (and even on the run), so they are approximate: compare them, don't copy them.
Q1: Merge two sorted lists
Real-life example: a teacher has two piles of answer sheets, one from section A (marks 45, 62, 88) and one from section B (50, 70, 91, 97). Each pile is already sorted, lowest on top. She needs one merit list. She doesn't shuffle everything and start again: she compares the two top sheets, takes the smaller one, and repeats. When one pile runs out, whatever is left in the other pile goes on the end, as it is.
| Input (a, b) | Output |
|---|---|
[45, 62, 88], [50, 70, 91, 97] |
[45, 50, 62, 70, 88, 91, 97] |
[], [3, 5] |
[3, 5] (one list empty) |
[1, 1], [1] |
[1, 1, 1] (repeats are kept) |
[7], [] |
[7] |
Ask the interviewer: are both lists sorted in the same direction (smallest first)? Should repeats be kept? (Usually yes: a merge keeps everything.) Can a list be empty? Should I return a new list, or change one of them? Can I use sorted(), or do you want it done by hand?
Attempt 1: join and sort
a = [45, 62, 88] # section A, sorted
b = [50, 70, 91, 97] # section B, sorted
print(sorted(a + b))
Output:
[45, 50, 62, 70, 88, 91, 97]
Why it's not the answer they want: it is correct. But a + b makes one long list and sorted() sorts it from scratch, which costs O((n + m) log(n + m)), where n and m are the two lengths. It ignores the one fact the question gives you: the lists are already sorted. In an interview the follow-up is always "use that, do it in one pass". (In real code sorted(a + b) is fine, and Python's sort is actually very quick on two sorted runs; the interview is testing whether you can write the merge.)
Attempt 2: two pointers, but forgetting the leftovers
Two pointers means two index variables walking through the data at the same time. Here i points into a and j points into b. While both lists still have items, compare a[i] with b[j], append the smaller one, and move that pointer forward.
def merge(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
return result
print(merge([45, 62, 88], [50, 70, 91, 97]))
Output:
[45, 50, 62, 70, 88]
Why it's wrong: 91 and 97 are gone. No error, just two students missing from the merit list. The while condition says "while both lists have items", so the loop stops as soon as either list runs out. Section A ran out after 88, and the loop ended while section B still had two sheets. That's exactly the step the teacher didn't forget.
The fix: extend with the leftovers
After the loop, add what's left of both lists. A slice like a[i:] is "everything from position i to the end", which is everything not used yet. At most one of the two slices has anything in it, and it is already sorted, so it can go on the end as it is. list.extend() adds every item of another list to the end.
def merge(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result.extend(a[i:]) # leftovers of a
result.extend(b[j:]) # leftovers of b
return result
print(merge([45, 62, 88], [50, 70, 91, 97]))
print(merge([], [3, 5]), merge([1, 1], [1]), merge([7], []))
Output:
[45, 50, 62, 70, 88, 91, 97]
[3, 5] [1, 1, 1] [7]
All seven students in order. An empty list gives back the other one (the loop never runs, and the leftovers are the whole other list). And [1, 1] with [1] gives three ones: repeats are kept.
- Time O(n + m): every item is looked at once. Space O(n + m) for the result list.
Walking through the merge
Adding a print at every comparison:
def merge(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
take = "a" if a[i] <= b[j] else "b"
print(f"i={i} j={j} compare {a[i]} vs {b[j]} -> take {take}")
if take == "a":
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
print(f"loop ends: i={i} j={j}, leftovers a[i:]={a[i:]} b[j:]={b[j:]}")
result.extend(a[i:])
result.extend(b[j:])
return result
print(merge([45, 62, 88], [50, 70, 91, 97]))
Output:
i=0 j=0 compare 45 vs 50 -> take a
i=1 j=0 compare 62 vs 50 -> take b
i=1 j=1 compare 62 vs 70 -> take a
i=2 j=1 compare 88 vs 70 -> take b
i=2 j=2 compare 88 vs 91 -> take a
loop ends: i=3 j=2, leftovers a[i:]=[] b[j:]=[91, 97]
[45, 50, 62, 70, 88, 91, 97]
| Step | i | j | a[i] vs b[j] | Take | result after |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 45 vs 50 | 45 (from a) | [45] |
| 2 | 1 | 0 | 62 vs 50 | 50 (from b) | [45, 50] |
| 3 | 1 | 1 | 62 vs 70 | 62 (from a) | [45, 50, 62] |
| 4 | 2 | 1 | 88 vs 70 | 70 (from b) | [45, 50, 62, 70] |
| 5 | 2 | 2 | 88 vs 91 | 88 (from a) | [45, 50, 62, 70, 88] |
| end | 3 | 2 | a is empty | extend [91, 97] |
[45, 50, 62, 70, 88, 91, 97] |
At step 5, i becomes 3 = len(a), so the loop stops. Attempt 2 returned right here.
Why <= and not <: a stable merge
On a tie (a[i] == b[j]), <= takes from a first. That keeps equal items in their original order: everything from the first list before equal items from the second. A merge (or a sort) that keeps equal items in their original order is called stable. It matters when the items carry more than the value you compare, like a name with the marks:
def merge_by_marks(a, b, stable=True):
result = []
i = j = 0
while i < len(a) and j < len(b):
take_a = a[i][1] <= b[j][1] if stable else a[i][1] < b[j][1]
if take_a:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result.extend(a[i:])
result.extend(b[j:])
return result
section_a = [("Asha", 62), ("Ravi", 88)]
section_b = [("Neha", 62), ("Kabir", 91)]
print(merge_by_marks(section_a, section_b)) # <=
print(merge_by_marks(section_a, section_b, stable=False)) # <
Output:
[('Asha', 62), ('Neha', 62), ('Ravi', 88), ('Kabir', 91)]
[('Neha', 62), ('Asha', 62), ('Ravi', 88), ('Kabir', 91)]
Asha and Neha both have 62. With <=, Asha (section A) stays first; with <, Neha jumps ahead. The stable merge is the heart of merge sort, which we write in episode 22.
In real code: heapq.merge
The standard library's heapq.merge merges any number of sorted inputs. It is lazy: it gives back an iterator that produces the next item only when asked, so wrap it in list() to see everything.
import heapq
a = [45, 62, 88]
b = [50, 70, 91, 97]
merged = heapq.merge(a, b)
print(merged)
print(list(merged))
print(list(heapq.merge([1, 4], [2, 5, 9], [3])))
Output (the hex address changes every run):
<generator object merge at 0x7fe8f28def80>
[45, 50, 62, 70, 88, 91, 97]
[1, 2, 3, 4, 5, 9]
Interviewers want to see the two pointers first; mention heapq.merge afterwards.
Q2: Intersection and union, with repeats
Real-life example: two roommates each write a shopping list. The intersection is what's on both lists (buy it once, together). The union is everything either of them needs. But my list says eggs three times: I need three dozen. Your list says eggs twice. Those repeats change the answer.
mine = ["milk", "eggs", "eggs", "bread", "eggs"]
yours = ["eggs", "eggs", "rice", "milk"]
| Question | Expected output |
|---|---|
| Intersection, repeats counted (shared items) | ['milk', 'eggs', 'eggs']: two eggs, because you only have two |
| Union, repeats counted (bigger count wins) | ['milk', 'eggs', 'eggs', 'eggs', 'bread', 'rice'] |
| Union, each item once, in first-seen order | ['milk', 'eggs', 'bread', 'rice'] |
| Just "which items are on both?" | milk, eggs (any order) |
Ask the interviewer: do repeats matter, or is it a yes/no question per item? Does the order of the result matter? If an item is in my list three times and yours twice, how many in the answer? (For an intersection, usually the smaller count: 2.) Are the lists sorted? (If yes, see practice question 2.)
Attempt 1: sets with & and |
A set is a collection that holds each item once and has no order. & gives the items in both sets (the intersection), | the items in either (the union).
mine = ["milk", "eggs", "eggs", "bread", "eggs"]
yours = ["eggs", "eggs", "rice", "milk"]
print(set(mine) & set(yours)) # in both lists
print(set(mine) | set(yours)) # in either list
Output, from two runs of the same program (a set's order is not fixed, so yours may differ):
{'eggs', 'milk'}
{'eggs', 'rice', 'milk', 'bread'}
{'milk', 'eggs'}
{'bread', 'rice', 'eggs', 'milk'}
Why it's wrong (for this question): for a yes/no question ("is milk on both lists?") it's perfect. But eggs are counted once: my three and your two are both gone. And the order changes between runs, because Python mixes a random number into string hashes each time it starts (this is called hash randomization). So if the question says keep the duplicates or keep the order, a set is the wrong tool. Sets also can't be indexed: set(...)[0] is a TypeError (see Common mistakes).
Attempt 2: keep x if x is in the other list
mine = ["milk", "eggs", "eggs", "bread", "eggs"]
yours = ["eggs", "eggs", "rice", "milk"]
common = [x for x in mine if x in yours]
print(common)
Output:
['milk', 'eggs', 'eggs', 'eggs']
Why it's wrong: three eggs, but you only have two, so we can only share two. The check x in yours never uses anything up: your two eggs match my first egg, my second egg, and my third egg too.
And it's slow: in on a list vs a set
x in some_list is a scan: Python compares x with each item from the start until it finds it. That's O(m) for a list of length m, so the whole comprehension is O(n·m). x in some_set is a hash lookup: Python computes the item's hash (a number worked out from its value) and jumps straight to where it would be stored, with no scanning. That's O(1) on average.
import time
a = list(range(0, 40_000, 2))
b = list(range(0, 40_000, 3))
start = time.perf_counter()
slow = [x for x in a if x in b] # 'in' on a list: a scan
print(len(slow), f"list: {time.perf_counter() - start:.3f} s")
start = time.perf_counter()
b_set = set(b)
fast = [x for x in a if x in b_set] # 'in' on a set: a hash lookup
print(len(fast), f"set: {time.perf_counter() - start:.4f} s")
Output (one run; timings vary by machine and run):
6667 list: 1.207 s
6667 set: 0.0010 s
a has 20,000 even numbers and b has 13,334 multiples of 3. Same answer both times (6,667 multiples of 6), but the list version took about a second and the set version about a thousandth of a second, roughly a thousand times faster, even counting the time to build the set.
The fix: count what's still unmatched with Counter
Counter, from the collections module, is a dictionary that maps each item to how many times it appears. A missing item counts as 0 instead of raising KeyError. A Counter is a multiset: a set that remembers how many copies of each item it holds. Printed, Counter(mine) is Counter({'eggs': 3, 'milk': 1, 'bread': 1}) (most common first) and Counter(yours)["bread"] is 0.
On two Counters, & keeps the smaller count of each item and drops items that are only on one side: Counter(mine) & Counter(yours) is Counter({'eggs': 2, 'milk': 1}). | keeps the larger count: Counter({'eggs': 3, 'milk': 1, 'bread': 1, 'rice': 1}).
Now the full answer. left is a Counter of your list: how many of each item you still have unmatched. Walk my list; if left[x] is above zero, keep x and use one up.
from collections import Counter
mine = ["milk", "eggs", "eggs", "bread", "eggs"]
yours = ["eggs", "eggs", "rice", "milk"]
def intersect(a, b):
left = Counter(b) # how many of each are still unmatched
common = []
for x in a:
if left[x] > 0:
common.append(x)
left[x] -= 1
return common
print(intersect(mine, yours))
print(list((Counter(mine) & Counter(yours)).elements())) # min of the counts
print(list((Counter(mine) | Counter(yours)).elements())) # max of the counts
print(list(dict.fromkeys(mine + yours))) # union, no repeats, in order
Output:
['milk', 'eggs', 'eggs']
['milk', 'eggs', 'eggs']
['milk', 'eggs', 'eggs', 'eggs', 'bread', 'rice']
['milk', 'eggs', 'bread', 'rice']
intersectgives milk and two eggs, in the order of my list..elements()repeats each item by its count, soCounter & Counterturned back into a list gives the same intersection. Its order is the order items were first added to the Counter, not sorted.Counter | Countergives the union with repeats: milk, three eggs, bread, rice.dict.fromkeys(mine + yours)makes a dictionary whose keys are the items. A dictionary keeps keys in the order they were first added, and each key only once, solist(...)of it is an ordered union without repeats. We met it in episode 6.
Complexity: building the Counter is O(m), the walk is O(n), and every left[x] lookup is O(1) on average: O(n + m) time, O(m) extra space (the Counter).
Walking through the Counter
intersect(mine, yours), one item of mine at a time (left starts as {'eggs': 2, 'rice': 1, 'milk': 1}):
| x (from mine) | left[x] before | Action | left[x] after |
|---|---|---|---|
| milk | 1 | keep | 0 |
| eggs | 2 | keep | 1 |
| eggs | 1 | keep | 0 |
| bread | 0 (not in yours) | skip | 0 |
| eggs | 0 | skip: no eggs left to share | 0 |
The rule: only a yes/no question per item? Use sets. Repeats matter? Use a Counter. Order matters too? Walk the list and let the Counter decide, like intersect.
Q3: Maximum subarray sum (Kadane's algorithm)
Real-life example: a chai stall writes down its profit every day, in hundreds of rupees: −2, 3, 5, −4, 6, −9, 2. Some days are losses. The owner wants to show an investor the best run of consecutive days. A subarray is a block of neighbouring items with no gaps (not any selection: you can't skip the −4). Here the best block is 3, 5, −4, 6 = 10. The −4 is worth keeping because 6 comes after it.
| Input (profit per day) | Output | Best block |
|---|---|---|
[-2, 3, 5, -4, 6, -9, 2] |
10 |
[3, 5, -4, 6] |
[-3, -1, -7] (every day a loss) |
-1 |
[-1] |
[4] |
4 |
[4] |
[1, 2, 3] (every day a profit) |
6 |
the whole list |
Ask the interviewer: must the block have at least one day? (Usually yes; then the all-negative answer is the largest single number, −1. Some versions allow an empty block and answer 0.) Do you want the sum, or also which days? (See practice question 3.) Can the list be empty?
Attempt 1: brute force over every block
Brute force means trying every possibility. Try every start day i and every end day j, add the days from i to j with sum(), keep the best. random.seed(1) makes the "random" year the same on every run.
import time, random
def best_streak(days):
best = days[0]
for i in range(len(days)):
for j in range(i, len(days)):
total = sum(days[i:j + 1]) # profit from day i to day j
best = max(best, total)
return best
print(best_streak([-2, 3, 5, -4, 6, -9, 2])) # profit per day
random.seed(1)
year = [random.randint(-500, 500) for _ in range(1_000)]
start = time.perf_counter()
print(best_streak(year), f"{time.perf_counter() - start:.2f} s")
Output (one run; the time varies):
10
12719 1.42 s
Why it's slow: there are about n²/2 blocks, and sum(days[i:j + 1]) adds each block up from scratch, another O(n) each time. So O(n³) time. 1,000 days (almost three years) took over a second. Ten times more days means about a thousand times longer.
A middle step, O(n²): keep a running total for each start day, total += days[j], instead of re-summing the block every time. That removes one loop's worth of work and is much faster, but still O(n²): a million days would take hours. There's a much better idea.
Kadane's idea: extend the run, or start fresh
Walk the days once and keep one number, current: the best total of a run that ends today. Each new day p there are only two choices: extend the run so far (current + p), or start fresh today (p). Pick the bigger one: current = max(p, current + p). If the run so far is below zero, it can only drag today down, so starting fresh wins. Also keep best, the biggest current ever seen. This one-pass method is called Kadane's algorithm (after Jay Kadane, who found it in 1984).
Attempt 2: Kadane starting at zero
A version you'll see a lot online starts best and current at 0 and resets current to 0 whenever it goes negative:
def best_streak(days):
best = 0
current = 0
for p in days:
current = max(0, current + p) # a losing run? start over
best = max(best, current)
return best
print(best_streak([-2, 3, 5, -4, 6, -9, 2]))
print(best_streak([-3, -1, -7])) # a monsoon week: every day a loss
Output:
10
0
Why it's wrong: 10 is right, but the monsoon week says 0, and no block of days made 0. The best you can do is −1, the single day with the smallest loss. Starting at 0 quietly allows an empty block (no days at all), which adds up to 0. The question needs at least one day. Some interviewers accept 0; most expect −1. Ask, and handle it.
The fix: start at the first day
Start best and current at days[0], and walk from the second day. current is the bigger of today alone and the run plus today.
import time, random
def best_streak(days):
best = current = days[0]
for p in days[1:]:
current = max(p, current + p) # extend the run, or start fresh here
best = max(best, current)
return best
for days in [[-2, 3, 5, -4, 6, -9, 2], [-3, -1, -7], [4], [1, 2, 3]]:
print(days, "->", best_streak(days))
random.seed(1)
year = [random.randint(-500, 500) for _ in range(1_000)]
start = time.perf_counter()
print(best_streak(year), f"{time.perf_counter() - start:.5f} s")
big = [random.randint(-500, 500) for _ in range(1_000_000)]
start = time.perf_counter()
print(best_streak(big), f"{time.perf_counter() - start:.2f} s")
Output (one run; timings vary):
[-2, 3, 5, -4, 6, -9, 2] -> 10
[-3, -1, -7] -> -1
[4] -> 4
[1, 2, 3] -> 6
12719 0.00014 s
300947 0.09 s
10 for the week, −1 for the monsoon, 4 for a single day, 6 when every day is a profit. The 1,000 days give 12719, the same as the brute force, in a fraction of a millisecond instead of over a second. And a million days take about a tenth of a second; the O(n³) brute force would take years.
- Time O(n) (one pass), space O(1) (two variables). (Strictly,
days[1:]makes a copy, which is O(n) memory; loop overrange(1, len(days))if that matters.) - An empty list raises
IndexErrorondays[0](see Common mistakes): decide what an empty input should return and check for it first.
Kadane step by step
best_streak([-2, 3, 5, -4, 6, -9, 2]), one day at a time:
| Day | p | current + p | Choice | current | best |
|---|---|---|---|---|---|
| 0 | −2 | (start) | start | −2 | −2 |
| 1 | 3 | 1 | fresh (3 > 1) | 3 | 3 |
| 2 | 5 | 8 | extend | 8 | 8 |
| 3 | −4 | 4 | extend (still positive) | 4 | 8 |
| 4 | 6 | 10 | extend | 10 | 10 |
| 5 | −9 | 1 | extend | 1 | 10 |
| 6 | 2 | 3 | extend | 3 | 10 |
On day 1, the run so far was −2, below zero, so starting fresh won. On day 3 the run dropped to 4 but stayed positive, so it was worth carrying into day 4.
Common mistakes (and what you really see)
Every message in the "What you see" column was copied from a real run (the 0x... addresses change every run).
| Mistake | What you see | Why | Fix |
|---|---|---|---|
while i < len(a) and j < len(b) with nothing after it |
[45, 50, 62, 70, 88]: 91 and 97 lost, no error |
the loop stops when either list ends | result.extend(a[i:]) and result.extend(b[j:]) |
sorted(a + b) in the interview |
correct, but "they're already sorted" | ignores the input; O((n+m) log(n+m)) | two pointers, O(n + m) |
< instead of <= in the merge |
equal items from b jump ahead of a's |
not stable | a[i] <= b[j] |
print(heapq.merge(a, b)) |
<generator object merge at 0x...> |
it's lazy, an iterator | list(heapq.merge(a, b)) |
merged = a.extend(b) |
merged is None |
extend changes a and returns None |
call a.extend(b), then use a |
set(a) & set(b) when repeats matter |
{'eggs', 'milk'}: eggs once, order differs between runs |
a set keeps each item once, no order | Counter(a) & Counter(b) |
set(...)[0] |
TypeError: 'set' object is not subscriptable |
sets have no positions | list(...), or sorted(...) first |
[x for x in a if x in b] |
3 eggs (one too many), and ~1 s for 20,000 × 13,334 items (varies) | nothing used up; in on a list is O(m), so O(n·m) |
a Counter of what's left |
Counter(a) & set(b) |
TypeError: unsupported operand type(s) for &: 'Counter' and 'set' |
& needs two Counters (or two sets) |
Counter(a) & Counter(b) |
print((c1 & c2).elements()) |
<itertools.chain object at 0x...> |
elements() is an iterator |
list((c1 & c2).elements()) |
best = 0 in Kadane |
[-3, -1, -7] → 0 |
allows an empty block | best = current = days[0] |
best_streak([]) with days[0] |
IndexError: list index out of range |
an empty list has no first day | check if not days: first |
sum(days[i:j + 1]) in two loops |
~1.4 s for 1,000 days (varies) | O(n³) | Kadane, O(n) |
Your turn: merge k sorted lists (solution)
Not two lists: any number of sorted lists. Three sections: [[1, 4], [2, 5, 9], [3]] → [1, 2, 3, 4, 5, 9].
Solution
Let k be the number of lists and N the total number of items.
The tempting way: merge them one by one into a growing result (result = merge(result, lst) for each list). It's correct, but the result gets longer every time and is copied again in every merge: about O(N·k) time.
Pairwise merge (two at a time, like a knockout tournament): merge list 0 with 1, 2 with 3, and so on; that halves the number of lists. Repeat until one is left. Each round touches every item once (O(N)), and there are about log₂ k rounds: O(N log k) time, O(N) space. It reuses today's merge exactly.
Heap: a heap (Python's heapq module) is a list arranged so the smallest item is always at position 0; heappush and heappop each cost O(log size). Put the first item of every list in the heap, as a tuple (value, which list, index). Pop the smallest, append it, and push the next item from the same list. The heap never holds more than k items, so each pop/push is O(log k): O(N log k) time, O(k) extra space besides the result. It's the teacher with k piles, always taking the smallest top sheet. The list number in the tuple also breaks ties, so Python never has to compare anything else.
import heapq
def merge(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result.extend(a[i:])
result.extend(b[j:])
return result
def merge_k_pairwise(lists):
"""Merge the lists two at a time, like a knockout tournament."""
if not lists:
return []
while len(lists) > 1:
paired = []
for k in range(0, len(lists), 2):
if k + 1 < len(lists):
paired.append(merge(lists[k], lists[k + 1]))
else:
paired.append(lists[k]) # odd one out waits a round
lists = paired
return lists[0]
def merge_k_heap(lists):
"""Always take the smallest 'top sheet' from a heap."""
heap = []
for which, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], which, 0)) # (value, which list, index)
result = []
while heap:
value, which, idx = heapq.heappop(heap)
result.append(value)
if idx + 1 < len(lists[which]):
heapq.heappush(heap, (lists[which][idx + 1], which, idx + 1))
return result
tests = [[[1, 4], [2, 5, 9], [3]], [], [[], [2], []], [[1, 1], [1], [0, 5]]]
for lists in tests:
print(lists, "->", merge_k_pairwise(lists), merge_k_heap(lists), list(heapq.merge(*lists)))
Output:
[[1, 4], [2, 5, 9], [3]] -> [1, 2, 3, 4, 5, 9] [1, 2, 3, 4, 5, 9] [1, 2, 3, 4, 5, 9]
[] -> [] [] []
[[], [2], []] -> [2] [2] [2]
[[1, 1], [1], [0, 5]] -> [0, 1, 1, 1, 5] [0, 1, 1, 1, 5] [0, 1, 1, 1, 5]
All three agree on every test, including no lists, empty lists and repeats. heapq.merge(*lists) does the heap approach for you (*lists passes each list as a separate argument). On a bigger test (500 sorted lists of 1,000 random numbers each), both were correct and the heap was roughly twice as fast as pairwise merging, about 0.35 s against 0.9 s on our machine (timings vary), because pairwise merging builds a whole new list every round.
Practice questions (with solutions)
1. Merge k sorted lists. [[1, 4], [2, 5, 9], [3]] → [1, 2, 3, 4, 5, 9]. Why is merging them one by one into a growing result slow?
Solution
The full code (pairwise and heap) is in "Your turn" above. One by one, result = merge(result, lst) for each list: with k lists of about N/k items, the i-th merge copies about i·N/k items, so the total is about N·k/2, which is O(N·k). With 500 lists that is about 250 times the work of one pass over the data. Pairwise merging and the heap are both O(N log k) (with 500 lists, log₂ 500 is about 9). In real code it's one line:
import heapq
lists = [[1, 4], [2, 5, 9], [3]]
print(list(heapq.merge(*lists)))
Output:
[1, 2, 3, 4, 5, 9]
2. Intersection of two sorted lists with two pointers, keeping repeats. [1, 2, 2, 3, 5] and [2, 2, 2, 5, 7] → [2, 2, 5].
Solution
Like the merge, but you only keep matches. If the two items are equal, keep one and move both pointers (each side uses one up, which handles repeats exactly like the Counter). Otherwise move the pointer at the smaller item: it's too small to appear in the other list.
def intersect_sorted(a, b):
i = j = 0
common = []
while i < len(a) and j < len(b):
if a[i] == b[j]:
common.append(a[i]) # a match: use one from each side
i += 1
j += 1
elif a[i] < b[j]:
i += 1 # a[i] is too small to be in b
else:
j += 1 # b[j] is too small to be in a
return common
print(intersect_sorted([1, 2, 2, 3, 5], [2, 2, 2, 5, 7]))
print(intersect_sorted([1, 3], [2, 4]), intersect_sorted([], [1]), intersect_sorted([4, 4], [4]))
Output:
[2, 2, 5]
[] [] [4]
O(n + m) time, O(1) extra space (besides the answer): no Counter needed, because the sorted order does the matching. Here leftovers are not added: once one list ends, nothing else can match.
3. Return the days of the best streak. For [-2, 3, 5, -4, 6, -9, 2], return the sum and the start and end indices: 10, (1, 4).
Solution
Kadane, plus three indices. When you start fresh, remember today as the start of the current run. When current beats best, save that start and today as the best run's ends.
def best_streak_days(days):
best = current = days[0]
start = best_start = best_end = 0
for d in range(1, len(days)):
p = days[d]
if p > current + p: # starting fresh is better
current = p
start = d # a new run begins today
else:
current += p
if current > best:
best = current
best_start, best_end = start, d
return best, best_start, best_end
for days in [[-2, 3, 5, -4, 6, -9, 2], [-3, -1, -7], [4], [1, 2, 3]]:
best, s, e = best_streak_days(days)
print(days, "->", best, (s, e), days[s:e + 1])
Output:
[-2, 3, 5, -4, 6, -9, 2] -> 10 (1, 4) [3, 5, -4, 6]
[-3, -1, -7] -> -1 (1, 1) [-1]
[4] -> 4 (0, 0) [4]
[1, 2, 3] -> 6 (0, 2) [1, 2, 3]
Still O(n) time, O(1) space. p > current + p is the same as current < 0. Using > (not >=) in current > best keeps the first best run if two tie.
4. Maximum product subarray. The biggest product of a block of neighbours. [2, 3, -2, 4] → 6 (2 × 3); [-2, 3, -4] → 24 (the whole list).
Solution
Copying Kadane with * fails: a negative times a negative is positive, so the most negative product so far can become the biggest one day later. Keep two numbers: hi, the biggest product ending here, and lo, the smallest. Each day, the new hi and lo come from three candidates: start fresh (x), hi * x, or lo * x.
def max_product_wrong(nums):
best = current = nums[0]
for x in nums[1:]:
current = max(x, current * x) # Kadane copied as is
best = max(best, current)
return best
def max_product(nums):
best = hi = lo = nums[0] # hi: biggest product ending here, lo: smallest
for x in nums[1:]:
candidates = (x, hi * x, lo * x)
hi, lo = max(candidates), min(candidates)
best = max(best, hi)
return best
for nums in [[2, 3, -2, 4], [-2, 3, -4], [-2, 0, -1], [-3], [0, 2]]:
print(nums, "->", max_product_wrong(nums), max_product(nums))
Output (first number: copied Kadane; second: the fix):
[2, 3, -2, 4] -> 6 6
[-2, 3, -4] -> 3 24
[-2, 0, -1] -> 0 0
[-3] -> -3 -3
[0, 2] -> 2 2
The copied version says 3 for [-2, 3, -4]; the real answer is 24. hi, lo = max(...), min(...) updates both from the old values at once (both right-hand sides are worked out before either name changes). A 0 resets both, which is correct: any block through a 0 has product 0. O(n) time, O(1) space.
Quick quiz
What does this print?
from collections import Counter
a = [1, 1, 2, 3, 3, 3]
b = [1, 3, 3, 4]
print(sorted((Counter(a) & Counter(b)).elements()))
(A) [1, 3] (B) [1, 3, 3] (C) [1, 1, 3, 3, 3] (D) [1, 3, 3, 4]
Answer
(B). & keeps the smaller count of each item: 1 → min(2, 1) = 1, 3 → min(3, 2) = 2, and 2 and 4 are only in one list, so they drop out. elements() repeats each item by its count, and sorted puts them in order.
[1, 3, 3]
Interview questions
- How do you merge two sorted lists in O(n + m)? Two pointers: compare
a[i]andb[j], append the smaller, advance that pointer; after the loop,extendwitha[i:]andb[j:]. - What's the most common bug in that merge? Forgetting the leftovers. The loop stops when either list ends, so the tail of the other list is silently lost.
- Why
<=and not<? On a tie,<=takes from the first list, so equal items keep their original order: a stable merge, which merge sort relies on. - Intersection of two lists with repeats?
Counter(a) & Counter(b)(min of the counts), or walkawith a Counter ofband use one up per match to keepa's order. O(n + m). If both are sorted, two pointers in O(1) extra space. - Why is
[x for x in a if x in b]slow?inon a list scans: O(m) per check, O(n·m) total. Convertbto a set (O(1) average lookups), or use a Counter if repeats matter. - When is a set the right tool, and when not? For yes/no membership and de-duplication. Not when repeats or order matter: a set keeps each item once and has no fixed order.
- Explain Kadane's algorithm. Keep
current, the best sum of a run ending here:current = max(p, current + p)(extend or start fresh), andbest = max(best, current). O(n) time, O(1) space. - What if every number is negative? Starting at 0 returns 0 (an empty block). Start
bestandcurrentat the first item to return the largest single number. Ask whether an empty block is allowed. - How do you return which days? Record the start index whenever you start fresh, and save start and end whenever
bestimproves.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Sorted list | Items in order, smallest first (here) | [45, 62, 88] |
| Merge | Combine sorted lists into one sorted list | two piles → one merit list |
| Two pointers | Two index variables walking through data at the same time | i in a, j in b |
| Leftovers | The items still unused when one list runs out | b[j:] = [91, 97] |
Slice a[i:] |
A new list from position i to the end |
[45, 62, 88][1:] → [62, 88] |
list.extend(x) |
Adds every item of x to the end; returns None |
result.extend(b[j:]) |
list.append(x) |
Adds one item to the end | result.append(a[i]) |
| Stable merge / stable sort | Equal items keep their original order | <= takes from a on a tie |
| Merge sort | A sort that splits a list in halves and merges them back | episode 22 |
heapq.merge |
Standard-library lazy merge of any number of sorted inputs | list(heapq.merge(a, b)) |
| Lazy / iterator | Produces items one at a time, only when asked | <generator object merge ...> |
Heap (heapq) |
A list kept so the smallest item is always at index 0 | heappush, heappop |
| k-way merge | Merging k sorted lists at once | Your turn |
| Set | Collection with each item once and no fixed order | {'eggs', 'milk'} |
| Intersection | Items in both collections (&) |
milk, eggs |
| Union | Items in either collection (|) |
milk, eggs, bread, rice |
| Hash | A number computed from a value, used to find it fast | how sets and dicts store keys |
| Hash randomization | Python mixes a random value into string hashes each run, so set order changes | three runs, three orders |
| Hash lookup | Jumping straight to an item's slot by its hash, no scanning: O(1) average | x in b_set |
| Scan | Checking items one by one from the start: O(n) | x in some_list |
Counter |
A dict from item to how many times it appears; missing items give 0 | Counter(mine)["eggs"] → 3 |
| Multiset | A set that remembers how many copies of each item it holds | a Counter |
Counter & Counter |
Keeps the smaller count of each item | eggs: min(3, 2) = 2 |
Counter | Counter |
Keeps the larger count of each item | eggs: max(3, 2) = 3 |
.elements() |
Iterator repeating each item by its count | list(c.elements()) |
dict.fromkeys(seq) |
A dict with the items as keys, first-seen order, each once | ordered union |
| Subarray | A block of neighbouring items, no gaps | [3, 5, -4, 6] |
| Maximum subarray sum | The largest total of any non-empty subarray | 10 |
| Brute force | Try every possibility, no cleverness | every (i, j) block |
| Kadane's algorithm | One pass: current = max(p, current + p), best = max(best, current) |
O(n) |
| Empty block | A subarray with no items, sum 0; usually not allowed | why best = 0 gives 0 |
| Big-O | How the time or memory grows with the input size | O(n) |
| O(n + m) | Time grows with the two lengths added: each item once | the merge |
| O(n·m) | Every item of one list against every item of the other | x in list in a loop |
| O(N log k) | N items, each costing log k steps | heap merge of k lists |
| O(n²), O(n³) | Time grows like n × n, or n × n × n | running totals; re-summing every block |
| O(1) space | A fixed number of variables, whatever the input size | best, current |
IndexError |
Raised when an index is outside the list | [][0] |
TypeError |
Raised when an operation doesn't work on that type | set(...)[0] |
random.seed() |
Makes random numbers repeatable | random.seed(1) |
time.perf_counter() |
High-resolution stopwatch | timing the brute force |
Summary
- Merge two sorted lists:
sorted(a + b)works but ignores that the lists are sorted. Two pointers take the smaller item each step, in O(n + m); never forget the leftovers,extend(a[i:])andextend(b[j:]).<=makes it a stable merge. For k lists, merge pairwise or use a heap: O(N log k), orheapq.merge. - Intersection and union: sets are for yes/no questions; they drop repeats and have no fixed order.
x in listinside a loop never uses anything up and is O(n·m). A Counter of what's still unmatched gives the right repeats in O(n + m);Counter &is min of the counts,|is max;dict.fromkeys(a + b)is an ordered union without repeats. - Maximum subarray: brute force with
sum()is O(n³). Kadane keeps the best run ending today,current = max(p, current + p), in O(n) time and O(1) space. Start atdays[0], not 0, or an all-negative list wrongly gives 0.
Next episode: List questions VI: flattening a nested list (with recursion and with a stack), splitting a list into chunks, and grouping items by a key with defaultdict and groupby.