Data Structures Arrays and Strings 3

Question 1

What is the best approach to find all duplicate elements in an array of integers in O(n) time and O(1) extra space?

Accepted Answer

Negate visited indices (sign marking)

Answer

By negating the element at each visited index, you can detect duplicates in O(n) time using the array itself as a marker with O(1) extra space.

Question 2

What is the purpose of prefix sum arrays?

Accepted Answer

To answer range sum queries in O(1) after O(n) preprocessing

Answer

A prefix sum array stores cumulative sums so that any subarray sum can be computed in O(1) time using prefix[r] - prefix[l-1].

Question 3

Which technique solves the 'maximum subarray sum' problem in O(n) time?

Accepted Answer

Kadane's algorithm

Answer

Kadane's algorithm tracks the maximum sum ending at each position, updating the global maximum in a single O(n) pass.

Question 4

What is the time complexity of rotating an array of n elements by k positions in place?

Accepted Answer

O(n)

Answer

Using the three-reversal method, an array can be rotated by k positions in O(n) time with O(1) extra space.

Question 5

Which approach finds the kth largest element in an unsorted array in average O(n) time?

Accepted Answer

Quickselect algorithm

Answer

Quickselect uses the partition step from quicksort to narrow down to the kth element, achieving O(n) average time without fully sorting.

Data Structures Practice Test