Hackerrank Python Data Structures & Algorithms 3 — Questions and Answers
Question 1: What is the time complexity of inserting an element at the beginning of a Python list?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n log n)
Correct answer: O(n)
Inserting at index 0 requires shifting all existing elements one position right, making it O(n).
Question 2: Which Python collection type uses a hash table internally and guarantees O(1) average-case lookup?
- list
- tuple
- dict (Correct answer)
- deque
Correct answer: dict
Python dicts are hash maps, providing O(1) average-case get/set operations.
Question 3: What does `collections.deque` provide that a regular list does not?
- Sorted order
- O(1) appends and pops from both ends (Correct answer)
- Duplicate removal
- Thread-safe reads
Correct 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.
Question 4: Given `d = defaultdict(list)`, what happens when you access `d['new_key']`?
- KeyError is raised
- None is returned
- An empty list is created and returned (Correct answer)
- 0 is returned
Correct 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.
Question 5: Which algorithm does Python's built-in `sort()` use?
- Quicksort
- Heapsort
- Timsort (Correct answer)
- Mergesort
Correct answer: Timsort
Python uses Timsort, a hybrid of merge sort and insertion sort, with O(n log n) worst case.
Question 6: What is the space complexity of a recursive Fibonacci function without memoization for input n?
- O(1)
- O(n) (Correct answer)
- O(2^n)
- O(log n)
Correct 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).
Question 7: Which data structure is most appropriate for implementing a LIFO (Last-In, First-Out) pattern in Python?
- collections.deque used as a queue
- list used with append/pop (Correct answer)
- heapq module
- collections.OrderedDict
Correct 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.
Hackerrank Python Data Structures & Algorithms 3
What is the time complexity of inserting an element at the beginning of a Python list?