Hackerrank Python Data Structures & Algorithms 4 — Questions and Answers
Question 1: What does `heapq.heappush(h, item)` guarantee about the resulting list `h`?
- h is fully sorted
- h[0] is always the smallest element (Correct answer)
- h is a max-heap
- h contains no duplicates
Correct answer: h[0] is always the smallest element
Python's heapq maintains a min-heap invariant, so h[0] is always the minimum element.
Question 2: What is the output of `list(zip([1,2,3], [4,5]))`?
- [(1,4),(2,5),(3,None)]
- [(1,4),(2,5)] (Correct answer)
- [(1,4,2,5)]
- TypeError
Correct answer: [(1,4),(2,5)]
zip stops at the shortest iterable, so the result only contains pairs up to index 1.
Question 3: Which approach correctly implements a graph as an adjacency list in Python?
- graph = [[0,1],[1,0]]
- graph = {0: [1,2], 1: [0,2]} (Correct answer)
- graph = {(0,1), (1,2)}
- graph = [(0,1),(1,2)]
Correct answer: graph = {0: [1,2], 1: [0,2]}
A dict mapping each node to a list of its neighbors is the standard adjacency list representation.
Question 4: What is the average time complexity of `item in my_set` for a Python set?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n^2)
Correct answer: O(1)
Python sets use hash tables, so membership testing is O(1) on average.
Question 5: Which code snippet correctly performs a binary search on a sorted list `arr` for target `t`?
- import bisect; bisect.bisect_left(arr, t) (Correct answer)
- arr.index(t)
- sorted(arr).index(t)
- arr.find(t)
Correct answer: import bisect; bisect.bisect_left(arr, t)
bisect.bisect_left returns the insertion point for t in O(log n); arr.index() is O(n).
Question 6: What does BFS (Breadth-First Search) use to track nodes to visit next?
- Stack
- Priority queue
- Queue (Correct answer)
- Set
Correct answer: Queue
BFS uses a FIFO queue to explore nodes level by level.
Question 7: What is the time complexity of accessing an element by index in a Python list?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n log n)
Correct answer: O(1)
Python lists are backed by dynamic arrays, so index access is O(1) constant time.
Hackerrank Python Data Structures & Algorithms 4
What does `heapq.heappush(h, item)` guarantee about the resulting list `h`?