Appendix C — Python Interview Toolkit

The Python examples use only the standard library and favor explicit loops over clever compression. Know these operations well enough that API recall does not interrupt the algorithm.

C.1 Lists and sequences

API	Interview use	Typical cost
len(values)	item count	\(O(1)\)
values[i]	indexed access	\(O(1)\)
append(x)	add at end	amortized \(O(1)\)
pop()	remove last item / stack top	\(O(1)\)
values[a:b]	copied slice	\(O(b-a)\)

[value] * n is safe for immutable scalar values. Do not use it to create nested mutable rows; use [[] for _ in range(n)] instead.

C.2 Dictionaries, sets, and counting

A dict provides expected \(O(1)\) membership, lookup, and assignment:

if needed in index_by_value:
    return index_by_value[needed]
index_by_value[value] = index

collections.defaultdict(list) is convenient for grouping, and collections.Counter is a dictionary specialized for frequencies. Use a plain dictionary when showing the state transition explicitly helps the interview explanation.

C.3 Queue and stack

A list is the ordinary stack: append pushes and pop removes the top.

Use collections.deque for a queue:

Operation	Meaning
append(x)	enqueue at back
popleft()	dequeue from front
len(queue)	current frontier size

Removing index zero from a list is \(O(n)\) and should not be used as a queue operation.

C.4 Sorting and comparison

sorted(values) returns a new list; values.sort() changes a list in place. A key function usually reads more directly than a comparator:

ranked = sorted(words, key=lambda word: (-frequency[word], word))

Tuple keys compare component by component, which makes primary and tie-break ordering compact.

C.5 Strings and characters

Iterating a Python str yields one-character strings representing Unicode code points. Strings are immutable, so build a sorted canonical key with:

key = "".join(sorted(word))

This is not the same as Unicode grapheme-cluster processing. Clarify the intended meaning of “character” when non-ASCII input matters.

C.6 Interview nodes and identity

Python has no standard interview-style ListNode or TreeNode. Define only the fields the problem needs:

class ListNode:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

Use is for node identity. == may invoke value equality and is not a substitute when the contract names a particular node object.

C.7 unittest in the examples

Every module defines a unittest.TestCase and ends with:

if __name__ == "__main__":
    unittest.main()

Common assertions include assertEqual, assertTrue, assertFalse, assertIs, assertIsNone, and assertRaises. Tests should assert observable behavior rather than local maps, queues, or pointer positions.