Hackerrank Algorithms 2 — Questions and Answers
Question 1: What is the time complexity of binary search on a sorted list of n elements?
- O(n)
- O(log n) (Correct answer)
- O(n log n)
- O(1)
Correct answer: O(log n)
Binary search halves the search space each iteration, giving O(log n) time complexity.
Question 2: Which Python built-in function returns the index of the leftmost value in a sorted list that is greater than or equal to a target, using the `bisect` module?
- bisect.bisect_right
- bisect.bisect_left (Correct answer)
- bisect.insort
- bisect.find
Correct answer: bisect.bisect_left
`bisect.bisect_left` returns the leftmost position where the target can be inserted to keep the list sorted.
Question 3: Given a list `nums = [3, 1, 4, 1, 5, 9]`, what does `sorted(nums, reverse=True)` return?
- [1, 1, 3, 4, 5, 9]
- [9, 5, 4, 3, 1, 1] (Correct answer)
- [3, 1, 4, 1, 5, 9]
- [9, 5, 4, 1, 3, 1]
Correct answer: [9, 5, 4, 3, 1, 1]
`sorted()` with `reverse=True` returns a new list sorted in descending order.
Question 4: Which algorithm sorts by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning?
- Bubble Sort
- Insertion Sort
- Selection Sort (Correct answer)
- Merge Sort
Correct answer: Selection Sort
Selection sort scans the unsorted portion each pass to select the minimum and swap it into position.
Question 5: What is the worst-case time complexity of quicksort?
- O(n log n)
- O(n)
- O(n^2) (Correct answer)
- O(log n)
Correct answer: O(n^2)
Quicksort degrades to O(n²) when the pivot is always the smallest or largest element (already sorted input with bad pivot choice).
Question 6: In Python, what does `collections.Counter([1,1,2,3,3,3])` return?
- [1, 1, 2, 3, 3, 3]
- Counter({1: 2, 3: 3, 2: 1})
- Counter({3: 3, 1: 2, 2: 1}) (Correct answer)
- {1: 2, 2: 1, 3: 3}
Correct answer: Counter({3: 3, 1: 2, 2: 1})
`Counter` returns a dictionary-like object with elements as keys and their counts as values, ordered by most common.
Question 7: Which data structure gives O(1) average time for insert, delete, and lookup?
- List
- Sorted list
- Hash table (dict/set) (Correct answer)
- Binary search tree
Correct answer: Hash table (dict/set)
Hash tables use hashing to achieve O(1) average-case for the three core operations.
Hackerrank Algorithms 2
What is the time complexity of binary search on a sorted list of n elements?