Online Coding Test — free practice test

Correct answer: O(log n). Each comparison discards half the remaining range, so the number of steps is the number of times n can be halved — log₂ n.

Correct answer: 10. 2⁹ = 512 and 2¹⁰ = 1,024, so ten halvings are enough to cover 1,000 items. Nine would only guarantee 512.

Correct answer: O(n log n). At n = 10⁶, O(n log n) is roughly 2×10⁷ operations. O(n²) is 10¹², which no judge will finish; the exponential and factorial options are far worse.

Correct answer: 5,050. The closed form is n(n+1)/2, so 100 × 101 ÷ 2 = 5,050. Knowing it lets you verify a loop’s output in O(1).

Correct answer: Maximum contiguous subarray sum, in O(n). Kadane's keeps a running sum, resets it whenever it turns negative, and tracks the best sum seen — one pass, so O(n).

Correct answer: Hash map. A hash map computes the slot directly from the key. A sorted array needs O(log n) via binary search, a linked list O(n), and a heap only gives O(1) access to its root.

Correct answer: O(n²). On an already-sorted input with a bad pivot choice, each partition removes only one element, giving n levels of O(n) work. The O(n log n) figure is the average case.

Correct answer: Queue. A queue removes from the end it did not add to, so the oldest element leaves first. A stack is last-in, first-out.