Python for DSA Interviews

**For:** JavaScript developers. Prepares for online assessments and technical interviews.
**Skips:** identical basics (loops, assignment, functions as values).
**Covers:** only syntax and built-ins that differ from JS or that DSA problems need.
**Version:** Python 3.9+. LeetCode and HackerRank run 3.10 or newer.
Click Solution under each exercise only after you try it.

1. Basic Syntax

Blocks and indentation

No braces. Indentation defines the block. Use 4 spaces.
A block header ends with :
No parentheses around conditions. No semicolons.
else if becomes elif.
pass = empty block.

Operators

Inline conditional (ternary)

Form: value_if_true if condition else value_if_false.
The condition is in the middle. JS puts it first: cond ? a : b.
It is an expression. It gives a value. Use it in return, assignments, arguments, f-strings, lambdas and comprehensions.
else is required.
Only the chosen branch runs.

Chained and nested ternary

Chain more branches by putting another ternary in the else part.
It reads left to right. Add parentheses for clarity.
More than 2 levels: use if / elif / else.

Ternary inside a comprehension

if after for = filter. Items are dropped. No else.
if / else before for = ternary. Every item is kept and changed.

One-line statements

A short body can go on the same line after the colon.
This is for statements (return, break, continue, print, a single assignment). It is not an expression.
No else needed. Use it for guard clauses.

Ternary vs and / or

cond and a or b looks like JS cond ? a : b. It is wrong when a is falsy (0, "", [], None).
Use the ternary.

Shorter than a ternary

is vs ==

== compares values.
is compares identity (same object in memory).
Use is only for None: if node is None.
Never use is for numbers or strings.

Truthiness

Biggest trap from JS: an empty list [] and empty dict {} are falsy in Python. In JS they are truthy.

Variables, swap, unpacking

No let, const, var. Just assign.
Python has function scope, no block scope. A variable made in a for or if stays visible after.

None, print, input

Exercises: Basic Syntax

Predict the output of each line.

Solution
Write sign(n) that returns -1, 0 or 1 using the ternary expression.

Solution
Swap lst[i] and lst[j] in one line.

Solution
Split [1, 2, 3, 4, 5] into head (first), middle (list of the three in the middle) and tail (last) in one line.

Solution
Rewrite with one inline conditional each.

Solution
Write grade(score) with a chained ternary: 90 and above gives "A", 80 and above "B", else "C".

Solution
Why is [x for x in nums if x > 0 else 0] a SyntaxError? Fix it so negatives become 0.

Solution

2. Loops

for loops: only for-in

No C-style for (let i = 0; i < n; i++).
for x in iterable gives the values. (JS for...of)
Python has no equivalent of JS for...in over indices. Use range.

range

range(stop), range(start, stop), range(start, stop, step).
stop is excluded.
range is lazy: no memory cost. x in range(...) is O(1).

enumerate: index and value

while, break, continue, for-else

No do...while. Use while True: with break.
for ... else: the else block runs if the loop did not hit break.

Iterating dict and other iterables

Grid and window patterns

Do not change a list while you loop over it

Exercises: Loops

Print every element of [4, 5, 6] with its index counting from 1: 1 4, 2 5, 3 6.

Solution
Given a list, print the difference between each element and the one before it. Use range.

Solution
Brute-force Two Sum: return the indices [i, j] with i < j and nums[i] + nums[j] == target, or [].

Solution
Count the cells with value 1 that have at least one neighbour (up, down, left, right) with value 1.

Solution
Use for ... else to return the first index of a list where the value is negative, or -1.

Solution

3. Functions

Define, call, return

def name(params): then an indented body.
No function keyword. No braces. No arrow syntax (see lambda below).
No return = the function returns None.
return a, b returns one tuple. Unpack it at the call.
A function must exist when it is called, not when it is defined. A function body can call a function defined later in the file.

Functions are values

A function is an object, like in JS. Assign it, store it, pass it, return it.
f = the function itself. f() = call it and get the result.
Forgetting the (), or adding them by mistake, is the most common bug when passing functions.

Pass a function to a function

Built-ins that take a function

Built-in	The function you pass
`sorted(x, key=f)`, `x.sort(key=f)`	item to sort key
`min(x, key=f)`, `max(x, key=f)`	item to compare key
`map(f, x)`	item to new item
`filter(f, x)`	item to True / False
`functools.reduce(f, x, init)`	(accumulator, item) to new accumulator
`defaultdict(f)`	no argument, returns the default value
`heapq.nlargest(k, x, key=f)`	item to key
`sorted(x, key=cmp_to_key(f))`	(a, b) to negative / 0 / positive

