Hackerrank Python Data Structures & Algorithms 5

Question 1

Which sorting algorithm has the best worst-case time complexity?

Accepted Answer

Merge sort — O(n log n)

Answer

Quicksort — O(n log n)

Answer

Bubble sort — O(n)

Answer

Selection sort — O(n log n)

Question 2

What will `Counter('aabbbc').most_common(2)` return?

Accepted Answer

[('b', 3), ('a', 2)]

Answer

[('a', 2), ('b', 3)]

Answer

[('b', 3), ('c', 1)]

Answer

{'b': 3, 'a': 2}

Question 3

In a singly linked list, what is the time complexity to find the middle node?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n^2)

Question 4

What is the key property of a binary search tree (BST)?

Accepted Answer

Left subtree values < node value < right subtree values

Answer

All nodes have exactly two children

Answer

The tree is always balanced

Answer

Duplicate values are forbidden

Question 5

Which Python snippet uses dynamic programming to compute the nth Fibonacci number in O(n) time and O(1) space?

Accepted Answer

a,b=0,1
for _ in range(n): a,b=b,a+b
return a

Answer

return fib(n-1) + fib(n-2)

Answer

memo = {}; return memo.setdefault(n, fib(n-1)+fib(n-2))

Answer

return sum(fib(i) for i in range(n))

Question 6

What problem does a hash collision cause, and how does Python resolve it?

Accepted Answer

Slowdown — Python uses open addressing or chaining

Answer

Data loss — Python raises KeyError

Answer

Duplicate keys — Python overwrites the old value

Answer

Memory leak — Python deletes the colliding entry

Question 7

What is the time complexity of Dijkstra's algorithm using a min-heap (priority queue) with V vertices and E edges?

Accepted Answer

O(E log V)

Answer

O(V^2)

Answer

O(V log E)

Answer

O(E + V)