Python Data Structures & Algorithms Flashcards

What does `heapq.heappush(h, item)` guarantee about the resulting list `h`?

Answer: h[0] is always the smallest element

Python's heapq maintains a min-heap invariant, so h[0] is always the minimum element.

What is the output of `list(zip([1,2,3], [4,5]))`?

Answer: [(1,4),(2,5)]

zip stops at the shortest iterable, so the result only contains pairs up to index 1.

Which approach correctly implements a graph as an adjacency list in Python?

Answer: graph = {0: [1,2], 1: [0,2]}

A dict mapping each node to a list of its neighbors is the standard adjacency list representation.

What is the average time complexity of `item in my_set` for a Python set?

Answer: O(1)

Python sets use hash tables, so membership testing is O(1) on average.

Which code snippet correctly performs a binary search on a sorted list `arr` for target `t`?

Answer: import bisect; bisect.bisect_left(arr, t)

bisect.bisect_left returns the insertion point for t in O(log n); arr.index() is O(n).

What does BFS (Breadth-First Search) use to track nodes to visit next?

Answer: Queue

BFS uses a FIFO queue to explore nodes level by level.

What is the time complexity of accessing an element by index in a Python list?

Answer: O(1)

Python lists are backed by dynamic arrays, so index access is O(1) constant time.