lambda

lambda args: expression. JS: (args) => expression.
Body = one expression. It is returned automatically. No return, no statements, no assignment, no loops.
A ternary a if c else b is an expression. It is allowed.
Use def when the body needs more than one expression, or when you need to name and reuse it.

Return a function: closures

An inner function remembers the variables of the outer function. That is a closure.
It remembers the variable, not the value at that time.

Late binding: closures read the variable when called, not when created. All lambdas below see the final i.

Existing functions you can pass

Dispatch table: dict of functions

functools.partial: pre-fill arguments

Arguments

positional: by order.
keyword: name=value, any order.
default: def f(a, b=10). Parameters with defaults go last.
*args: collects extra positional arguments into a tuple. (JS rest ...args)
**kwargs: collects extra keyword arguments into a dict.
f(*list) and f(**dict) at the call spread them out. (JS spread)

Mutable default argument trap

A default value is created once, when def runs. A default list or dict is shared by all calls. Use None and create the list inside.

Arguments are passed by object reference

The function gets a reference to the same object, like JS.
Mutating a list, dict or set in the function changes the caller's object.
Reassigning the parameter name only changes the local name.
int, str, tuple are immutable. The caller can never see a change.
lst += [x] on a list mutates it. lst = lst + [x] makes a new list.

Scope: local, nonlocal, global

Variables made in a function are local. Scope is the whole function, not a block.
An inner function can read outer variables.
To reassign an outer variable, declare nonlocal (or global for module level).
Changing a list or dict (append, d[k] = v) needs no declaration.
Assigning to a name anywhere in a function makes it local for the whole function. Reading it before the assignment raises UnboundLocalError.

Helper functions inside functions

Decorators

@d above a def means f = d(f).
A decorator is a function that takes a function and returns a function.
You will mostly use @cache and @lru_cache. Writing your own is rare.

Exercises: Functions

Predict the output.

Solution
Write apply_n(f, x, n): apply f to x, n times. apply_n(lambda v: v * 2, 1, 5) gives 32.

Solution
Sort [("al", 90), ("bo", 85), ("cy", 90)] by score descending, then name ascending. Pass a function defined with def as the key.

Solution
Write make_counter(). Each call of the returned function gives 1, 2, 3, ...

Solution
Write compose(f, g) that returns a function computing f(g(x)).

Solution
Evaluate Reverse Polish Notation with a dict of functions. Division truncates toward zero.

Solution
Make a list of 3 functions where the function at index i returns i.

Solution
Count the even numbers in a list with an inner function and nonlocal. (Practice only. sum is simpler.)

Solution
Reverse a list in place so that the caller sees the change. Why does a = a[::-1] fail?

Solution

4. Numbers and Booleans

int has no size limit

No overflow. No Number.MAX_SAFE_INTEGER. int grows as needed.
Interviews that need a 32-bit result: check the range by hand.
float("inf") is the "infinity" value for min/max initialisation.

Division, floor, modulo

Python // and % round toward negative infinity. JS % keeps the sign of the dividend. They differ for negative numbers.

round, floor, ceil, sqrt

Float precision

Converting types

min, max, sum

bool is an int

Exercises: Numbers and Booleans

Predict: -7 // 2, -7 % 3, int(-7 / 2), round(2.5), round(3.5), 2 ** -1, 10 / 5.

Solution
Reverse the digits of a signed integer. Return 0 if the result leaves the 32-bit signed range.

Solution
Given a and b, how many boxes of size b hold a items? No math import.

Solution
Count how many numbers in a list are both positive and even, in one expression.

Solution

5. Slicing [start:stop:step]

The rules

Syntax: seq[start:stop:step].
Works on str, list, tuple, range. Result has the same type as the input.
start: first index taken. Included.
stop: where to stop. Excluded.
step: jump size. Default 1. Negative = walk backward.
Every part is optional. Empty part = default.
Same idea as range(start, stop, step).
JS: arr.slice(start, end) has no step.

Index table (read this first)

Every item has two indexes: one from the front, one from the back.
Last item = -1. Second to last = -2.

start and stop only

Leave a part empty

No start: begin at the first item.
No stop: go to the end, including the last item.
[:] = everything.

