When is Bucket Sort LEAST likely to be an efficient sorting algorithm?
The data is uniformly distributed.
The dataset is very large and sparse.
The data is heavily skewed towards a few buckets.
The elements are integers within a known range.
Which of the following factors significantly influences the choice of sorting algorithm for large datasets?
All of the above
Stability of the sorting algorithm (whether it maintains relative order of equal elements)
Available memory and storage space
Data distribution (uniform, sorted, reverse sorted, etc.)
Given an array of integers, find the subarray with the maximum sum in linear time. The subarray must contain at least one element.
Divide and conquer approach by finding the maximum subarray in the left half, right half, and the one crossing the midpoint.
Kadane's Algorithm, which iterates through the array, keeping track of the maximum sum ending at each index.
Dynamic programming approach by building a table to store the maximum sum ending at each index.
Brute force approach by checking all possible subarrays.
You need to perform matrix multiplication on two large matrices, A and B, where A is of size M x N and B is of size N x P. You have multiple machines available for distributed computing. Which approach would likely yield the BEST performance improvement?
Divide matrix B into column blocks and distribute each block with a copy of A to different machines.
Divide both matrices A and B into smaller, equally sized submatrices and distribute the computation of these submatrices across the machines.
Divide matrix A into row blocks and distribute each block with a copy of B to different machines.
Performing the matrix multiplication sequentially on a single machine without any distribution.
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the missing number.
Calculate the sum of all numbers from 0 to n and subtract the sum of the array elements.
Use a hash table to store the presence of each number.
Sort the array and find the missing element.
Use the XOR operation to find the missing number.
Consider an algorithm that iterates through a sorted array of size N. In each iteration, it performs a binary search on the array. What is the overall time complexity of this algorithm?
O(log N)
O(N)
O(N^2)
O(N log N)
Which sorting algorithm is the MOST suitable for sorting a massive dataset that cannot fit entirely in RAM?
External Merge Sort
Quick Sort
Bubble Sort
Merge Sort
What is a key advantage of Radix Sort over comparison-based sorting algorithms like Quick Sort and Merge Sort?
Radix Sort can achieve better than O(n log n) time complexity in certain cases.
Radix Sort guarantees stability, while Quick Sort and Merge Sort do not.
Radix Sort is generally more suitable for sorting strings than numerical data.
Radix Sort is always more space-efficient than comparison-based algorithms.
In the context of external sorting, what does the term 'run' typically refer to?
The process of merging two sorted subarrays.
A sequence of sorted elements that can be held in memory.
A single pass through the entire dataset.
The number of disk I/O operations performed.
Given an array of n integers, find three elements in the array such that the sum is closest to a given target number. Return the sum of the three integers.
Use a hash table to store the sum of all pairs of elements.
Use three nested loops to iterate through all possible triplets.
Use dynamic programming to store the closest sum for all subarrays of size three.
Sort the array and use two pointers to find pairs of elements with a sum close to the target minus the current element.