Python as Your Interview Language
Most interviews let you choose the language. Python, JavaScript, Java, C++, Go, Rust, Ruby and C are all accepted almost everywhere, and the right choice is simply the one you write fastest without looking things up. This course uses Python: it is short to write, easy to read aloud, and its standard library already holds most of the tools the patterns need.
The rule
Pick one language and know its toolbox cold, costs included.
"Cold" means you never pause to remember a name, and "costs included" means you know how long each tool takes. These are the pieces that turn the patterns in this course into a few lines:
from collections import Counter, defaultdict, deque
import heapq
seen = set() # membership test is instant on average
counts = Counter("banana") # Counter({'a': 3, 'n': 2, 'b': 1})
groups = defaultdict(list) # a missing key starts as an empty list
queue = deque([1, 2, 3]) # fast at both ends: popleft(), appendleft()
heap = [7, 2, 9, 4]
heapq.heapify(heap) # heap[0] is now the smallest item
smallest = heapq.heappop(heap) # 2
by_length = sorted(["kiwi", "fig", "banana"], key=len) # ['fig', 'kiwi', 'banana']A few facts worth knowing by heart:
x in some_setandkey in some_dicttake roughly constant time.x in some_listscans the whole list.some_list.pop(0)shifts every remaining item, so usedeque.popleft()for queues.sortedtakes akey. A tuple key breaks ties:key=lambda t: (-t[1], t[0])sorts by the second field descending, then by the first ascending.- Python integers never overflow, and
//rounds toward minus infinity, so-7 // 2is-4. - Strings cannot be changed in place. Build a list of pieces and
"".jointhem at the end. - Recursion stops at a depth of about 1,000 by default, which matters for very deep recursive solutions.
If you choose another language, build the same list for it before your first interview: its hash map and set, its double-ended queue, its heap, and its sort with a custom order.
The shortcut
For every line inside a loop, name the operation, then name its cost, and multiply by the number of times the loop runs. Most "correct but too slow" submissions hide one expensive line inside a cheap-looking loop.
The code
shared = [x for x in a if x in b], whereaandbare lists of up to 100,000 names each.
The trap is judging speed by how short the code looks. One in on the wrong container can turn a one-liner into the slowest line in the program.
Drills
Answer fast — trust the rule.
Which of these takes roughly constant time on average?
What does Counter("banana").most_common(1) return?
After h = [7, 2, 9, 4] and heapq.heapify(h), what does heapq.heappop(h) return?
Why reach for deque instead of a list when you remove items from the front again and again?
What comes first in sorted([("ana", 3), ("ben", 5), ("cy", 5)], key=lambda t: (-t[1], t[0]))?
Remember
- Pick one language and know its toolbox cold, costs included.
- Shortcut: for each line in a loop, name its cost and multiply.
- Trap:
x in some_listinside a loop; make it a set first.