Negative start and stop

Negative numbers count from the end. -n means len - n.
Last k items: [-k:].
Everything except the last k items: [:-k].

[-0:] is [0:], the whole list. If k can be 0, a[-k:] is a bug. Use a[len(a) - k:].

step

Positive step: walk forward, jump step indexes each time.
[::2] = every 2nd item, starting with the first.
[1::2] = every 2nd item, starting with the second.

Negative step: walk backward

Step -1 goes from right to left.
With a negative step the defaults flip:
- no start = the last item
- no stop = before the first item (first item is included)
So start must be larger than stop. Otherwise the result is empty.
Stop is still excluded.

Reverse from index i down to index 0, including 0: use s[i::-1]. s[i:0:-1] misses index 0. s[i:-1:-1] is empty, because -1 means the last index.

Out-of-range never raises

A slice clamps indexes to the valid range.
A single index outside the range raises IndexError.

Slice returns a new object

A list slice is a shallow copy. Cost: O(k) for k items.
Changing the slice does not change the original list.
Items inside are not copied. A nested list stays shared.
a[:], a.copy(), list(a) are all shallow copies.
A slice in a loop of size n can make the loop O(n^2). Use indexes for big inputs.

Slice assignment and delete (lists only)

A list slice on the left of = replaces that part.
The new part can have a different length. The list grows or shrinks.
With a step, the length must match exactly.
Strings and tuples are immutable. They do not allow this.

Slicing other types

Common recipes

Goal	Code
First k items	`a[:k]`
Last k items (k > 0)	`a[-k:]`
Drop the first	`a[1:]`
Drop the last	`a[:-1]`
Drop first and last	`a[1:-1]`
Reverse (copy)	`a[::-1]`
Copy	`a[:]`
Even positions / odd positions	`a[::2]` / `a[1::2]`
Left half / right half	`a[:len(a)//2]` / `a[len(a)//2:]`
Rotate left by k	`a[k:] + a[:k]`
Rotate right by k	`a[-k:] + a[:-k]` (use `k %= len(a)` first)
Window of size k at i	`a[i:i+k]`
Palindrome test	`s == s[::-1]`
Reverse the first k chars only	`s[:k][::-1] + s[k:]`
Insert x at index i (new list)	`a[:i] + [x] + a[i:]`
Remove index i (new list)	`a[:i] + a[i+1:]`

Slice objects (rare)

Exercises: Slicing

Predict each value.

Solution
Write last_k(a, k) that returns the last k items and works when k == 0.

Solution
Write the slice that returns "dcba" from "abcdef". Then the slice that returns "dcb".

Solution
Rotate a list left by k. Return a new list. Handle k larger than the length.

Solution
Split a list into chunks of size k. The last chunk can be shorter.

Solution
Reverse each word, keep the word order: "ab cd" gives "ba dc".

Solution
Reverse only the first k characters of a string: ("abcdef", 3) gives "cbadef".

Solution
Reverse a list in place in one line, without .reverse().

Solution
From a 2D grid, get the second column as a list.

Solution

6. Strings

Indexing and slicing

Strings are immutable. You cannot change a character.
No char type. s[0] is a string of length 1.
Slice syntax: s[start:stop:step]. stop is excluded. All three are optional.
Negative index counts from the end.
A slice never raises an error. A single index can.

JS to Python methods

JS	Python
`s.length`	`len(s)`
`s.charAt(i)`	`s[i]`
`s.substring(a, b)`	`s[a:b]`
`s.indexOf(x)` (-1 if missing)	`s.find(x)` (-1) or `s.index(x)` (raises ValueError)
`s.includes(x)`	`x in s`
`s.split("")`	`list(s)`
`s.split(",")`	`s.split(",")`
`arr.join(",")`	`",".join(arr)` (join lives on the separator; items must be str)
`s.trim()`	`s.strip()`
`s.toUpperCase()`	`s.upper()`
`s.startsWith(x)`	`s.startswith(x)`
`s.replaceAll(a, b)`	`s.replace(a, b)` (replaces ALL by default)
`s.repeat(3)`	`s * 3`
`s.charCodeAt(i)`	`ord(s[i])`
`String.fromCharCode(n)`	`chr(n)`
`s.padStart(5, "0")`	`s.zfill(5)` or `s.rjust(5, "0")`
`s.split("").reverse().join("")`	`s[::-1]`

split, join, strip

find, count, replace, startswith

