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

Sort and scan

Answer

Use a hash set

Answer

Two nested loops

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

To sort an array in-place

Answer

To find the median in O(log n)

Answer

To reverse subarrays efficiently

Question 3

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

Accepted Answer

Kadane's algorithm

Answer

Merge sort

Answer

Binary search

Answer

Floyd's algorithm

Question 4

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

Accepted Answer

O(n)

Answer

O(k)

Answer

O(n log n)

Answer

O(n×k)

Question 5

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

Accepted Answer

Quickselect algorithm

Answer

Sort and index

Answer

Min-heap of size k

Answer

Counting sort

Question 6

What is the key property of a sorted rotated array that enables binary search on it?

Accepted Answer

At least one half of the array is always sorted

Answer

All elements are distinct

Answer

The pivot is always at the center

Answer

The array has an odd number of elements