Python Data Structures & Algorithms Flashcards

Which sorting algorithm has the best worst-case time complexity?

Answer: Merge sort — O(n log n)

Merge sort guarantees O(n log n) in all cases; quicksort degrades to O(n^2) in the worst case.

What will `Counter('aabbbc').most_common(2)` return?

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

most_common(2) returns the two highest-frequency elements in descending order as a list of tuples.

In a singly linked list, what is the time complexity to find the middle node?

Answer: O(n)

Without direct index access, you must traverse up to n/2 nodes, making it O(n).

What is the key property of a binary search tree (BST)?

Answer: Left subtree values < node value < right subtree values

A BST maintains the invariant that every left descendant is smaller and every right descendant is larger than the current node.

Which Python snippet uses dynamic programming to compute the nth Fibonacci number in O(n) time and O(1) space?

Answer: a,b=0,1 for _ in range(n): a,b=b,a+b return a

Iterating with two variables achieves O(n) time and O(1) space by only storing the last two values.

What problem does a hash collision cause, and how does Python resolve it?

Answer: Slowdown — Python uses open addressing or chaining

Python's dict uses open addressing (probing) to find the next available slot when two keys hash to the same index.

What is the time complexity of Dijkstra's algorithm using a min-heap (priority queue) with V vertices and E edges?

Answer: O(E log V)

With a binary min-heap, each edge relaxation costs O(log V), giving O(E log V) total.