Character tests

ord, chr, alphabet tricks

f-strings

Sequence operations on strings

A string is a sequence of characters. All shared sequence operations work.
A string is immutable. No assignment, no append, no del.
Difference from lists: in, index and count also accept a substring.

Building and converting

Two-pointer palindrome

Exercises: Strings

Valid palindrome: ignore case and non-alphanumeric characters.

Solution
Valid anagram: are a and b made of the same letters?

Solution
Return the index of the first non-repeating character, or -1.

Solution
Reverse the words of a sentence. Collapse extra spaces.

Solution
Caesar cipher: shift every lowercase letter by k (wrap around).

Solution
Longest common prefix of a list of strings.

Solution

7. Lists (Arrays)

JS array to Python list

JS	Python	Cost
`arr.length`	`len(lst)`	O(1)
`arr.push(x)`	`lst.append(x)`	O(1)
`arr.pop()`	`lst.pop()`	O(1)
`arr.shift()`	`lst.pop(0)` (use `deque` instead)	O(n)
`arr.unshift(x)`	`lst.insert(0, x)`	O(n)
`arr.includes(x)`	`x in lst`	O(n)
`arr.indexOf(x)`	`lst.index(x)` (raises if missing)	O(n)
`arr.slice(a, b)`	`lst[a:b]`	O(k)
`arr.concat(b)`, `[...a, ...b]`	`a + b`, `[a, b]`	O(n)
`arr.splice(i, 1)`	`lst.pop(i)` or `del lst[i]`	O(n)
`arr.reverse()`	`lst.reverse()` (in place) or `lst[::-1]` (copy)	O(n)
`arr.map(f)`	`[f(x) for x in lst]`
`arr.filter(f)`	`[x for x in lst if f(x)]`
`arr.reduce(f, init)`	`functools.reduce(f, lst, init)` or `sum`
`arr.some / every`	`any(...)` / `all(...)`
`arr.find(f)`	`next((x for x in lst if f(x)), None)`
`Array(n).fill(0)`	`[0] * n`
`arr.at(-1)`	`lst[-1]`
`arr.join(",")`	`",".join(map(str, lst))`

Operations shared by all sequences

Sequence = ordered items with an index: list, str, tuple, range.
These operations work the same on all of them.
Names: + is concatenation. * is repetition (it repeats references, a shallow copy).
Only list is mutable. See the next sub-topics for the changing operations.

Index and slice

Negative indexes never raise: a[i - 1] with i = 0 silently returns the last element. Guard the bounds yourself.

Add and remove

These change the list itself. str and tuple do not allow them.

Create, copy, 2D grids

[[0] * m] * n makes n references to the same row. Use a comprehension.

List comprehensions

Form: [expr for x in iterable if cond].
With if/else in the expression, the if/else goes before for.
Nested: write the loops in the same order as nested for statements.

map and filter: `[f(x) for x in lst]`

JS arr.map(f) = [f(x) for x in lst]. Transform every item.
JS arr.filter(f) = [x for x in lst if f(x)]. Keep items where f(x) is truthy.
Both together: [f(x) for x in lst if g(x)]. Filter first, then map.
f is any expression: a function call, a method, an operator, a ternary.

[x for x in lst if f(x) else 0] is a SyntaxError. A filter has no else. To keep every item, use the ternary form: [x if f(x) else 0 for x in lst].

Unpacking and built-in helpers

Matrix patterns

Exercises: Lists

Predict.

Solution
Move all zeros to the end in place. Keep the order of the others.

Solution
Rotate the list right by k.

Solution
Rotate an n x n matrix 90 degrees clockwise.

Solution
Product of array except self (no division).

Solution
Remove duplicates from a sorted list in place. Return the new length.

Solution

8. Tuples

What a tuple is

Tuple = immutable list. Written with ().
A tuple is hashable (if its items are). So it can be a dict key or set item.
A list is not hashable. JS has no equal.
Use tuples for coordinates, pairs, heap items and function results.

Sequence operations on tuples

Tuples as keys

Return several values

Exercises: Tuples

Why does {[1, 2]: "x"} fail? Fix it.

Solution
Given points [(1,2),(3,4),(1,2)] return the number of distinct points.

Solution
Write a function that returns both the sum and the product of a list.

Solution

9. Dictionary and Set

dict basics

