Concept 1 of 71 min
Shared references, copies and mutable defaults
2 names, 1 list
| a | [5, 6] |
|---|---|
| b | same list as a |
- b.append(7)
- a is now [5, 6, 7]
Assigning b to a copies the reference, so changing b changes a; a[:] makes a new list.
A grid built by multiplication
| grid | [[0] * 3] * 4 |
|---|
- Set grid[0][0] to 1
- All 4 rows now start with 1
The outer * repeats one inner list; a list comprehension builds separate rows.
Removing while looping
| List | [10, 20, 31] |
|---|---|
| Remove | even numbers |
- Removes 10; the loop then skips 20
- Result: [20, 31]
Build a new list instead of removing items while looping over it.
d2 = d does the same for a dictionary. += on a list changes it in place, and a tuple can hold a list that still changes. Multiplying a list that holds a list repeats the same inner list.
A default list is created once for all calls, and removing items while looping skips some. Most 'what does this print' questions test whether you see 2 names on 1 object.
A default argument is evaluated when the function is defined, so every call appends to the same list: use None and build the list inside. The outer multiplication copies references to the same row; a list comprehension creates new rows.
Removing from a list shifts it under the iterator, so the next item is skipped: build a new list instead.
C++ is the mirror image: a std::vector passed by value is copied, so the function changes the copy; pass a reference to change the original, or a const reference to avoid the copy.
- Thinking b = a makes a copy.
- Using a list as a default argument.
- Removing items from the list you are looping over.
A colleague's function keeps returning results from earlier calls. What is your first suspect in Python?
A complete answer covers
- A mutable default argument shared by every call.
- Or a module-level list or dict that is never reset.
- Fix it with None as the default and a new object inside.
- Write a test that calls the function twice.
Also in our technical interviews, on camera, with a score.
Concept 2 of 71 min
Closures, scope, generators and in-place methods
Lambdas made in a loop
| Loop | range(4) |
|---|---|
| Each lambda returns | k |
- Called after the loop: 3, 3, 3, 3
- Bound with lambda k=k: k: 0, 1, 2, 3
A plain closure reads k when called; a default argument freezes it when created.
A generator of squares, used twice
| Square of 0 | 0 |
|---|---|
| Square of 1 | 1 |
| Square of 2 | 4 |
| Square of 3 | 9 |
- First sum = 0 + 1 + 4 + 9 = 14
- Second sum: 0, the generator is used up
A generator keeps no copy; use a list to read the values twice.
sort() returns None
| x | [5, 9, 1].sort() |
|---|
- sort() sorts in place and returns None
- So x is None
Use sorted() when you need the sorted list back.
A generator is used up after one pass. A name assigned in a function is local and raises UnboundLocalError if read first. list.sort() returns None, while sorted() returns a new list.
The loop variable is shared by every lambda, and by the time they run the loop has finished. A generator yields values lazily and keeps no copy, so the second pass finds it empty; a list comprehension can be read many times.
Python decides at compile time that a name assigned inside a function is local, so a += 1 reads a local that has no value yet: pass it in and return it, or declare it global.
Methods that change an object in place return None, so x = x.sort() loses the list.
- Expecting each lambda to remember its own loop value.
- Reading a generator twice.
- Assigning the result of list.sort().
When would you choose a generator over a list in a data pipeline, and what is the catch?
A complete answer covers
- When the data is large: a generator holds one item at a time.
- It lets you chain steps lazily and stop early.
- The catch: it can be read only once and has no length.
- Turn it into a list when you need several passes.
Also in our technical interviews, on camera, with a score.
Concept 3 of 71 min
Numbers, slices and truthiness
Binary floats
| Sum | 0.1 + 0.2 |
|---|
- Result: 0.30000000000000004
Compare floats with a tolerance such as math.isclose, and use decimals for money.
Rounding halves
| Value A | 0.5 |
|---|---|
| Value B | 1.5 |
| Value C | 2.5 |
- Python's round() gives 0, 2 and 2
- Excel's ROUND gives 1, 2 and 3
Python rounds halves to the nearest even number, which avoids a bias upwards.
Slices exclude their end
| s | 'banking' |
|---|---|
| Slice | s[2:5] |
- Letters 2, 3 and 4: 'nki'
- Length = 5 − 2 = 3
Because the end is excluded, s[a:b] is exactly b − a long.
Binary floats make 0.1 + 0.2 differ from 0.3. round() sends halves to the nearest even number. A slice includes its start and excludes its end.
Empty containers are falsy, while a list holding 0 is truthy. Most decimals have no exact binary form, so compare floats with a tolerance such as math.isclose, and use decimals for money.
Rounding halves to even avoids a bias upwards over many roundings; Excel rounds halves away from 0.
Excluding the end makes s[a:b] exactly b − a long and lets s[:k] and s[k:] split a string cleanly. Truthiness tests emptiness, not content, so [0] is true and '' is false.
- Testing floats with ==.
- Expecting round() to send every half up.
- Counting the end position in a slice.
A pricing script sums thousands of small fees and the total is off by a fraction of a cent. What is going on and how do you fix it?
A complete answer covers
- Binary floats cannot store most decimals exactly.
- Errors add up over many operations.
- Use integer cents or the decimal module for money.
- Round only at the end, with an explicit rule.
Also in our technical interviews, on camera, with a score.
Concept 4 of 71 min
Counting loops and recursion
A doubling loop
| Counter | doubles from 1 |
|---|---|
| Stop | above 1,000,000 |
| 220 | 1,048,576 |
| Bigger input | 2,000,000 |
- It passes 1,000,000 after 20 doublings
- Doubling the input: 20 + 1 = 21 passes
The loop grows with log₂ n, not with n.
Naive Fibonacci against a cache
| fib(6), n of 5 | 8 |
|---|---|
| fib(9), n of 8 | 34 |
| fib(11), n of 10 | 89 |
| Calls | 2 × fib(n+1) − 1 |
- fib(5): 2 × 8 − 1 = 15 calls
- fib(8): 2 × 34 − 1 = 67 calls
- fib(10): 2 × 89 − 1 = 177 calls
A cache computes only 6, 9 and 11 values: naive calls grow like the Fibonacci numbers themselves.
- Naive recursion
- With a cache
A loop whose inner range grows with the outer one runs 1 + 2 + … + n times. A recursion that calls itself twice without a cache, like naive Fibonacci, grows exponentially until memoisation brings it to O(n).
Big O keeps the dominant term and drops constants, in Python as in any language. 2 nested loops are only O(n²) when the inner one runs about n times for each outer step; an inner loop that doubles its counter makes the whole O(n log n).
Naive Fibonacci recomputes the same values again and again, roughly φⁿ calls; caching each result, or a simple loop, computes each value once.
Off-by-one errors are the other classic: with f(0) at 0 and f(1) at 1, f(10) is 55 and f(11) is 89.
- Calling every pair of nested loops O(n²).
- Counting both loops as running fully when the inner one grows.
- Being off by one on the Fibonacci index.
An O(n²) step takes 1 second on 1,000 rows. Roughly how long on 100,000 rows?
What does O(n log n) mean, and why does it matter more than raw speed?
Your recursive function is correct but far too slow for large inputs. How do you speed it up?
A complete answer covers
- Check whether it solves the same subproblems again and again.
- If so, cache the results: memoisation, or functools.lru_cache.
- Or rewrite it bottom-up as a loop, which also avoids deep recursion.
- Give the new complexity and the memory it costs.
Also in our technical interviews, on camera, with a score.
Concept 5 of 71 min
Choosing the right data structure
A list or a set
| Values to check | 10,000 |
|---|---|
| Items in the list | 10,000 |
- List: 10,000 × 10,000 = 100,000,000
- Set: about 10,000 lookups
Converting the list to a set once turns 100 million comparisons into 10,000 lookups.
Two-sum in one pass
| Values | [8, 3, 11, 5] |
|---|---|
| Target | 16 |
- At 8: needs 16 − 8 = 8, not seen
- At 3: needs 16 − 3 = 13, not seen
- At 11: needs 16 − 11 = 5, not seen
- At 5: needs 16 − 5 = 11, seen
The pass returns 11 and 5 after reading each value once, in O(n).
Hash tables have an O(n) worst case when keys collide. A single pass with a hash map of seen values solves two-sum in O(n). collections.deque appends and pops at both ends in O(1).
Strings should be built with ''.join() over a list rather than += in a loop.
A list is scanned item by item; a hash table jumps to a bucket, which is why converting a list to a set once can turn an O(n²) loop into O(n).
Average O(1) depends on a good hash: if many keys land in the same bucket, a lookup scans them all.
For two-sum, check whether target − x is already in the map, then add x. list.pop(0) shifts every element, unlike a deque. Strings are immutable, so repeated += can copy the growing string each time, O(n²) at worst, while ''.join() is linear.
- Saying hash lookups are O(1) in the worst case.
- Using list.pop(0) as a queue.
- Building a long string with += in a loop.
You must check whether any two numbers in a list add up to a target. How do you avoid comparing every pair?
You need to remove duplicates from 10 million trade identifiers while keeping their order. How would you do it and at what cost?
A complete answer covers
- One pass, keeping a set of identifiers already seen.
- Append an identifier to the output only the first time.
- O(n) time on average and O(n) extra memory.
- dict.fromkeys also keeps order in modern Python.
Also in our technical interviews, on camera, with a score.
Concept 6 of 71 min
Searching, sorting and the top k
Merge sort against a quadratic sort
| Items | 106 |
|---|---|
| log₂ of 106 | about 20 |
- Merge sort ≈ 106 × 20 = 20,000,000
- Quadratic ≈ 106 × 106 = 1012
The quadratic sort does 50,000 times more work.
The top 10 with a heap
| Values | 106 |
|---|---|
| k | 10 |
| log₂ of 10 | about 3.3 |
- Heap ≈ 106 × 3.3 = 3,300,000 steps
Keeping only the best 10 in a small heap avoids sorting the whole list.
Merge sort takes O(n log n) time even in the worst case, with O(n) extra space. Heapsort sorts in place but is not stable.
The k largest of n values come from a min-heap of size k in O(n log k). When hi = lo + 1, mid equals lo; if lo = mid, nothing moves.
Python integers do not overflow, unlike (lo + hi) in C or Java. Merge sort always splits in halves but needs a buffer to merge.
A stable sort keeps equal items in their original order, which matters when sorting by several keys.
For the top k, the heap holds the current best k and each new value costs log k; scanning k times for the next maximum costs O(nk).
- Writing lo = mid in a binary search.
- Saying merge sort sorts in place.
- Sorting everything to get the top few.
You receive a stream of trades and must always know the 100 largest by size. How would you keep that list?
A complete answer covers
- A min-heap of size 100: its smallest is the bar to beat.
- Each new trade costs O(log 100), or nothing if it is smaller.
- Memory stays fixed at 100 items.
- Sorting everything each time would cost O(n log n).
Also in our technical interviews, on camera, with a score.
Concept 7 of 71 min
AdvancedWhy append is O(1) even though it copies
16 appends
| Appends | 16 |
|---|---|
| Capacity 1 | 1 |
| Capacity 2 | 2 |
| Capacity 3 | 4 |
| Capacity 4 | 8 |
| Capacity 5 | 16 |
- Doubling: copies = 1 + 2 + 4 + 8 = 15
- One slot at a time: copies = 15 × 16 ÷ 2 = 120
15 copies against 120; for 1,000,000 appends, fewer than 1,000,000 against about 500 billion.
It copies at most a constant times n elements over n appends. When the array is full, every element is copied into a bigger block, so the cost hides in the resizes.
Doubling makes those resizes rare: the copies add up to a series that stays below one copy per append.
Growing by a fixed number of slots makes them frequent, and the total copying grows with the square of the number of appends: quadratic, which is why Python lists and C++ vectors over-allocate geometrically.
A geometric growth factor smaller than 2, as some libraries use, still keeps the total linear, trading a little more copying for less unused memory.
Amortised O(1) is an average: one append can still cost O(n), which matters in latency-sensitive code, where reserving capacity in advance avoids the spike.
- Calling append O(n) because a resize copies the array.
- Growing a buffer by a fixed number of slots.
- Forgetting that amortised O(1) still allows a slow single append.
Appending to a Python list sometimes copies the whole list. Why is append still called O(1)?
A complete answer covers
- The list over-allocates, growing its capacity by a proportion when full.
- Copies then add up to a constant times the number of appends.
- So the cost per append is O(1) on average, amortised.
- A single append can still be O(n): reserve capacity when latency matters.
Also in our technical interviews, on camera, with a score.
Recap
- In Python a name points to an object: b = a shares it, a[:] or .copy() makes a new one, and a default list is created once.
- Closures read variables when called, generators run once, and assigning to a name inside a function makes it local.
- Floats are binary: 0.1 + 0.2 is not 0.3; round() sends halves to the even number; / always gives a float.
- Count loops by how fast the counter moves: doubling is log n, nested independent loops multiply.
- Sets and dicts look up in O(1) on average, O(n) at worst; lists scan in O(n); a heap gives the top k in O(n log k).
25 questions on Coding and algorithms
Timed, like the real one, drawn from a bank of 33. Every answer explained.