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

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?

Accepted Answer

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

Answer

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?

Accepted Answer

O(n)

Answer

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)?

Accepted Answer

Left subtree values < node value < right subtree values

Answer

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?

Accepted Answer

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

Answer

Iterating with two variables achieves O(n) time and O(1) space by only storing the last two values.

(Hackerrank) HackerRank Python Certification Practice Test