dict = JS Map (not JS plain object). Keys can be any hashable value: int, str, tuple, bool, None.
Order = insertion order.
Missing key: d[k] raises KeyError. JS returns undefined.
k in d checks keys, O(1).

dict methods

Method	Does	JS
`d.get(k, default=None)`	value, or default if missing. No error	`map.get(k) ?? default`
`d.keys()`	view of keys	`map.keys()`
`d.values()`	view of values	`map.values()`
`d.items()`	view of `(key, value)` pairs	`map.entries()`
`d.update(other)`	merge. Overwrites existing keys	`Object.assign(o, other)`
`d.setdefault(k, default)`	return `d[k]`. If missing, set default first
`d.pop(k, default)`	remove `k`, return its value. `KeyError` if missing and no default
`d.popitem()`	remove and return the last inserted pair
`d.clear()`	remove all items	`map.clear()`
`d.copy()`	shallow copy	`{...o}`
`dict.fromkeys(keys, value=None)`	new dict. Every key gets the same value
`a \| b`, `a \|= b`	merge (Python 3.9+). New dict / in place	`{...a, ...b}`

Counting and grouping

Reading g[k] on a defaultdict creates the key. To test without creating, use k in g.

Sorting and searching a dict

Adding or removing keys while you loop over a dict raises RuntimeError. Loop over list(d) or list(d.items()).

Nested dict

OrderedDict for LRU

set basics

{} is an empty dict. Make an empty set with set().

set methods

Method	Does	JS
`s.add(x)`	add one item. No error if present	`set.add(x)`
`s.update(it)`	add all items of an iterable
`s.discard(x)`	remove `x`. No error if missing	`set.delete(x)`
`s.remove(x)`	remove `x`. `KeyError` if missing
`s.pop()`	remove and return an arbitrary item
`s.clear()`	remove all items	`set.clear()`
`s.copy()`	shallow copy	`new Set(s)`
`s.union(*its)`	new set with all items. Same as `\|`
`s.intersection(*its)`	new set with common items. Same as `&`
`s.difference(*its)`	new set, items not in the others. Same as `-`
`s.symmetric_difference(it)`	items in exactly one set. Same as `^`
`s.intersection_update(*its)`	in place `&=`
`s.difference_update(*its)`	in place `-=`
`s.symmetric_difference_update(it)`	in place `^=`
`s.issubset(it)`	all items of `s` are in `it`. Same as `<=`
`s.issuperset(it)`	`s` has all items of `it`. Same as `>=`
`s.isdisjoint(it)`	no common items

Set operations

Exercises: Dictionary and Set

Two Sum in O(n): return the indices of the two numbers that add to target.

Solution
Group anagrams: ["eat","tea","tan","ate","nat","bat"] to groups.

Solution
Longest consecutive sequence in O(n). Example [100,4,200,1,3,2] gives 4.

Solution
Top K frequent elements.

Solution
Intersection of two lists, unique values.

Solution
Predict: type({}), type({1}), d = {}; d.get("a"), Counter("aab")["z"].

Solution
Subarray sum equals K: count subarrays with sum k (prefix sum + dict).

Solution

10. Stack, Queue, Heap

Stack: use a list

Queue: use deque

from collections import deque.
All four end operations are O(1).
Never use list.pop(0) as a queue. It is O(n).

BFS template (grid)

Heap: heapq

heapq is a min-heap on a plain list. There is no max-heap.
Max-heap trick: store the negative value.
Peek = h[0]. Do not call sorted on the heap list; only h[0] is the minimum.

If two tuples tie on the first field, Python compares the next field. If that field is not comparable (a node object, a dict), you get TypeError. Add a unique counter: (priority, count, item).

Top-K and Dijkstra patterns

Exercises: Stack, Queue, Heap

Valid parentheses for ()[]{}.

Solution
Kth largest element in a list (heap of size k).

Solution
Daily temperatures: for each day, how many days until a warmer day (0 if none)?

Solution
Sliding window maximum with a deque.

Solution
Merge k sorted lists into one sorted list with a heap.

Solution
Implement a max-heap of numbers using heapq. Show push, peek, pop.

Solution

11. Sorting and Binary Search

sorted vs sort

sorted(x) works on any iterable and returns a new list.
lst.sort() sorts in place and returns None.
Sorts are stable. Time O(n log n).
Numbers sort numerically by default. JS sorts as strings.

key functions and multi-key sort

key takes one item and returns what to compare. It runs once per item.
Return a tuple to sort by several fields.
Negate a number to reverse one field.

