Hackerrank Python Data Structures & Algorithms 5 — Questions and Answers
Question 1: Which sorting algorithm has the best worst-case time complexity?
- Quicksort — O(n log n)
- Bubble sort — O(n)
- Merge sort — O(n log n) (Correct answer)
- Selection sort — O(n log n)
Correct 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.
Question 2: What will `Counter('aabbbc').most_common(2)` return?
- [('b', 3), ('a', 2)] (Correct answer)
- [('a', 2), ('b', 3)]
- [('b', 3), ('c', 1)]
- {'b': 3, 'a': 2}
Correct answer: [('b', 3), ('a', 2)]
most_common(2) returns the two highest-frequency elements in descending order as a list of tuples.
Question 3: In a singly linked list, what is the time complexity to find the middle node?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n^2)
Correct answer: O(n)
Without direct index access, you must traverse up to n/2 nodes, making it O(n).
Question 4: What is the key property of a binary search tree (BST)?
- All nodes have exactly two children
- Left subtree values < node value < right subtree values (Correct answer)
- The tree is always balanced
- Duplicate values are forbidden
Correct 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.
Question 5: Which Python snippet uses dynamic programming to compute the nth Fibonacci number in O(n) time and O(1) space?
- return fib(n-1) + fib(n-2)
- memo = {}; return memo.setdefault(n, fib(n-1)+fib(n-2))
- a,b=0,1 for _ in range(n): a,b=b,a+b return a (Correct answer)
- return sum(fib(i) for i in range(n))
Correct 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.
Question 6: What problem does a hash collision cause, and how does Python resolve it?
- Data loss — Python raises KeyError
- Duplicate keys — Python overwrites the old value
- Slowdown — Python uses open addressing or chaining (Correct answer)
- Memory leak — Python deletes the colliding entry
Correct 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.
Question 7: What is the time complexity of Dijkstra's algorithm using a min-heap (priority queue) with V vertices and E edges?
- O(V^2)
- O(E log V) (Correct answer)
- O(V log E)
- O(E + V)
Correct answer: O(E log V)
With a binary min-heap, each edge relaxation costs O(log V), giving O(E log V) total.
Hackerrank Python Data Structures & Algorithms 5
Which sorting algorithm has the best worst-case time complexity?