Algorithms Flashcards

Which Python data structure is ideal for BFS (breadth-first search) due to O(1) append and popleft?

Answer: collections.deque

`collections.deque` supports O(1) operations on both ends, making it efficient as a BFS queue.

What is the time complexity of inserting an element into a Python `heapq` (min-heap)?

Answer: O(log n)

Heap insertion (heappush) requires at most log n comparisons to restore the heap property.

What does the following return: `max([3, 1, 4, 1, 5], key=lambda x: -x)`?

Answer: 1

Using `-x` as the key inverts comparisons, so `max` finds the element with the largest negative value, which is the smallest element (1).

In the context of graph algorithms, what does DFS stand for and what data structure does it use?

Answer: Depth-First Search, stack

DFS explores as deep as possible before backtracking, using a stack (or recursion call stack) to track the path.

What is the output of `list(zip([1,2,3], ['a','b']))`?

Answer: [(1,'a'),(2,'b')]

`zip` stops at the shortest iterable, so only two pairs are produced.

Which approach solves the coin change problem (minimum coins for amount n) most efficiently?

Answer: Bottom-up dynamic programming

Bottom-up DP builds solutions for all amounts from 0 to n, guaranteeing an optimal result in O(n * coins) time.

What is the result of `sum(1 for c in 'hello world' if c == 'l')`?

Answer: 3

'hello world' contains 'l' at indices 2, 3, and 9, so the generator yields 1 three times.