Custom comparator: cmp_to_key

bisect: binary search built in

The list must be sorted. Cost O(log n).
bisect_left(a, x): first index where a[i] >= x (lower bound).
bisect_right(a, x): first index where a[i] > x (upper bound).

Binary search templates

(lo + hi) / 2 gives a float. a[2.5] raises TypeError. Always use //.

Other helpers

Exercises: Sorting and Binary Search

Sort words by frequency descending. Ties: alphabetical.

Solution
Merge overlapping intervals.

Solution
Search insert position in a sorted list (one line with bisect).

Solution
First and last position of x in a sorted list, or [-1, -1].

Solution
Largest number: arrange numbers to form the largest concatenation.

Solution
Koko eating bananas: the smallest speed k so that all piles finish within h hours.

Solution

12. Recursion

How recursion works

A recursive function calls itself on a smaller input.
Every recursive function needs a base case. It returns without a recursive call. Without it: RecursionError.
Every call has its own local variables.
Calls wait on the call stack. The last call finishes first.
Same idea as JS. Python differences: low depth limit and no tail-call optimisation.

Small examples

Recursion limits

Default depth limit: 1000. Deeper raises RecursionError.
Python has no tail-call optimisation.
For deep recursion (long linked list, DFS on 10^5 nodes) raise the limit or go iterative.

Tree recursion

Two ways to move data: pass it down as arguments, or return it up.
Most tree problems: solve left, solve right, combine.

Divide and conquer

Backtracking template

Build an answer step by step: choose, explore, undo.
Keep one shared path list. Undo with path.pop().
Prune early: stop a branch as soon as it cannot work.

Append a copy of the path: res.append(path[:]). res.append(path) stores the same list many times. Later path.pop() empties all of them.

How slow is recursion?

Cost = (number of calls) x (work per call).
One call per level (factorial): O(n). Two calls per level (naive fib): O(2^n).
Repeated calls with the same arguments: use memoization. See Dynamic Programming.
Backtracking: subsets O(2^n), permutations O(n!).
Slices in recursion (s[1:]) copy. Pass indexes for big inputs.

Exercises: Recursion

Write sum_list(a) with recursion. No loops, no sum.

Solution
Flatten a nested list: [1, [2, [3]], 4] gives [1, 2, 3, 4].

Solution
Count how many ways to climb n stairs (1 or 2 steps) with plain recursion. What is the time cost?

Solution
All permutations of a list of distinct numbers.

Solution
Generate all valid strings of n pairs of parentheses.

Solution
Subsets that sum to target (numbers can be picked once). Prune when the sum is too large.

Solution

13. Dynamic Programming

What DP is

DP = recursion + remember answers.
Use it when the same subproblem repeats (overlapping subproblems) and the best answer is built from best sub-answers (optimal substructure).
Signs: "count the ways", "minimum / maximum", "is it possible", "longest ...".
Five steps:
- State: what does dp[i] mean? Write it in words.
- Transition: how does dp[i] come from smaller states?
- Base case: the smallest known answers.
- Order: fill smaller states first.
- Answer: which cell holds it?
Two styles: top-down (recursion + cache) and bottom-up (table + loops).

Top-down: memoization

@cache (3.9+) or @lru_cache(maxsize=None) on the recursive function.
Arguments must be hashable: ints, strings, tuples. Not lists.
Recursion depth still applies. For n above ~1000 raise sys.setrecursionlimit or use bottom-up.

Bottom-up: tables

Make an array. Fill it with loops from small to large.
Start value depends on the question:

Question type	Start value	Base case
Count ways	`0`	`dp[0] = 1`
Minimum	`float("inf")`	`dp[0] = 0`
Maximum	`0` (or `-inf` if negatives exist)	`dp[0] = 0`
Possible? (bool)	`False`	`dp[0] = True`

1D examples

2D examples

Save space

If dp[i] needs only the last few cells, keep variables, not an array.
If a 2D row needs only the previous row, keep two rows.

Top-down or bottom-up?

	Top-down (`@cache`)	Bottom-up (table)
Write	Fast: copy the recursion	Needs the fill order
Depth limit	Yes (1000)	No
Speed	Slower (call overhead)	Faster
Computes	Only needed states	All states

Interview tip: write the recursion first, add @cache, then convert if asked.

Exercises: Dynamic Programming

Why does @cache fail on f([1, 2])? Fix the call.

