Python Data Structures & Algorithms Flashcards

What is the time complexity of inserting an element at the beginning of a Python list?

Answer: O(n)

Inserting at index 0 requires shifting all existing elements one position right, making it O(n).

Which Python collection type uses a hash table internally and guarantees O(1) average-case lookup?

Answer: dict

Python dicts are hash maps, providing O(1) average-case get/set operations.

What does `collections.deque` provide that a regular list does not?

Answer: O(1) appends and pops from both ends

deque is a doubly-linked list optimized for O(1) appendleft/popleft, unlike list which is O(n) at the left end.

Given `d = defaultdict(list)`, what happens when you access `d['new_key']`?

Answer: An empty list is created and returned

defaultdict calls the factory function (list) to create a default value when a missing key is accessed.

Which algorithm does Python's built-in `sort()` use?

Answer: Timsort

Python uses Timsort, a hybrid of merge sort and insertion sort, with O(n log n) worst case.

What is the space complexity of a recursive Fibonacci function without memoization for input n?

Answer: O(n)

The call stack depth reaches n at most, so space complexity is O(n) even though the time complexity is O(2^n).

Which data structure is most appropriate for implementing a LIFO (Last-In, First-Out) pattern in Python?

Answer: list used with append/pop

A Python list with append() to push and pop() to pull from the end naturally implements a LIFO stack.