Solution
Coin change: fewest coins for amount, or -1.

Solution
Unique paths in an m x n grid with @cache (top-down).

Solution
Maximum subarray sum (Kadane).

Solution
Minimum path sum from the top-left to the bottom-right of a grid (move right or down).

Solution
Partition equal subset sum: can the list be split into two parts with equal sums?

Solution

14. Classes for Linked Lists, Trees, Graphs

Class syntax

__init__ = constructor.
self = JS this. It is an explicit first parameter of every method.
No new. Call the class like a function.
Attributes are created by assigning to self.name.
No private keyword. Nobody uses one in interviews.

Linked list patterns

Tree patterns

Trie, Union-Find, Graph

Heap items: lt

A class-level mutable (class A: items = []) is shared by all instances. Create lists in __init__ with self.items = [].

Exercises: Classes

Merge two sorted linked lists.

Solution
Detect a cycle in a linked list.

Solution
Check if a binary tree is a valid BST.

Solution
Implement MinStack with push, pop, top, get_min all O(1).

Solution
Number of islands (grid of "1" and "0") with DFS.

Solution

15. Useful Modules and Input/Output

itertools

math, functools, copy, typing

Input for online assessments

Codility/LeetCode: you write a function. No input parsing.
HackerRank and similar: read from stdin, print to stdout.
input() reads one line as str, without the newline.

Quick debugging

Exercises: Modules and I/O

Input: first line n, second line n ints. Print the sum of the even ones.

Solution
Return all pairs (x, y) from a list (by position, i < j) with x + y == target, using itertools.

Solution
Answer many queries "sum of nums[l..r]" (inclusive) in O(1) each.

Solution
GCD of a whole list.

Solution
Generate all binary strings of length 3.

Solution

16. Cheat Sheet and Gotchas

Time complexity of built-ins

Type	Operation	Cost
list	`lst[i]`, `len`, `append`, `pop()`	O(1)
	`x in lst`, `index`, `remove`, `count`	O(n)
	`pop(0)`, `insert(0, x)`, `insert(i, x)`, `del lst[i]`	O(n)
	`lst[a:b]` (copy)	O(b - a)
	`sort`, `sorted`	O(n log n)
	`min`, `max`, `sum`	O(n)
dict / set	get, set, delete, `in`	O(1) average
dict / set	iterate, copy	O(n)
deque	`append`, `appendleft`, `pop`, `popleft`	O(1)
deque	`dq[i]` in the middle	O(n)
heapq	`heappush`, `heappop`	O(log n)
	`h[0]` peek	O(1)
	`heapify`	O(n)
str	`s[i]`, `len`	O(1)
str	slice, `+`, `in`, `find`, `count`, `join`	O(n)
bisect	`bisect_left` / `bisect_right` (`insort` is O(n))	O(log n)

Pick the structure

Need	Use
Fast "seen before?"	`set`
Count items / group items	`Counter` / `defaultdict(list)`
Value to index lookup	`dict`
LIFO (undo, DFS, parentheses)	`list`
FIFO (BFS, sliding window)	`deque`
Smallest / largest so far, top-K, Dijkstra	`heapq`
Sorted data, lower / upper bound	`bisect`
Overlapping subproblems	`@cache` or a `dp` list

JS to Python quick map

JS	Python
`null`, `undefined`	`None`
`true / false`	`True / False`
`===`, `!==`	`==`, `!=`
`&& \|\| !`	`and or not`
`x ?? y`	`x if x is not None else y`
`cond ? a : b`	`a if cond else b`
`Math.floor(a / b)`	`a // b`
`Math.max(...arr)`	`max(arr)`
`Infinity`	`float("inf")`
`parseInt(s)`	`int(s)`
`console.log(a, b)`	`print(a, b)`
`for (const x of arr)`	`for x in arr:`
`for (const k in obj)`	`for k in d:`
`Object.entries(o)`	`d.items()`
`new Map()`, `{}` as a map	`{}` (dict)
`new Set()`	`set()`
`[...a, ...b]`, `{...a}`	`[a, b]`, `{**a}`
`arr.sort((a, b) => a - b)`	`sorted(arr)` / `key=`
`typeof x`	`type(x)`, `isinstance(x, int)`
`this`, `new Foo()`	`self`, `Foo()`
`function f(a = 1)`	`def f(a=1):`
`(x) => x * 2`	`lambda x: x * 2`